DSA problem
Final Prices With a Special Discount in a Shop
You are given an integer array prices where prices[i] is the price of the i-th item in a shop. There is a special discount: if you buy the i-th item, you receive a discount equivalent to prices[j] where j is the smallest index such that j > i and prices[j] <= prices[i]. If no such j exists, you receive no discount. Return an array where the i-th element is the final price you pay for the i-th item — that is, prices[i] - discount.
The brute-force approach is straightforward: for each item i, walk to the right scanning prices[j] until you find the first j with prices[j] <= prices[i]. That costs O(n²) time in the worst case (already-sorted-descending input), which is wasteful because many of those scans repeat work.
A monotonic stack solves this in a single linear pass. We iterate left-to-right and maintain a stack of indices whose prices are still waiting for a discount-eligible smaller-or-equal price. The stack stays monotonically non-increasing from bottom to top: when we see a new price prices[i], any index on top of the stack whose price is greater than or equal to prices[i] has just found its discount, so we pop and subtract prices[i] from answer[top].
After processing the array, anything still on the stack never found a smaller-or-equal price to its right and keeps its original price. Total work is O(n) because each index is pushed and popped at most once.
Examples
prices = [8,4,6,2,3][4,2,4,2,3]prices = [1,2,3,4,5][1,2,3,4,5]prices = [10,1,1,6][9,0,1,6]Constraints
- 1 <= prices.length <= 500
- 1 <= prices[i] <= 10^3
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.