Final Prices With a Special Discount in a Shop

This problem involves iterating over the prices and for each price, finding out if there is a lower or equal price on its right, and if so, subtracting that from the current price. If no such price is found, we keep the original price.

This approach sounds like a Stack problem, where we can store the indexes of the prices on the stack. If the current price is less than or equal to the price at the top of the stack, we calculate the discounted price and pop that price index off the stack. We then add the current price’s index to the stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # Step 1: Initialize the stack
        stack = []

        # Step 2: Iterate over prices
        for i in range(len(prices)):
            # Step 3: While stack is not empty and current price is less than or equal to price at top of stack
            while stack and prices[i] <= prices[stack[-1]]:
                # Calculate the discounted price and update the price at the top of stack
                prices[stack[-1]] -= prices[i]
                # Pop the top of stack
                stack.pop()

            # Step 4: Add the current price's index to the stack
            stack.append(i)

        # Step 5: Return the final prices after discounts
        return prices

In the code, we first initialize an empty stack. Then we iterate over the prices. If the current price is less than or equal to the price at the top of the stack, we calculate the discounted price and update the price at that index. We then pop the index off the stack. If no such price is found or after updating, we add the current price’s index to the stack. Finally, we return the updated prices list which now contains the final prices after applying the discounts.

Identifying Problem Isomorphism

“Final Prices With a Special Discount in a Shop” can be mapped to “Daily Temperatures”.

Reasoning:

Both involve iterating over an array and finding the next element that satisfies a certain condition. In “Daily Temperatures”, the task is to find the next warmer temperature, while in “Final Prices With a Special Discount in a Shop”, the task is to find the next price that is smaller or equal.

Both can be solved using a stack to keep track of the elements we have seen so far. In “Daily Temperatures”, we use the stack to store indices of the temperatures, while in “Final Prices With a Special Discount in a Shop”, we use the stack to store indices of the prices. In both problems, the top of the stack always represents the next element that satisfies the condition for the elements below it in the stack.

“Daily Temperatures” is simpler than “Final Prices With a Special Discount in a Shop” because it only requires finding the next greater element. The second one requires finding the next smaller or equal element and performing an additional subtraction operation.

Tidbits

Similar to the problem 503. Next Greater Element II

Abstract Representation of the Problem

We are given a sequence of integers, where each integer signifies a specific value. This sequence also has an associated rule that applies a modification to these values. The rule is: for each integer in the sequence (from left to right), look at the subsequent integers in the sequence and find the first integer that is less than or equal to the current one. The value of this found integer is then subtracted from the current integer. If no such integer is found, the current integer remains unchanged.

The problem task is to apply this rule to the entire sequence and return the modified sequence.

Q&A

How does one think of a solution like this during an interview?

Understand the Problem: You are given a list of prices. For each price, you need to find the next smallest or equal price in the list and subtract it from the current price. If there is no such price, the price remains the same. Your task is to return a new list with these discounted prices.
Problem Decomposition: You realize that you need to traverse the list of prices. For each price, you need to find the next price in the list that is smaller than or equal to the current price. This forms two sub-problems: traversing the list and finding the next suitable price.
Brute Force Approach: You first think of a simple solution. For each price, traverse all the following prices and find the first price that is smaller or equal. Subtract this price from the current price to get the discounted price. If no such price is found, the price remains the same. However, this would involve a lot of repeated steps and is not very efficient.
Optimization: You realize that you can optimize the above approach by keeping track of the previous prices in a stack. For each price, while it’s less than or equal to the top of the stack, you pop elements from the stack and update those prices in the result list. Then, you push the current price to the stack. This way, you can find the next smallest or equal price for each element in a single pass, making your solution more efficient.
Code and Explain: Now you can start coding your solution in Python. Explain your code to the interviewer as you write it, making sure to highlight how it solves the problem and any particular parts that address the sub-problems you identified earlier.
Testing: Finally, test your code with various test cases to ensure it works as expected. Consider edge cases such as when the list of prices has only one price, when all the prices are the same, and when prices are in descending order. After you have tested these edge cases, test your code with random test cases.

Think out loud and communicate your thought process to the interviewer throughout this process. This will help the interviewer understand how you approach problems and how you come up with solutions.

Just one question how does you thought of implementing this question with stack ? I mean I really couldn’t understand how does it came to your mind. Is there any relevant pattern for using stack in these type of questions.

The choice to use a stack in this problem, and similar ones, comes from recognizing a pattern known as the “Next Greater Element” pattern. In this type of problem, you need to find the next element in an array that satisfies a specific condition compared to the current element.

A stack is particularly suited to this kind of task because it operates on a “Last-In-First-Out” (LIFO) principle. You can think of it as stacking books on a table. The last book you place is the first one you’ll remove. This property is helpful when you’re iterating through an array and want to compare the current element with the previous ones.

You can push elements onto the stack until you find an element that satisfies the condition (e.g., it’s larger than or equal to the top element of the stack). At that point, you can start popping elements from the stack. This process guarantees that for each element, you efficiently find the next element that meets the condition.

In the “Final Prices With a Special Discount in a Shop” problem, the condition is finding the next smaller or equal price. Hence, the stack can keep track of prices, and when a price is found that’s smaller or equal to the top of the stack, discounts can be applied.

Recognizing such patterns comes with practice. The more problems you solve, the better you’ll get at identifying these patterns and knowing which data structures to use.

Keyword is “backreference”. When you need to backreference, consider using a stack. For this problem, when you encounter a new price, you need to backreference previous prices to see if current price could be the discount of them. And stack is a good data structure to keep track of previous values.

That’s correct! “Backreference” is indeed a keyword that suggests the usage of stack data structure. When solving a problem requires you to refer back to previous values and there’s no need to access elements in between, a stack becomes a viable choice.

In this problem, we’re examining prices backwards, from the current price to previous ones, checking if the current price is lower or equal to the previous ones. We don’t need to refer to prices in between. So a stack, with its LIFO (Last In, First Out) characteristic, fits perfectly.

When a lower or equal price is encountered, it can serve as a discount for all the higher prices in the stack, hence we pop those out of the stack. The current price is then pushed onto the stack.

In conclusion, recognizing keywords like “backreference” and understanding what kind of data structures are usually associated with these keywords is very helpful in problem-solving.

Final Prices With a Special Discount in a Shop

Identifying Problem Isomorphism

Tidbits

Abstract Representation of the Problem

Similar Problems

Q&A