Final Prices With a Special Discount in a Shop

Easy

#1362Time: O(n^2), where n is the number of items. In the worst-case scenario (e.g., a strictly increasing array), the inner loop runs approximately n times for each of the n items.Space: O(n) to store the `answer` array. If we modify the input array in-place, the auxiliary space complexity would be O(1).1 company

Data structures

Array Stack Monotonic Stack

Companies

Dream11

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through each item and then scan all subsequent items to find the first one that offers a discount.

Algorithm

Create a new array answer of the same size as prices to store the final prices.
Iterate through the prices array with an index i from 0 to n-1, where n is the length of the array.
For each i, initialize a discount variable to 0.
Start a nested loop with an index j from i + 1 to n-1.
Inside the inner loop, check if prices[j] is less than or equal to prices[i].
If the condition is met, it means we've found the first applicable discount. Set discount = prices[j] and break the inner loop.
After the inner loop, calculate the final price for item i as prices[i] - discount and store it in answer[i].
After the outer loop completes, return the answer array.

Walkthrough

We can solve this problem by using two nested loops. The outer loop iterates through each item i from the beginning to the end of the prices array. For each item i, the inner loop iterates through the subsequent items j (where j > i).

Inside the inner loop, we look for the first item j whose price prices[j] is less than or equal to the price of the current item prices[i]. If we find such an item, we calculate the discounted price prices[i] - prices[j], store it in our result, and break the inner loop since we only care about the first such j.

If the inner loop completes without finding any item j that satisfies the condition, it means no discount is applicable for item i. In this case, the final price is simply prices[i].

1class Solution {2    public int[] finalPrices(int[] prices) {3        int n = prices.length;4        int[] answer = new int[n];5        for (int i = 0; i < n; i++) {6            int discount = 0;7            for (int j = i + 1; j < n; j++) {8                if (prices[j] <= prices[i]) {9                    discount = prices[j];10                    break; // Found the first valid discount11                }12            }13            answer[i] = prices[i] - discount;14        }15        return answer;16    }17}

Complexity

Time

O(n^2), where n is the number of items. In the worst-case scenario (e.g., a strictly increasing array), the inner loop runs approximately n times for each of the n items.

Space

O(n) to store the `answer` array. If we modify the input array in-place, the auxiliary space complexity would be O(1).

Trade-offs

Pros

Simple to understand and implement.
Directly follows the logic from the problem description.
Low auxiliary space complexity if allowed to modify the input array.

Cons

Inefficient for large input arrays due to its quadratic time complexity.

This problem can be optimized by recognizing it as a variation of the 'Next Smaller Element' problem. A monotonic stack is an ideal data structure for this, allowing us to find the next smaller or equal element for each item in a single pass.

Algorithm

Initialize an empty stack to store indices.
Initialize an answer array of the same size as prices.
Iterate through the prices array from right to left (from i = n-1 down to 0).
For each i, while the stack is not empty and the price at the index on top of the stack (prices[stack.peek()]) is strictly greater than prices[i], pop from the stack.
After the loop, if the stack is empty, there is no discount. Set answer[i] = prices[i].
Otherwise, the discount is prices[stack.peek()]. Set answer[i] = prices[i] - prices[stack.peek()].
Push the current index i onto the stack.
After iterating through all items, return the answer array.

Walkthrough

We can achieve a linear time solution using a monotonic stack. The stack will store indices of prices, maintaining a monotonically non-decreasing order of prices from bottom to top.

We iterate through the prices array from right to left. For each price prices[i], we look at the top of the stack. The elements on the stack represent items to the right of i.

While the stack is not empty and the price at the index on top of the stack is greater than prices[i], we pop from the stack. These popped items cannot be the discount for prices[i] or any item to its left (since prices[i] is smaller and closer).

After the while loop, if the stack is empty, it means no item to the right of i has a price less than or equal to prices[i]. The discount is 0.

If the stack is not empty, the index at the top of the stack corresponds to the first item to the right of i with a price less than or equal to prices[i]. This is the discount we apply.

Finally, we push the current index i onto the stack to be considered for items to its left. Since we process the array from right to left, we can directly calculate the final price for each item.

1import java.util.Stack;2 3class Solution {4    public int[] finalPrices(int[] prices) {5        int n = prices.length;6        int[] answer = new int[n];7        Stack<Integer> stack = new Stack<>(); // Stack of indices8 9        for (int i = n - 1; i >= 0; i--) {10            // Pop elements from stack that are greater than current price11            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {12                stack.pop();13            }14 15            // If stack is empty, no discount16            if (stack.isEmpty()) {17                answer[i] = prices[i];18            } else {19                // Top of stack is the next smaller or equal element20                answer[i] = prices[i] - prices[stack.peek()];21            }22 23            // Push current index onto the stack24            stack.push(i);25        }26        return answer;27    }28}

Complexity

Time

O(n), where n is the number of items. Each index is pushed onto and popped from the stack at most once, so the total operations are linear.

Space

O(n) in the worst case for the stack (e.g., for a strictly increasing array like `[1, 2, 3, 4, 5]`). This is auxiliary space, in addition to the O(n) space required for the output array.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Solves the problem in a single pass over the array.

Cons

Requires extra space for the stack.
The logic might be less intuitive than the brute-force approach for beginners.

Solutions

Solution

1class Solution { public int [] finalPrices ( int [] prices ) { int n = prices . length ; int [] ans = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = prices [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { if ( prices [ j ] <= prices [ i ]) { ans [ i ] -= prices [ j ]; break ; } } } return ans ; } }

1/** * @param {number[]} prices * @return {number[]} */ var finalPrices = function ( prices ) { for ( let i = 0 ; i < prices . length ; i ++ ) { for ( let j = i + 1 ; j < prices . length ; j ++ ) { if ( prices [ i ] >= prices [ j ]) { prices [ i ] -= prices [ j ]; break ; } } } return prices ; };

1class Solution : def finalPrices ( self , prices : List [ int ]) -> List [ int ]: ans = [] for i , v in enumerate ( prices ): ans . append ( v ) for j in range ( i + 1 , len ( prices )): if prices [ j ] <= v : ans [ - 1 ] -= prices [ j ] break return ans

1class Solution { public: vector < int > finalPrices ( vector < int >& prices ) { int n = prices . size (); vector < int > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = prices [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { if ( prices [ j ] <= prices [ i ]) { ans [ i ] -= prices [ j ]; break ; } } } return ans ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem