Final Prices With a Special Discount in a Shop

Easy

Asked by:

31 views

Topics:

ArraysStacks

You are given an integer array prices where prices[i] is the price of the i^th item in a shop.

There is a special discount for items in the shop. If you buy the i^th item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the i^th item of the shop, considering the special discount.

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
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]
Explanation: 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]

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the prices in the input array? Can prices be zero or negative?
If a price does not have a discount (i.e., there's no price later in the array that is less than or equal to it), should the final price be the original price?
What should be returned if the input array is empty or null?
Can I modify the input array directly, or should I create a new array to store the final prices?
Are there any constraints on the size of the input array 'prices' that I should be aware of?

Brute Force Solution

Approach

The brute force method for this problem is very straightforward. We need to calculate the final price for each item by checking all the items that come after it to see if there's a discount available.

Here's how the algorithm would work step-by-step:

For the very first item, look at all the other items that come after it in the shop.
If you find an item that comes after the first item and is cheaper than the first item, then the final price of the first item is its original price minus the cheaper item's price.
If you can't find any item cheaper than the first one, then the final price of the first item is just its original price.
Now, do the exact same thing for the second item. Look at all the items that come after the second one.
Again, if you find a cheaper item, reduce the second item's price. If not, the price stays the same.
Keep doing this for every single item in the shop, one by one.
The final prices are then the prices you have after checking for discounts for each item.

Code Implementation

def final_prices_brute_force(prices):
    number_of_prices = len(prices)
    final_prices = prices[:]

    for current_price_index in range(number_of_prices):
        # Iterate through prices to find a discount.

        for next_price_index in range(current_price_index + 1, number_of_prices):
            # Check for a discount and apply it if found.
            if prices[next_price_index] <= prices[current_price_index]:

                final_prices[current_price_index] = prices[current_price_index] - prices[next_price_index]
                break

    return final_prices

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array 'prices' of size n. For each element at index i, it iterates through the remaining elements from index i+1 to n-1 to find a potential discount. In the worst case, for the first element, we compare with n-1 other elements, for the second element we compare with n-2 elements and so on. Thus, the total number of comparisons approximates to n*(n-1)/2. This simplifies to O(n²).

Space Complexity

O(1) – The brute force approach described only modifies the input array in place and uses a few integer variables for loop counters. There are no additional data structures like lists, hash maps, or recursion stack frames being created to store intermediate results or visited elements. Therefore, the algorithm's auxiliary space usage remains constant irrespective of the input size N (the number of items in the shop), leading to a space complexity of O(1).

Optimal Solution

Approach

The key idea is to use a special data structure that allows us to efficiently find the next smaller price for each item. We go through the prices one by one, keeping track of potential discounts in a way that avoids unnecessary comparisons.

Here's how the algorithm would work step-by-step:

Imagine a stack of prices. We'll use this to remember which prices might be discounts for later items.
Start looking at the prices from the beginning.
For each price, check if any prices we've seen before (those in our stack) are higher than the current price.
If we find some higher prices, it means the current price is a discount for them. Remove those higher prices from the stack, applying the discount.
After checking for discounts, add the current price to the stack. It might be a discount for items we see later.
Repeat this process for all the prices.
Finally, go back and calculate the final prices by subtracting any discounts we found from the original prices. If a price is still in the stack, it means it didn't have a discount.
The prices remaining in the stack indicate the element did not have a discount and must not be modified.

Code Implementation

def final_prices_with_discount(prices):
    number_of_prices = len(prices)
    final_prices = prices[:]
    stack = []

    for i in range(number_of_prices):
        # The stack holds potential discounts.
        while stack and prices[stack[-1]] >= prices[i]:
            final_prices[stack[-1]] -= prices[i]
            stack.pop()

        # Add the current price index to the stack.
        stack.append(i)

    return final_prices

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the prices array of size n once. While iterating, a stack is used to potentially apply discounts. Each price is pushed onto the stack at most once and popped at most once. Therefore, the stack operations, in total, take O(n) time. The total time complexity is thus dominated by the single pass through the array, resulting in O(n) complexity.

Space Complexity

O(N) – The algorithm uses a stack to store indices of prices. In the worst-case scenario, where the prices are monotonically increasing, all indices will be added to the stack. Therefore, the stack can potentially store up to N elements, where N is the number of prices in the input array. Thus, the auxiliary space used by the stack is proportional to the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array immediately as there are no prices to process.
Input array with only one element	Return the array as is, since no discount can be applied.
Input array with a large number of elements	Ensure the chosen algorithm has a time complexity of O(n) or O(n log n) to prevent timeouts, considering memory constraints.
Input array where all prices are the same	All prices will be discounted by the same amount, resulting in all discounted prices being the original price minus the discount or remain same if no discounted element is present.
Input array where prices are monotonically increasing	All prices will remain unchanged since no price will have a discount available.
Input array where prices are monotonically decreasing	Each price will be discounted by the next price in the sequence (except the last one which will remain unchanged).
Input array containing zero values	Zero values should be treated as valid prices and discounts applied accordingly.
Input array with extremely large integer values that could cause overflow	Use appropriate data types (e.g., long) to prevent integer overflow during calculations.

Empty input array

How to Handle:

Return an empty array immediately as there are no prices to process.

Input array with only one element

How to Handle:

Return the array as is, since no discount can be applied.

Input array with a large number of elements

How to Handle:

Ensure the chosen algorithm has a time complexity of O(n) or O(n log n) to prevent timeouts, considering memory constraints.

Input array where all prices are the same

How to Handle:

All prices will be discounted by the same amount, resulting in all discounted prices being the original price minus the discount or remain same if no discounted element is present.

Input array where prices are monotonically increasing

How to Handle:

All prices will remain unchanged since no price will have a discount available.

Input array where prices are monotonically decreasing

How to Handle:

Each price will be discounted by the next price in the sequence (except the last one which will remain unchanged).

Input array containing zero values

How to Handle:

Zero values should be treated as valid prices and discounts applied accordingly.

Input array with extremely large integer values that could cause overflow

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations.