Skip to content

1475. Final Prices With a Special Discount in a Shop

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

There is a special discount for 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.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

Input: prices = [10,1,1,6]
Output: [9,0,1,6]

Constraints:

  • 1 <= prices.length <= 500
  • 1 <= prices[i] <= 1000

Solution:

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] result = new int[n]; 

        Deque<Integer> stack = new ArrayDeque<>();


        for (int i = n - 1; i >= 0; i--){
            int cur = prices[i];
            if (i == n - 1){
                result[n - 1] = cur;
                stack.offerLast(cur);
                continue;
            }

            while (!stack.isEmpty()){
                int peek = stack.peekLast();
                if (peek > cur){
                    stack.pollLast();
                }else{
                    result[i] = cur - peek;
                    break;
                }
            }

            if (stack.isEmpty()){
                result[i] = cur;
            }
            stack.offerLast(cur);

        }

        return result;

        // 8 4 6 2 3 
        // i                  

                                    // stack: 3 2  4                    6 
        //           


        // 10, 1, 1 ,6 
        //  i

        // stack:  6  1 1 
    }
}

// TC: O(n)
// SC: O(n)