1475. Final Prices With a Special Discount in a Shop

EasyView on LeetCode

Array Stack Monotonic Stack

Time: O(n)

Space: O(n)

Intuition

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

Algorithm

1Monotone stack (decreasing). Process prices left to right.
2When processing price[i]: pop stack while stack top > price[i] and top index within i-k range.
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

// 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?