Leetcode Problem 1475. Final Prices With a Special Discount in a Shop

1475. Final Prices With a Special Discount in a Shop

Leetcode Solutions

Monotonic Stack Approach

  1. Initialize an empty stack and an array answer of the same length as prices to store the final prices.
  2. Iterate through the prices array from right to left.
  3. For each price, while the stack is not empty and the top of the stack is greater than the current price, pop from the stack.
  4. If the stack is not empty, the top of the stack is the discount for the current price. Subtract it from the current price and store the result in answer.
  5. If the stack is empty, there is no discount, and the current price is the final price. Store it in answer.
  6. Push the current price onto the stack.
  7. Return the answer array.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...