We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Final Prices With a Special Discount in a Shop

Number: 1570

Difficulty: Easy

Paid? No

Companies: Google, Meta, Dream11

Problem Description

Given an array of integers representing prices of items in a shop, for each item, find the next item in the list (with a greater index) that has a price less than or equal to the current price and subtract that price as a discount. If no such item exists, the original price is paid. Return an array containing the final prices for all items after applying the discount.

Key Insights

  • A brute-force approach would check each subsequent item for every index which can be inefficient.
  • Using a monotonic stack helps in efficiently finding the next smaller or equal price for each item.
  • Traverse the array once, while maintaining a stack of indices where the discount has not yet been applied.
  • When a price qualifies as the discount for the items stored in the stack, update those items.

Space and Time Complexity

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once. Space Complexity: O(n) - In the worst-case scenario, all elements are stored in the stack.

Solution

The solution uses a monotonic stack to track the indices of prices that have not yet found their discount. As we iterate over the prices:

  1. Check if the current price can act as a discount for any previously seen elements (stored in the stack) by comparing it with the price at the index on the top of the stack.
  2. If the current price is less than or equal to the price at the top of the stack, it qualifies as a discount; subtract it from that price and pop that index from the stack.
  3. Push the current index onto the stack. Once the iteration is complete, any index left in the stack did not encounter a valid discount and remains at its original price.

Code Solutions

# Python solution using a monotonic stack.

def finalPrices(prices):
    # Stack to store the indices of prices which are waiting for a discount.
    stack = []
    # Iterate over each price by its index.
    for i, price in enumerate(prices):
        # While there are indices in stack and the current price qualifies as a discount 
        while stack and prices[stack[-1]] >= price:
            # Pop index from the stack; current price is the discount for that price.
            index = stack.pop()
            prices[index] -= price   # Update the price at that index by applying the discount.
        # Push the current index onto the stack.
        stack.append(i)
    return prices

# Example usage:
# print(finalPrices([8,4,6,2,3])) would output [4,2,4,2,3].
← Back to All Questions