algoadvance

You have an array of prices where prices[i] is the price of the i-th item in a shop. There is a special discount for items in the shop: if you buy the i-th item, then you will receive a discount equivalent to the price of the next item that is cheaper or equal than the i-th item. If there isn’t an item that meets this criterion, you won’t get any discount for the i-th item.

Return an array where the i-th element is the price you need to pay for the i-th item after a suitable discount.

Example:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]

Constraints:

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 10^3

Clarifying Questions

1. Can prices have duplicate values?
   • Yes, prices can have duplicate values.
2. What should be done if there is no item cheaper than the current one?
   • In that case, the price remains unchanged.
3. What should be returned if the array is empty?
   • We can return an empty list as the result.

Strategy

To solve this problem efficiently:

1. Iterate through the prices list: For each price, look ahead in the list to find the first price that is less than or equal to the current price.
2. Apply the discount: Once such a price is found, subtract it from the current price.
3. Use a stack to help identify the first next lower price more efficiently.
   • Store indices in the stack while processing items from left to right.
   • For each new price, pop from the stack until the stack is empty or the price at the top of the stack is less than or equal to the current price.
   • Update the result accordingly.

Code

def finalPrices(prices):
    n = len(prices)
    result = [0] * n
    stack = []
    
    for i in range(n):
        while stack and prices[stack[-1]] >= prices[i]:
            result[stack.pop()] = prices[stack[-1]] - prices[i]
        stack.append(i)
        
    while stack:
        result[stack.pop()] = prices[stack[-1]]
    
    return result

# Example usage:
prices = [8, 4, 6, 2, 3]
print(finalPrices(prices))  # Output: [4, 2, 4, 2, 3]

Time Complexity

• The time complexity of this solution is O(n) where n is the length of the prices array.
  • Each element is pushed and popped from the stack exactly once.
• The space complexity is also O(n) due to the usage of an additional stack to keep track of the indices.

This approach ensures that we efficiently find the next lower price for each item with a linear scan through the list, providing a significant improvement over a naive O(n^2) approach.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?