LeetCode Entry

1475. Final Prices With a Special Discount in a Shop

18.12.2024 easy 2024 kotlin rust

Subtract next smaller value stack

1475. Final Prices With a Special Discount in a Shop easy blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/836

Problem TLDR

Subtract next smaller value #easy #monotonic_stack

Intuition

Brute force works. The next thing to try is a monotonic stack: iterate from the end, always keep values lower or equal than the current.

The big brain solution is to iterate forward: pop values lower than the current and adjust result at its index with the current value discount.

Approach

  • let’s implement all of them
  • we can do it in-place if needed

Complexity

  • Time complexity: \(O(n^2)\) or O(n)

  • Space complexity: \(O(n)\) or O(1) for brute-force in-place

Code


    fun finalPrices(prices: IntArray) = IntArray(prices.size) { i ->
        prices[i] - (prices.slice(i + 1..<prices.size)
                       .firstOrNull { it <= prices[i] } ?: 0)
    }



    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let (mut s, mut r) = (vec![], vec![0; prices.len()]);
        for i in (0..prices.len()).rev() {
            while s.last().map_or(false, |&x| x > prices[i]) { s.pop(); }
            r[i] = prices[i] - s.last().unwrap_or(&0);
            s.push(prices[i])
        }; r
    }



    vector<int> finalPrices(vector<int>& p) {
        vector<int> s;
        for (int i = 0; i < p.size(); ++i) {
            while (s.size() && p[s.back()] >= p[i]) {
                p[s.back()] -= p[i]; s.pop_back();
            }
            s.push_back(i);
        } return p;
    }