#1475

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Final Prices With a Special Discount in a Shop

Calculate final prices with discounts applied in a shop using a stack-based state management approach to find the correct price for each item.

array stack monotonic stack

Problem Statement

You are given an integer array prices where prices[i] is the price of the ith item in a shop. The goal is to calculate the final price for each item after applying a special discount. If you buy an item at index i, you will receive a discount equivalent to prices[j], where j is the smallest index greater than i such that prices[j] <= prices[i]. If no such j exists, no discount is applied.

Return an array of the same length where each element represents the final price after the discount. The problem requires an efficient solution using a stack to track potential discounts and compute the final prices in linear time.

Examples

Example 1

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

Output: [4,2,4,2,3]

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]

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]

Example details omitted.

Constraints

1 <= prices.length <= 500
1 <= prices[i] <= 1000

Solution Approach

Use of Stack for Efficient Discount Calculation

To solve this problem efficiently, use a stack to keep track of the indices of items in the array while iterating through them. The stack will allow for efficient retrieval of the closest index j with prices[j] <= prices[i], enabling quick discount application.

Monotonic Stack Property

The stack needs to maintain a monotonic order, meaning it holds indices of items in descending price order. This ensures that when we encounter a new price, we can quickly find the next item with a lower price for discounting. If no such item exists, no discount is applied.

Linear Time Complexity

By processing the array in a single pass and using the stack to manage state, the time complexity of this solution is O(n), where n is the length of the prices array. This ensures the solution is efficient even for the upper input limit.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of O(n) arises from the fact that each item is pushed and popped from the stack at most once. Thus, the algorithm processes the prices array in linear time. The space complexity is also O(n) due to the stack storing indices of the items as we traverse the array.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of stack-based state management to handle the discount logic.
Look for candidates who implement a monotonic stack to ensure the efficient calculation of discounts in linear time.
Be aware of how well candidates can explain time and space complexity, particularly in terms of how the stack helps optimize the solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting to pop elements from the stack when the price condition is met, which can result in incorrect discount calculations.
Not ensuring the stack maintains a monotonic order, leading to inefficient or incorrect solutions.
Failing to handle edge cases, such as when there are no discounts available for any items.

Follow-up variants

Modify the problem to apply discounts in reverse order (from last item to first), requiring a different stack management approach.
Change the problem so that discounts are applied based on a percentage rather than a fixed price, requiring adjustments to how discounts are calculated.
Introduce a scenario where discounts are limited to a certain number of items, requiring additional state management beyond a simple stack.

FAQ

How does a monotonic stack help solve the Final Prices With a Special Discount in a Shop problem?

A monotonic stack helps by maintaining an ordered sequence of indices that allows for efficient discount calculation, as we can quickly find the next smaller price to apply a discount.

What is the time complexity of the Final Prices With a Special Discount in a Shop problem?

The time complexity is O(n), as each item in the prices array is pushed and popped from the stack at most once, ensuring a linear time solution.

Can I solve the Final Prices With a Special Discount in a Shop problem using brute force?

Yes, brute force can be used by checking each item and searching for the next smaller price, but it would result in a time complexity of O(n^2), which is inefficient for large arrays.

What is the space complexity of the solution to the Final Prices With a Special Discount in a Shop problem?

The space complexity is O(n) due to the stack storing indices of the items as we traverse the prices array.

What are the potential pitfalls when solving the Final Prices With a Special Discount in a Shop problem?

Common pitfalls include forgetting to pop items from the stack correctly, not maintaining the stack's monotonic order, and not handling edge cases like when no discounts apply.

terminal

Solution

Solution 1: Monotonic Stack

The problem is essentially to find the first element on the right side that is smaller than each element. We can use a monotonic stack to solve this.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#1504 count submatrices with all ones #1526 minimum number of increments on subarrays to form a target array #1574 shortest subarray to be removed to make array sorted