Find Next Cheaper Item
Bigbasket aims to provide customers with the best shopping experience, which includes smart recommendations and competitive pricing. For effective inventory management and pricing strategies, it's often useful to understand how an item's price compares to others on the shelf. This problem asks you to identify, for each item, the first item to its right that is strictly cheaper.
You are given an array prices representing the prices of various items laid out on a shelf from left to right. Your task is to implement a function that returns an array result of the same length. For each index i in prices, result[i] should store the index j (where j > i) of the first item to the right of prices[i] such that prices[j] < prices[i]. If no such item exists to the right, result[i] should be -1.
prices: An array of integers, where prices[k] represents the price of the k-th item.result, where result[i] is the index of the next cheaper item to the right, or -1 if none exists.prices[j] < prices[i]).j > i).Examples
Example 1
Input:
prices = [10, 3, 7, 5, 8, 2]
Output:
[1, 5, 3, 5, 5, -1]
Note:
For 10 (index 0), 3 (index 1) is the first cheaper item. For 3 (index 1), 2 (index 5) is the first cheaper item. For 7 (index 2), 5 (index 3) is the first cheaper item. For 5 (index 3), 2 (index 5) is the first cheaper item. For 8 (index 4), 2 (index 5) is the first cheaper item. For 2 (index 5), no cheaper item exists to its right.
Example 2
Input:
prices = [5, 4, 3, 2, 1]
Output:
[1, 2, 3, 4, -1]
Note:
In a strictly decreasing sequence, each item's next cheaper item is simply the one immediately to its right.
Example 3
Input:
prices = [1, 2, 3, 4, 5]
Output:
[-1, -1, -1, -1, -1]
Note:
In a strictly increasing sequence, no item has a cheaper item to its right.
Constraints
1 <= prices.length <= 10^51 <= prices[i] <= 10^9prices[i] are integers.Loading editor...