Final Prices With A Special Discount In A Shop - Leetcode Solution

Problem:

Given an array of integers prices, where prices[i] is the price of a given product i in a shop. There is a special discount for products in the shop, if you buy the product i, 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 array where the ith element is the final price you will pay for the ith product of the shop considering the special discount.

Example:

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

Solution:

To solve this problem we need to loop through the given array prices from left to right. For each element prices[i] we need to find the smallest index j such that prices[j] <= prices[i] and j > i. If we find such index j then the discount for prices[i] is prices[j] and the final price we will pay for prices[i] is prices[i] - prices[j]. Otherwise, there is no discount for prices[i] and the final price we will pay for prices[i] is prices[i].

We can achieve this by using a stack. We will push the index i of each element prices[i] to the stack. If we encounter an element prices[j] such that prices[j] <= prices[i] for some i, then we will pop all the elements from the stack until we find the closest element prices[k] such that k > j and prices[k] <= prices[j] or the stack becomes empty. The discount for each popped element is prices[j] and the final price we will pay for each popped element is prices[i] - prices[j]. We will repeat this process until we have processed all the elements in the input array.

The time complexity of this solution is O(n) because each element is pushed to the stack once and popped from the stack at most once.

Here is the implementation of the solution in Python:

class Solution: def finalPrices(self, prices: List[int]) -> List[int]: stack = [] for i in range(len(prices)): while stack and prices[stack[-1]] >= prices[i]: j = stack.pop() prices[j] = prices[j] - prices[i] stack.append(i) return prices

I hope this explanation helps!

1