Scale Engineer

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
ArrayStackMonotonic Stack
Companies
Dream11

Prompt

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

There is a special discount for items in the shop. If you buy the ith 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 ith 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

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

class Solution {    public int[] finalPrices(int[] prices) {        int n = prices.length;        int[] answer = new int[n];        for (int i = 0; i < n; i++) {            int discount = 0;            for (int j = i + 1; j < n; j++) {                if (prices[j] <= prices[i]) {                    discount = prices[j];                    break; // Found the first valid discount                }            }            answer[i] = prices[i] - discount;        }        return answer;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem