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

Master LeetCode problem 1475 (Final Prices With a Special Discount in a Shop), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1475. Final Prices With a Special Discount in a Shop

Easy

Array Stack Monotonic Stack

Problem Explanation

Explanation:

We can solve this problem using a stack data structure to keep track of the indices of prices where we have not found a greater or equal price yet.
We iterate through each price in the array. If the current price is less than the price at the top of the stack, we calculate the discount and update the final price for the top of the stack.
If the current price is greater than or equal to the price at the top of the stack, we continue to pop items from the stack and update their final prices until we find a price greater than the current price.
Finally, we return the array containing the final prices. :

Solution Code

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = prices[idx] - prices[i];
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            ans[stack.pop()] = prices[i];
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1475 (Final Prices With a Special Discount in a Shop)?

This page provides optimized solutions for LeetCode problem 1475 (Final Prices With a Special Discount in a Shop) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1475 (Final Prices With a Special Discount in a Shop)?

The time complexity for LeetCode 1475 (Final Prices With a Special Discount in a Shop) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1475 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1475 in Java, C++, or Python.

Back to LeetCode Solutions