Frontend School

Find Next Cheaper Item

DSA
easy

Find Next Cheaper Item

Easy
Arrays
Stack
Monotonic Stack

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: prices: An array of integers, where prices[k] represents the price of the k-th item.
  • Output: An array of integers, result, where result[i] is the index of the next cheaper item to the right, or -1 if none exists.

Clarifications

  • All prices are positive integers.
  • We are looking for a strictly cheaper item (prices[j] < prices[i]).
  • If multiple cheaper items exist to the right, return the index of the first one encountered when scanning from left to right (i.e., the smallest j > i).

Examples

1

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.

2

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.

3

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

Constraints & assumptions

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

What interviewers evaluate

  • Correctness: The solution accurately identifies the next cheaper item for all elements or correctly identifies when none exists.
  • Efficiency: The solution achieves optimal time and space complexity (typically O(N) time and O(N) space).
  • Code Structure & Readability: The code is well-organized, clean, and easy to understand, with appropriate variable names and comments if necessary.
  • Algorithmic Approach: Demonstrates a clear understanding and correct application of the Monotonic Stack pattern.

Loading editor...