DDSA Solutions

1475. Final Prices With a Special Discount in a Shop

EasyView on LeetCode
ArrayStackMonotonic Stack
Time: O(n)
Space: O(n)

Problem Overview

For each price, find the nearest smaller price within the next k products.

Intuition

For each price, find the nearest smaller price within the next k products. Monotone stack.

Algorithm

  1. 1Monotone stack (decreasing). Process prices left to right.
  2. 2When processing price[i]: pop stack while stack top > price[i] and top index within i-k range.
  3. 3final_prices[stack.top] = price[i] (discount). Push i.

Common Pitfalls

  • •Stack front elements are candidate discounts. Check that the discount is within k distance.
1475.cs
C#
// Approach: Monotone stack; for each price pop all stack elements whose price is >= current price and apply the discount.
// Time: O(n) Space: O(n)

public class Solution
{
    public int[] FinalPrices(int[] prices)
    {
        int[] ans = (int[])prices.Clone();
        Stack<int> stack = new Stack<int>();

        for (int j = 0; j < prices.Length; ++j)
        {
            while (stack.Count > 0 && prices[j] <= prices[stack.Peek()])
                ans[stack.Pop()] -= prices[j];
            stack.Push(j);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems