Leetcode – Final Prices With a Special Discount in a Shop Solution

Spread the love

The Final Prices With a Special Discount in a Shop problem is a classic problem often encountered on Leetcode and similar competitive coding platforms. This problem tests your understanding of arrays and how to manipulate them efficiently.

Problem Statement

Before diving into the solution, let’s first understand the problem statement:

Given an array prices where prices[i] is the price of a given item in the ith day, you want to find the final prices considering the special discount for each item.

The special discount for items in the shop is described as follows:

  1. For any item, if you buy it on the ith day, you can get a discount of prices[j] where j > i and prices[j] <= prices[i].
  2. If multiple such j exist, consider the minimum such j.

Return an array ans where ans[i] is the final price of the item in ith day after considering the special discount.

Example:

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

Solution Overview

To solve this problem, we can use a stack to keep track of the elements for which we haven’t found a smaller or equal element yet.

  1. Initialize an empty stack and iterate through the array.
  2. For each element, check if the stack is empty:
    • If it is not, pop elements from the stack as long as they are greater than the current element and update their corresponding value in the answer array with the discounted price.
  3. Push the current element index onto the stack.

Implementation in Python

Let’s implement this solution in Python:

def finalPrices(prices):
    stack = []
    ans = prices.copy()

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            last = stack.pop()
            ans[last] = prices[last] - price
        stack.append(i)

    return ans

# Test the function
prices = [8, 4, 6, 2, 3]
print(finalPrices(prices))  # Output should be [4, 2, 4, 2, 3]

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the prices array. This is because we are iterating through the array once, and each element is pushed and popped from the stack exactly once.

Space Complexity

The space complexity is also O(n) because we are storing the indices of elements in a stack and making a copy of the original array for the answer.

Why Use a Stack?

The stack is particularly useful here because it allows us to keep track of elements for which we have not yet found a smaller or equal element. As we iterate through the array, we can efficiently determine which elements are greater than or equal to the current element by looking at the top of the stack. This enables us to update multiple elements in a single iteration, thereby reducing the time complexity to O(n).

Edge Cases

Always consider edge cases when solving problems like this:

  1. Empty array: If the array is empty, the function should return an empty array.
  2. Array with one element: If there is only one item, its discounted price will be the same as its original price.
# Edge Cases
print(finalPrices([]))  # Output should be []
print(finalPrices([10]))  # Output should be [10]

Conclusion

The Final Prices With a Special Discount in a Shop problem is an interesting array manipulation problem that can be efficiently solved using a stack. We learned how to implement the solution in Python and analyzed its time and space complexity. The stack data structure was key to achieving an optimal solution, and we also discussed edge cases to ensure the solution is robust.

Leave a Reply