Final Prices With a Special Discount in a Shop

LeetCode 1475: Final Prices With a Special Discount in a Shop Solution & Explanation

Problem Overview

TL;DR: Use a Monotonic Stack to find the "Next Smaller Element" for each item in the array in linear time, subtracting that value from the original price.

The problem asks us to process an array of item prices. For each item at index i, we need to look ahead to subsequent indices j > i to find the first price that is less than or equal to prices[i]. If such a price exists, it acts as a discount, and we subtract it from the original price. If no such price exists to the right, the item is sold at its original price.

This is a classic variation of the "Next Greater Element" problem, specifically adapted for LeetCode 1475 as a "Next Smaller or Equal Element" search.

Brute Force Approach for Final Prices With a Special Discount in a Shop

The naive approach involves simulating the problem statement directly using nested loops. For every item in the array, we scan all subsequent items to find the first valid discount.

1. Create a copy of the prices array to store the results.
2. Iterate through the array with an index i from 0 to n-1.
3. For each i, start an inner loop j from i+1 to n-1.
4. Check if prices[j] <= prices[i].
5. The moment this condition is met, subtract prices[j] from the result at i and break the inner loop (since we only apply the first valid discount).

1# Pseudo-code for Brute Force
2n = length(prices)
3answer = copy(prices)
4for i from 0 to n-1:
5    for j from i+1 to n-1:
6        if prices[j] <= prices[i]:
7            answer[i] = prices[i] - prices[j]
8            break
9return answer

Complexity Analysis:

• Time Complexity: $O(N^2)$. In the worst case (a strictly increasing array like [1, 2, 3, 4, 5]), for every element i, the inner loop runs until the end of the array without finding a discount.
• Space Complexity: $O(1)$ auxiliary space (ignoring the output array).

Why it fails: While the constraints for Final Prices With a Special Discount in a Shop are small ($N \le 500$), allowing an $O(N^2)$ solution to pass, this approach fails to demonstrate the optimal algorithmic thinking required for technical interviews. If the input size were increased to $10^5$ (common in similar problems), this solution would result in a Time Limit Exceeded (TLE).

Algorithm Strategy: Stack Patterns

1. Initialization: Create a result array answer initialized with the original prices. This ensures that if no discount is found, the original price remains. Initialize an empty stack to store indices.
2. Iteration: Traverse the prices array from left to right with index i.
3. Monotonic Maintenance:
   • While the stack is not empty AND prices[i] is less than or equal to the price at the index stored at the top of the stack (prices[stack.peek()]):
     • This means prices[i] is the "Next Smaller or Equal Element" for stack.peek().
     • Pop the index idx from the stack.
     • Update answer[idx]: answer[idx] = prices[idx] - prices[i].
4. Push: Push the current index i onto the stack. This item is now waiting for a future discount.
5. Termination: After the loop finishes, return the answer array. Any indices remaining in the stack simply never found a discount, so their values in answer remain the original prices.

Execution Flow

Let's trace the algorithm with prices = [8, 4, 6, 2, 3].

1. Initialize: answer = [8, 4, 6, 2, 3], stack = [].
2. i = 0, Price = 8:
   • Stack is empty.
   • Push 0. Stack: [0].
3. i = 1, Price = 4:
   • Check Stack: Top is 0 (Price 8). Is 4 <= 8? Yes.
   • Pop 0. The discount for index 0 is 4.
   • Update answer[0] = 8 - 4 = 4.
   • Stack is empty.
   • Push 1. Stack: [1].
4. i = 2, Price = 6:
   • Check Stack: Top is 1 (Price 4). Is 6 <= 4? No.
   • Push 2. Stack: [1, 2]. (Note: Prices at indices [1, 2] are [4, 6], which is increasing).
5. i = 3, Price = 2:
   • Check Stack: Top is 2 (Price 6). Is 2 <= 6? Yes.
   • Pop 2. The discount for index 2 is 2.
   • Update answer[2] = 6 - 2 = 4.
   • Check Stack: Top is 1 (Price 4). Is 2 <= 4? Yes.
   • Pop 1. The discount for index 1 is 2.
   • Update answer[1] = 4 - 2 = 2.
   • Stack is empty.
   • Push 3. Stack: [3].
6. i = 4, Price = 3:
   • Check Stack: Top is 3 (Price 2). Is 3 <= 2? No.
   • Push 4. Stack: [3, 4].
7. End: Return answer = [4, 2, 4, 2, 3].

Proof of Correctness

The algorithm is correct because it strictly adheres to the definition of the problem using the LIFO (Last-In-First-Out) property of the stack.

• Invariant: The stack always contains indices k such that we have not yet found a j > k with prices[j] <= prices[k].
• Order: By iterating left-to-right, we ensure that for any index i currently being processed, it is to the right of all indices currently in the stack.
• First Occurrence: By popping from the stack immediately when the condition prices[i] <= prices[stack.top()] is met, we guarantee that prices[i] is the first valid discount found for stack.top(). Once popped, an index is never processed again, ensuring we don't overwrite the correct discount with a later, further one.

Pattern Reuse Notes

The Monotonic Stack pattern used in Final Prices With a Special Discount in a Shop is highly transferable. It is the optimal strategy for any problem requiring the "Next Greater" or "Next Smaller" element.

• LeetCode 402: Remove K Digits - Uses a monotonic stack to build the smallest number sequence.
• LeetCode 496: Next Greater Element I - The canonical version of this pattern; finds the next element strictly greater than the current one.
• LeetCode 503: Next Greater Element II - Applies the same pattern on a circular array.
• LeetCode 739: Daily Temperatures - Finds the distance to the next warmer day, which is structurally identical to finding the index of the Next Greater Element.

Reference Implementation

C++ Solution for LeetCode 1475

1class Solution {
2public:
3    vector<int> finalPrices(vector<int>& prices) {
4        vector<int> answer = prices;
5        stack<int> st; // Monotonic stack storing indices
6
7        for (int i = 0; i < prices.size(); ++i) {
8            // While stack is not empty and current price is a valid discount
9            // for the item at the top of the stack
10            while (!st.empty() && prices[i] <= prices[st.top()]) {
11                int idx = st.top();
12                st.pop();
13                // Apply discount
14                answer[idx] = prices[idx] - prices[i];
15            }
16            st.push(i);
17        }
18        
19        return answer;
20    }
21};

Java Solution for LeetCode 1475

1class Solution {
2    public int[] finalPrices(int[] prices) {
3        int n = prices.length;
4        int[] answer = prices.clone(); // Copy original prices
5        Deque<Integer> stack = new ArrayDeque<>(); // Use Deque as stack for indices
6
7        for (int i = 0; i < n; i++) {
8            // While stack is not empty and current price is <= price at stack top
9            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
10                int idx = stack.pop();
11                // Apply discount: original price - current price
12                answer[idx] = prices[idx] - prices[i];
13            }
14            stack.push(i);
15        }
16
17        return answer;
18    }
19}

Python Solution for LeetCode 1475

1class Solution:
2    def finalPrices(self, prices: List[int]) -> List[int]:
3        answer = prices[:] # Create a copy of prices
4        stack = [] # Stack to store indices
5
6        for i, price in enumerate(prices):
7            # While stack is not empty and we found a discount
8            while stack and price <= prices[stack[-1]]:
9                idx = stack.pop()
10                answer[idx] = prices[idx] - price
11            
12            stack.append(i)
13        
14        return answer