Problem

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.

Examples

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

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

Given an array prices where prices[i] represents the price of the ith item in a shop, we need to compute the final prices after applying a special discount. The special discount for the ith item is the smallest price found in the subsequent items that is less than or equal to prices[i]. If no such price exists, the item won’t have any discount.

Approach

  1. Create an empty list ans of the same length as prices.
  2. Iterate through each price in the prices array.
  3. For each price, look for the smallest price in the items that follow it that is less than or equal to it.
  4. If such a price is found, subtract that price from the current item price; otherwise, the price remains unchanged.
  5. Store the final price calculation in ans.
  6. Return the list ans.

Code

Java
public class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int discount = 0;
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    discount = prices[j];
                    break;
                }
            }
            ans[i] = prices[i] - discount;
        }
        return ans;
    }
}
Python
class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n: int = len(prices)
        ans: List[int] = [0] * n
        for i in range(n):
            discount: int = 0
            for j in range(i + 1, n):
                if prices[j] <= prices[i]:
                    discount = prices[j]
                    break
            ans[i] = prices[i] - discount
        return ans

Complexity

  • ⏰ Time complexity: O(n^2) where n is the length of the prices array. This results from the nested iteration where for each item, we potentially scan through the remaining items.
  • 🧺 Space complexity: O(n) for the output list ans.

Method 2 - Using monotonic increasing stack

The problem appears straightforward at first glance, but finding an optimal solution requires a deeper understanding. Now, for each element we want to get the next smallest or equal element on the right, which we will act as discount. We have seen similar problems like Next Greater Element 2 .

Now, we have to determine the most recent element on the right-hand side of the current element that is smaller than or equal to the current element. The key is not the position of the element used as a discount but its value and how recently it appeared in the process. Given that the element’s “recentness” is crucial, a stack is the most suitable data structure for this scenario. Let’s proceed with a stack-based algorithm.

Now, when is not possible to get the discount? It is when all the elements on the right in the array are larger than this element. So, how about we use monotonic increasing stack. And as soon as we find the price less than price in stack, we know we are in for the discount. So, we can pop out all the elements till we can apply those discount. Also, to apply discount we need to know the index at which we are applying the discount in answer, so we will be storing indices in stack and not the actual value.

Approach

  1. Clone the prices array as the original price before applying any discount.
  2. Use a stack to maintain the indices of strictly increasing prices. This way for current index, we will know the previous prices that are less than current price
  3. Use a stack to hold indices of previous prices that are greater than the current price, and keep popping out prices that are not less than the current price, applying the current price as a discount to previous prices.

Dry Run

Lets dry run for prices = [8,4,6,2,3]

Initial stack:
stk = [], ans = [8,4,6,2,3]
Iterations
We see 8

First element is 8 and stack is empty, so, we will just add its index to stack.

stk = | 0 |
We see 4

Then, we get 4, which is less then element in the stack, so we pop out and 8’s index and apply the discount:

stk = []
ans[0] = 8 - 4 = 4

And, now we can 4’s index on stack:

stk = | 1 |
We see 6

As 6 > 4, we can’t get any discount, so we push 6’s index to stack:

stk = | 2 |
      | 1 |
We see 2

Now, 2 < 6 ⇨ we pop out 6’s index and give discount. So,

stk = | 1 |, ans[2] = 6 - 2 = 4

Then, 2 < 4 as well, so we pop out 4’s index and give discount:

stk = [], ans[1] = 4 - 2 = 2

Now, we push 2’s index on stack:

stk = | 3 |
We see 3

As 3 > 2, we push its index on stack as well.

stk = | 4 |
      | 3 |
Final

Now, we are done with all the elements in stack, so we return the answer.

ans = [4,2,4,2,3]

Code

Java
public class Solution {
    public int[] finalPrices(int[] prices) {
        int[] ans = prices.clone();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                ans[stack.pop()] -= prices[i];
            }
            stack.push(i);
        }

        return ans;
    }
}
Python
class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        ans: List[int] = prices[:]
        stack: List[int] = []

        for i in range(len(prices)):
            while stack and prices[stack[-1]] >= prices[i]:
                ans[stack.pop()] -= prices[i]
            stack.append(i)

        return ans

Complexity

  • ⏰ Time complexity: O(n) because each element is pushed and popped from the stack at most once.
  • 🧺 Space complexity: O(n) for the stack storing the indices and the ans array.