# Final Prices With a Special Discount in a Shop
**Difficulty:** EASY
[External](https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop)
Canonical: https://scaleengineer.com/dsa/problems/final-prices-with-a-special-discount-in-a-shop
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Dream11](https://scaleengineer.com/companies/dream11)
---
## Problem
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
## Brute Force using Nested Loops
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.
**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).
**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.
### Explanation
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]`.

```java
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;
    }
}
```
### 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.

## Optimized Approach using Monotonic Stack
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Stack;

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>(); // Stack of indices

        for (int i = n - 1; i >= 0; i--) {
            // Pop elements from stack that are greater than current price
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                stack.pop();
            }

            // If stack is empty, no discount
            if (stack.isEmpty()) {
                answer[i] = prices[i];
            } else {
                // Top of stack is the next smaller or equal element
                answer[i] = prices[i] - prices[stack.peek()];
            }

            // Push current index onto the stack
            stack.push(i);
        }
        return answer;
    }
}
```
### Algorithm
1. Initialize an empty `stack` to store indices.
2. Initialize an `answer` array of the same size as `prices`.
3. Iterate through the `prices` array from right to left (from `i = n-1` down to `0`).
4. 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.
5. After the loop, if the stack is empty, there is no discount. Set `answer[i] = prices[i]`.
6. Otherwise, the discount is `prices[stack.peek()]`. Set `answer[i] = prices[i] - prices[stack.peek()]`.
7. Push the current index `i` onto the stack.
8. After iterating through all items, return the `answer` array.

# Solutions
### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @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 ; };
```

### Python

```python
class 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
```

### CPP

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