Final Prices With a Special Discount in a Shop

Final Prices With a Special Discount in a Shop

What is this problem about?

The Final Prices With a Special Discount interview question asks you to calculate the final price of items after applying a specific discount rule. For each item $i$ at price prices[i], you receive a discount equal to the price of the first item $j$ to its right ($j > i$) such that prices[j] <= prices[i]. If no such item exists, you pay the full price.

Why is this asked in interviews?

Companies like Uber and Amazon use this Monotonic Stack interview pattern to test your efficiency with linear data. It’s a "Next Smaller Element" variation. While an O(N^2) solution using nested loops is easy to write, the interviewer expects the O(N) stack-based solution, which demonstrates a more advanced understanding of data structures.

Algorithmic pattern used

This problem is solved using a Monotonic Increasing Stack.

1. Iterate through the prices.
2. Maintain a stack of indices whose prices haven't found a discount yet.
3. For the current price prices[i]:
   • While the stack is not empty and the price at the stack's top index is greater than or equal to prices[i]:
     • The current item i is the "first smaller or equal" item for the item at the top of the stack.
     • Apply the discount: prices[stack.pop()] -= prices[i].
4. Push the current index i onto the stack.
5. Return the modified prices array.

Example explanation

Prices: [8, 4, 6, 2, 3]

1. Item 8: Stack [0].
2. Item 4: 4 <= 8. Discount for 8 is 4. 8 - 4 = 4. Stack [1].
3. Item 6: 6 > 4. Stack [1, 2].
4. Item 2:
   • 2 <= 6. Discount for 6 is 2. 6 - 2 = 4.
   • 2 <= 4. Discount for 4 is 2. 4 - 2 = 2.
   • Stack [3].
5. Item 3: 3 > 2. Stack [3, 4]. Final: [4, 2, 4, 2, 3].

Common mistakes candidates make

• Brute Force: Using two nested loops, which results in O(N^2) time complexity.
• Stack Type: Confusing a monotonic increasing stack with a monotonic decreasing stack.
• Index vs Value: Storing values in the stack instead of indices, which makes it harder to update the original array.

Interview preparation tip

"Next Smaller/Greater Element" is a very common interview theme. Whenever you need to look for the first element to the right that satisfies a comparison, a Monotonic Stack is the optimal solution.