FastPrepNext Smaller Ticket Price

Next Smaller Ticket Price

Amazon logoAmazon● MediumINTERNONSITE INTERVIEW

Problem statement

You are given an integer array prices, where prices[i] is the price of ticket i.

For each ticket, find the next strictly smaller price to its right. If no later ticket is cheaper, the answer for that ticket is -1.

Return an array of the same length as prices containing those answers in index order.

Function

nextSmallerPrices(prices: int[]) → int[]

Examples

Example 1

prices = [8,4,6,2,3]return = [4,2,2,-1,-1]

Ticket 8 is followed by cheaper 4. Ticket 4 is followed by cheaper 2. Ticket 6 is followed by cheaper 2. Tickets 2 and 3 have no later cheaper price.

Example 2

prices = [5,4,3,2,1]return = [4,3,2,1,-1]

Each ticket is immediately followed by a cheaper ticket except the last.

Example 3

prices = [1,2,3]return = [-1,-1,-1]

Every later ticket is more expensive, so every answer is -1.

Constraints

  • 1 <= prices.length <= 10^5.
  • 1 <= prices[i] <= 10^9.

Source note: Author-written prompt excerpt retained for source fidelity.

More Amazon problems

See Amazon hiring insights
Saved
public int[] nextSmallerPrices(int[] prices) {
  // Write your code here.
}
prices[8,4,6,2,3]
expected[4,2,2,-1,-1]
Checking account…