How do you solve Final Prices With a Special Discount in a Shop on LeetCode?

Final Prices With a Special Discount in a Shop (LeetCode #1475) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack can significantly reduce the time complexity from O(n²) to O(n).

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

The optimal solution for Final Prices With a Special Discount in a Shop runs in O(n) time and uses O(n) space. We traverse the prices list once, and each index is pushed and popped from the stack at most once, leading to O(n) complexity.

What is the brute force solution for Final Prices With a Special Discount in a Shop?

The brute force approach for Final Prices With a Special Discount in a Shop is Brute Force, with O(n²) time complexity and O(1) space complexity. We will check each item and look for the next item that has a price less than or equal to the current item's price. This is straightforward but can be slow for larger lists. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Final Prices With a Special Discount in a Shop?

Final Prices With a Special Discount in a Shop uses the following concepts: Array, Stack, Monotonic Stack. The recommended patterns to study are: Stack, Array.

What are the interview tips for Final Prices With a Special Discount in a Shop?

Always consider the brute force solution first to understand the problem. Think about how you can reduce the number of comparisons needed. Practice using stacks for problems that involve finding the next or previous elements.

What are common mistakes when solving Final Prices With a Special Discount in a Shop?

Not using a stack effectively, leading to unnecessary nested loops. Failing to handle edge cases where no discounts apply.

#1475

Final Prices With a Special Discount in a Shop

Easy

ArrayStackMonotonic StackStackArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

We can use a stack to keep track of the indices of the prices. This allows us to efficiently find the next smaller price for each item without needing a nested loop.

⚙️

Algorithm

6 steps

1Step 1: Initialize an empty stack and an answer list with the same values as prices.
2Step 2: Iterate through each price using its index.
3Step 3: While the stack is not empty and the current price is less than or equal to the price at the index stored at the top of the stack, pop the index from the stack.
4Step 4: For each popped index, set the answer at that index to the price minus the current price (this is the discount).
5Step 5: Push the current index onto the stack.
6Step 6: Return the answer list.

solution.py9 lines

1def finalPrices(prices):
2    stack = []
3    answer = prices[:]
4    for i in range(len(prices)):
5        while stack and prices[i] <= prices[stack[-1]]:
6            j = stack.pop()
7            answer[j] -= prices[i]
8        stack.append(i)
9    return answer

ℹ

Complexity note: We traverse the prices list once, and each index is pushed and popped from the stack at most once, leading to O(n) complexity.

1Using a stack can significantly reduce the time complexity from O(n²) to O(n).
2Understanding how to track indices with a stack is crucial for problems involving 'next' or 'previous' elements.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.