Final Prices With a Special Discount in a Shop Solution & Editorial - DSA Pattern

Final Prices With a Special Discount in a Shop Solution & Editorial - DSA Pattern | Thita.ai

0

n-1

python
# Pseudo-code for Brute Force
n = length(prices)
answer = copy(prices)
for i from 0 to n-1:
    for j from i+1 to n-1:
        if prices[j] <= prices[i]:
            answer[i] = prices[i] - prices[j]
            break
return answer

cpp
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> answer = prices;
        stack<int> st; // Monotonic stack storing indices

        for (int i = 0; i < prices.size(); ++i) {
            // While stack is not empty and current price is a valid discount
            // for the item at the top of the stack
            while (!st.empty() && prices[i] <= prices[st.top()]) {
                int idx = st.top();
                st.pop();
                // Apply discount
                answer[idx] = prices[idx] - prices[i];
            }
            st.push(i);
        }
        
        return answer;
    }
};

java
class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] answer = prices.clone(); // Copy original prices
        Deque<Integer> stack = new ArrayDeque<>(); // Use Deque as stack for indices

        for (int i = 0; i < n; i++) {
            // While stack is not empty and current price is <= price at stack top
            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
                int idx = stack.pop();
                // Apply discount: original price - current price
                answer[idx] = prices[idx] - prices[i];
            }
            stack.push(i);
        }

        return answer;
    }
}

python
class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        answer = prices[:] # Create a copy of prices
        stack = [] # Stack to store indices

        for i, price in enumerate(prices):
            # While stack is not empty and we found a discount
            while stack and price <= prices[stack[-1]]:
                idx = stack.pop()
                answer[idx] = prices[idx] - price
            
            stack.append(i)
        
        return answer

AI Coach Insight

Focus on the core pattern. For Final Prices With a Special Discount in a Shop, identifying the Stack Patterns is key to optimizing your solution.

Complexity Analysis

Time Complexity: $O(N)$
- We iterate through the prices array once.
- Each index is pushed onto the stack exactly once.
- Each index is popped from the stack at most once.
- Therefore, the total number of operations is proportional to $N$ .
Space Complexity: $O(N)$
- In the worst case (a strictly increasing array), the stack will store all $N$ indices simultaneously.
- We also use $O(N)$ space for the output array, which is required by the problem.

Related Patterns

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.

Common Mistakes & FAQ

Q: Why do I get the wrong answer when I store values in the stack instead of indices?

Mistake: Storing prices[i] in the stack instead of i.
Why: If you only store the price, you lose the information about where that price was located in the original array. When you find a discount, you need to know which index in the answer array to update.
Consequence: You cannot update the correct element in the result array, leading to incorrect output.

Q: Why are some items in my output 0 or incorrect?

Mistake: Initializing the answer array with zeros and only updating it when a discount is found.
Why: The problem states that if no discount is found, the final price is the original price.
Consequence: Items that never find a discount will remain 0 (or uninitialized) instead of retaining their original price. Always initialize answer as a copy of .

prices

Editorial: Final Prices With a Special Discount in a Shop

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

Problem Overview

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

Want to master more patterns?

Core Insight for Final Prices With a Special Discount in a Shop

Execution Flow

Proof of Correctness

Reference Implementation

C++ Solution for LeetCode 1475

Java Solution for LeetCode 1475

Python Solution for LeetCode 1475

AI Coach Insight

Complexity Analysis

Related Patterns

Common Mistakes & FAQ