1475 - Final Prices With a Special Discount in a Shop (Easy)
Problem Link
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/
Problem Statement
Given the 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 array where the ith element 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 <= 5001 <= prices[i] <= 10^3
Approach 1: Stack
We first initialize the result list to be a copy of prices. The reason of choosing to copy prices is that it is convenient to not change anything if an item does not have a discount.
Then we initalize a stack and iterate prices. If the last element of the stack if greater than or equal to the current_price , we have found a discount for the last element of the stack. We calculate the discounted price, and put it in the result array (its index is stored as the second element). We pop that element from the stack.
We then add the new item to the stack with its value and its index.
def finalPrices(self, prices: List[int]) -> List[int]:
#initialize the result list to be a copy of prices
result = prices.copy()
#initialize stack
stack = []
#iterate prices
for i in range(len(prices)):
#declare current_price
current_price = prices[i]
#identify the prices that have not found a discount yet
while(stack and stack[-1][0] >= current_price):
#get the item's index
item_index = stack[-1][1]
#set its discounted price
result[item_index] = stack[-1][0] - current_price
#remove the item as it has found a discount
stack.pop()
#add the current item to the stack
stack.append([current_price, i])
#return result
return result