Final Prices With a Special Discount in a Shop

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount on items in the shop if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.

Example:

Input:  prices={8,4,6,2,3}
Output: special={4,2,4,2,3}

Approach

Java

import java.util.Arrays;
import java.util.Stack;
public class FinalPricesSpecialDiscount {
    public static void main(String[] args) {
        int prices[] = { 8, 4, 6, 2, 3 };
        int special[] = finalPrices(prices);
        System.out.println(Arrays.toString(special));
    }
    // function to find the final
    // price after discount
    static int[] finalPrices(int[] prices) {
        Stack<Integer> st = new Stack<Integer>();
        int n = prices.length;
        if (n == 0)
            return prices;
        // push last into the stack
        st.push(prices[n - 1]);
        // iterate till we reah to 0
        for (int i = n - 2; i >= 0; i--) {
            // while stack is not empty and st top is
            // greater then current price then pop
            while (!st.isEmpty() && st.peek() > prices[i])
                st.pop();
                // if stack is not empty then update new price
                // and push into the stack
                if (!st.isEmpty()) {
                    int x = st.peek();
                    st.push(prices[i]);
                    prices[i] = prices[i] - x;
                }
                // else push into the stack without discount
                else
                    st.push(prices[i]);
        }
        return prices;
    }
}

C++

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

//function to find the final
//price after dicount 
vector<int> finalPrices(vector<int>& prices) 
{
       stack<int> st;
       int n=prices.size();
       if(n==0)
             return prices;
      //push last into the stack
      st.push(prices[n-1]);
     //iterate till we reah to 0
      for(int i=n-2;i>=0;i--)
      {
          //while stack is not empty and st top is
          //greater then current price then pop
          while(!st.empty()&&st.top()>prices[i])
                 st.pop();
          //if stack is not empty then update new price
          //and push into the stack
         if(!st.empty())
         {
             int x=st.top();
             st.push(prices[i]);
             prices[i]=prices[i]-x;
         }
         //else push into the stack without discount
          else
               st.push(prices[i]);
         
      }
    return prices;
}
int main()
{
   vector<int> prices ={8,4,6,2,3};
   vector<int> special=finalPrices(prices);
   for(int i=0;i<special.size();i++)
      cout<<special[i]<<" ";
   return 0;
}