Code Implementation

class Solution:
    def finalPrices(self, prices):
        n = len(prices)
        answer = prices[:]
        for i in range(n):
            for j in range(i+1, n):
                if prices[j] <= prices[i]:
                    answer[i] = prices[i] - prices[j]
                    break
        return answer
      

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

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

var finalPrices = function(prices) {
    let n = prices.length;
    let answer = prices.slice();
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if (prices[j] <= prices[i]) {
                answer[i] = prices[i] - prices[j];
                break;
            }
        }
    }
    return answer;
};
      

Problem Description

You are given an array of integers called prices, where each element represents the price of an item in a shop, arranged in the order they are displayed. For each item at index i, you need to find the first item with index j > i such that prices[j] <= prices[i]. If such an item exists, you receive a discount equal to prices[j] on the current item. If no such item exists, there is no discount. The goal is to return an array where each element is the final price after applying the special discount described above.

Key constraints:

• Each item may receive at most one discount, from the first qualifying item that follows it.
• Discounts are only applied to items that come after the current item (no reordering).
• There is always exactly one possible final price per item.

Thought Process

At first glance, the problem looks like we need to, for each item, scan ahead to find the first item that is less than or equal to its value. This suggests a straightforward brute-force approach where, for each item, we look at every item that comes after it until we find a suitable discount or reach the end of the array.

However, brute-force can be inefficient for large arrays. We might wonder if there's a way to make this more efficient, perhaps by using a stack to remember possible discounts as we scan through the list. The key insight is that for each item, we're only interested in the first qualifying price after it, which hints at a "next less than or equal" pattern, often solved with a stack.

Solution Approach

Let's walk through both the brute-force and optimized approaches:

• Brute-force approach:
  1. For each index i in prices:
  2. Scan all items at indices j > i.
  3. If you find prices[j] <= prices[i], subtract prices[j] from prices[i] and break.
  4. If no such j is found, keep the original price.
  This is simple to implement but has O(n²) time complexity.
• Optimized approach (using a stack):
  1. Initialize an empty stack to keep track of indices whose discounts haven't been found yet.
  2. Iterate through the prices array:
  3. While the stack isn't empty and prices[current] <= prices[stack.top()]:
     • Pop the index from the stack and set its discount to prices[current].
  4. Push the current index onto the stack.
  5. At the end, prices that remain in the stack get no discount.
  This approach is O(n) time and O(n) space.

For teaching purposes, the initial brute-force solution is often used, as shown in the code tabs above.

Example Walkthrough

Let's use the input prices = [8, 4, 6, 2, 3]:

• i = 0 (prices[0] = 8):
  • Look at 4, 6, 2, 3. The first value ≤ 8 is 4 (at index 1).
  • Discount: 8 - 4 = 4.
• i = 1 (prices[1] = 4):
  • Look at 6, 2, 3. The first value ≤ 4 is 2 (at index 3).
  • Discount: 4 - 2 = 2.
• i = 2 (prices[2] = 6):
  • Look at 2, 3. The first value ≤ 6 is 2 (at index 3).
  • Discount: 6 - 2 = 4.
• i = 3 (prices[3] = 2):
  • Look at 3. 3 is not ≤ 2, so no discount.
  • Final price: 2.
• i = 4 (prices[4] = 3):
  • No items after this. No discount.
  • Final price: 3.

The final output is [4, 2, 4, 2, 3].

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) because for each item we may scan all items after it.
  • Space Complexity: O(1) extra (not counting the output array).
• Optimized (stack) approach:
  • Time Complexity: O(n) because each index is pushed and popped at most once from the stack.
  • Space Complexity: O(n) for the stack and output array.

Summary

The key insight is that for each price, we want the first following price that is less than or equal to it. The brute-force approach is intuitive but slow for large inputs. Using a stack, we can efficiently find and apply discounts in a single pass, making the solution both elegant and optimal. This pattern of "next less than or equal" is common and recognizing it allows us to use efficient data structures like stacks to solve similar problems quickly.