Final Prices With a Special Discount in a Shop Leetcode Solution

The problem Final Prices With a Special Discount in a Shop Leetcode Solution states that you are given an array of prices. There is a special condition that says that you get a special discount for each of the products. You get a discount of an equivalent amount of an element at jth index in the given array. Let’s say that the given array is prices. So you get a discount of prices[j] for prices[i] if j the minimum index such that j>=i and prices[j]<=prices[i]. But before going ahead with the solution, let us see a few examples.

[8,4,6,2,3]

[4,2,4,2,3]

Explanation: For the first element on the right that is less than or equal to itself is 4. So we subtract 4 from 8. Similarly, we perform the same operation for each of the remaining elements.

Approach for Final Prices With a Special Discount in a Shop Leetcode Solution

The problem Final Prices With a Special Discount in a Shop Leetcode Solution is simple. Because if one can observe that it is a slight modification over a very common and standard problem. The problem is a slight modification of next smaller element that is solved using a stack or queue. So, in this problem also, we will use a stack to find the next smaller or equal element to the current element.

So to solve the problem, we create a stack. And we push indices to the stack. Initially, 0 is pushed to the stack. Now we traverse over the elements in the array. We check if the current element is smaller or equal to the element that resides on the s.top() index. If the current element satisfies the previous condition then we pop the element and reduce the value at that index by the current value. Now push the current index. This way we find the next smaller or equal element.

Code for Final Prices With a Special Discount in a Shop Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

vector<int> finalPrices(vector<int>& prices) {
    stack<int> s;
    s.push(0);
    for(int i=1;i<prices.size();i++){
        while(!s.empty() && prices[s.top()] >= prices[i])prices[s.top()] -= prices[i], s.pop();
        s.push(i);
    }
    return prices;
}

int main() {
    vector<int> prices = {8,4,6,2,3};
    vector<int> output = finalPrices(prices);
    for(int i=0;i<output.size();i++)
        cout<<output[i]<<" ";
}

4 2 4 2 3

Java code

import java.util.*;
import java.io.*;

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

    public static void main(String[] args) {
        int[] prices = {8,4,6,2,3};
        int[] output = finalPrices(prices);
        for(int i=0;i<output.length;i++)
            System.out.print(output[i]+" ");
    }
}

4 2 4 2 3

Complexity Analysis

Time Complexity

O(N), since we traverse all the elements of the input.

Space Complexity

O(N),  we use a stack that used additional space.