LeetCode 1475 - Final Prices With a Special Discount in a Shop

The problem presents a scenario where you are buying items in a shop, each with a given price stored in an array prices.

leetcodeeasyarraystackmonotonic-stack

LeetCode Problem 1475

Difficulty: šŸŸ¢ Easy
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem presents a scenario where you are buying items in a shop, each with a given price stored in an array prices. For each item at index i, there may exist a discount based on the next item j (where j > i) such that prices[j] <= prices[i]. If such a j exists, the discount is equal to prices[j]; otherwise, no discount is applied. Your task is to compute the final price for each item after applying this discount, returning the results in an array of the same length as the input.

The input is a list of integers with length between 1 and 500, and each integer ranges from 1 to 1000. These constraints imply that the array is relatively small, so even an O(nĀ²) brute-force solution could work in practice, but an optimal approach using a monotonic stack can reduce time complexity to O(n).

Important edge cases include: arrays of length 1 where no discount can be applied, strictly increasing arrays where no discount ever applies, and arrays where multiple consecutive discounts are possible.

Approaches

The brute-force approach is straightforward: for each price at index i, you iterate over all subsequent prices to find the first price prices[j] that is less than or equal to prices[i]. Once found, subtract it from prices[i] to get the final price. While correct, this approach has a time complexity of O(nĀ²) because each element may require scanning through all remaining elements.

The optimal approach uses a monotonic stack. The key insight is that we can maintain a stack of indices in decreasing order of prices. As we traverse the array, if the current price is less than or equal to the price at the index on the top of the stack, we pop from the stack and apply the discount to that index. This ensures that for each item, the discount is applied from the first future price that is smaller or equal, achieving O(n) time complexity because each element is pushed and popped at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(1) Check every future element for each item
Optimal O(n) O(n) Use a monotonic stack to track indices needing discounts

Algorithm Walkthrough

  1. Initialize an empty stack to hold indices of items whose discount has not been determined yet.
  2. Traverse the prices array from left to right.
  3. For each current index i:

a. While the stack is not empty and the current price prices[i] is less than or equal to prices[stack[-1]], pop the index from the stack.

b. For the popped index, set the final price as prices[popped_index] - prices[i]. 4. Push the current index i onto the stack, since it may serve as a discount for future prices. 5. After the traversal, any indices remaining in the stack did not find a discount. Their final price remains equal to the original price. 6. Return the resulting array of final prices.

Why it works: The stack always maintains indices of prices in decreasing order. When a smaller or equal price is encountered, it correctly identifies the first eligible discount for each prior item, guaranteeing the correct application of the problem's discount rule.

Python Solution

from typing import List

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        final_prices = prices.copy()
        stack = []

        for i, price in enumerate(prices):
            while stack and price <= prices[stack[-1]]:
                idx = stack.pop()
                final_prices[idx] -= price
            stack.append(i)

        return final_prices

In this implementation, final_prices is initialized as a copy of prices to store the results. The stack stores indices whose discount is pending. The while loop applies the discount to all prior prices that are greater than or equal to the current price. The index i is then added to the stack for future processing. This ensures that each price receives at most one discount from the first subsequent eligible price.

Go Solution

func finalPrices(prices []int) []int {
    n := len(prices)
    finalPrices := make([]int, n)
    copy(finalPrices, prices)
    stack := []int{}

    for i, price := range prices {
        for len(stack) > 0 && price <= prices[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            finalPrices[idx] -= price
        }
        stack = append(stack, i)
    }

    return finalPrices
}

In Go, slices are used to replicate the stack behavior, and copy ensures finalPrices begins as a copy of prices. The loop logic mirrors the Python version, maintaining the stack of indices and applying discounts when a smaller or equal price is encountered.

Worked Examples

Example 1: prices = [8,4,6,2,3]

i price stack before action stack after final_prices
0 8 [] push 0 [0] [8,4,6,2,3]
1 4 [0] 4 <= 8 ā†’ pop 0, final_prices[0]=8-4=4 [1] [4,4,6,2,3]
2 6 [1] 6 > 4 ā†’ push 2 [1,2] [4,4,6,2,3]
3 2 [1,2] 2 <= 6 ā†’ pop 2, final_prices[2]=6-2=4; 2 <=4 ā†’ pop 1, final_prices[1]=4-2=2 [3] [4,2,4,2,3]
4 3 [3] 3 > 2 ā†’ push 4 [3,4] [4,2,4,2,3]

Example 2: prices = [1,2,3,4,5]

All prices are increasing. The stack accumulates indices, no discount ever applies, final_prices = [1,2,3,4,5].

Example 3: prices = [10,1,1,6]

i price stack before action stack after final_prices
0 10 [] push 0 [0] [10,1,1,6]
1 1 [0] 1 <= 10 ā†’ pop 0, final_prices[0]=10-1=9 [1] [9,1,1,6]
2 1 [1] 1 <= 1 ā†’ pop 1, final_prices[1]=1-1=0 [2] [9,0,1,6]
3 6 [2] 6 >1 ā†’ push 3 [2,3] [9,0,1,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is pushed and popped at most once in the stack
Space O(n) The stack may store all indices in the worst case

The algorithm is linear in time because the stack ensures each element is processed only twice, and space is proportional to the input size due to the stack and the copy of the prices array.

Test Cases

# Provided examples
assert Solution().finalPrices([8,4,6,2,3]) == [4,2,4,2,3]  # mixed discounts
assert Solution().finalPrices([1,2,3,4,5]) == [1,2,3,4,5]  # strictly increasing
assert Solution().finalPrices([10,1,1,6]) == [9,0,1,6]     # repeated small prices

# Edge cases
assert Solution().finalPrices([5]) == [5]                  # single element
assert Solution().finalPrices([3,3,3,3]) == [0,0,0,3]     # all equal prices
assert Solution().finalPrices([5,4,3,2,1]) == [1,1,1,1,1] # strictly decreasing
assert Solution().finalPrices([2,2,1,2]) == [0,1,1,2]     # mixed equal and smaller
Test Why
[8,4,6,2,3] Validates proper discount application with multiple next smaller prices
[1,2,3,4,5] Tests no discount case
[10,1,1,6] Handles repeated small discounts correctly
[5] Single-element array, edge case
[3,3,3,3] Equal prices, multiple discounts in sequence
[5,4,3,2,1] Strictly decreasing prices, maximum discount scenario
[2,2,1,2] Mixed equal and smaller prices, ensures stack