Problem Overview and Featured Summary

Featured Summary: The "Final Prices With a Special Discount in a Shop" is a popular algorithmic challenge that tests your ability to optimize nested loops using advanced data structures. In this problem, you are given an integer array prices where prices[i] represents the price of the ith item in a shop. The goal is to find the final price after applying a special discount: for each item, the discount is the price of the first subsequent item that is less than or equal to the current item's price. By leveraging a monotonic stack in C++, you can achieve an optimal O(n) time complexity solution.

Detailed Problem Statement

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 Scenarios

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]

Optimal C++ Solution Using a Monotonic Stack

The naive approach involves using nested loops to find the first smaller or equal element to the right, which results in an O(n²) time complexity. However, we can optimize this significantly by employing a monotonic stack. This data structure allows us to keep track of elements for which we haven't yet found a discount, reducing the time complexity to O(n).

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> st; 
        
        for (int i = 0; i < prices.size(); i++) {
            // While the stack is not empty and the current price is less than or equal
            // to the price at the index stored at the top of the stack
            while (!st.empty() && prices[i] <= prices[st.top()]) {
                int index = st.top(); 
                st.pop();
                // Apply the discount
                prices[index] -= prices[i]; 
            }
            // Push the current index onto the stack
            st.push(i); 
        }
        
        // Return the modified prices array as the answer
        return prices; 
    }
};

Algorithm Explanation and Step-by-Step Execution

1. Monotonic Stack Initialization: We use a stack to keep track of indices where the discount is yet to be applied. The stack is monotonic decreasing, meaning it stores indices of prices in non-increasing order of their original values.
2. Efficient Discount Calculation: For each price during the iteration, we check the stack:
   • If the current price is less than or equal to the price at the top of the stack, we apply the discount for the index at the top of the stack.
   • We remove that index from the stack since the discount has been fully applied.
3. Index Pushing: We then push the current index onto the stack to find its discount in future iterations.
4. Time Complexity: Each element is pushed onto the stack exactly once and popped from the stack at most once, resulting in a strictly O(n) time complexity.
5. Space Complexity: The stack stores at most n indices simultaneously, so the auxiliary space complexity is O(n).

Trace of Example Execution

Let's trace the algorithm for prices = [8, 4, 6, 2, 3]:

• Initialization: answer = [8, 4, 6, 2, 3], stack = [].
• Iteration 1 (i = 0): Push index 0. stack = [0].
• Iteration 2 (i = 1): prices[1] (4) <= prices[0] (8). Discount applied: answer[0] = 8 - 4 = 4. Pop stack. Push index 1. stack = [1].
• Iteration 3 (i = 2): prices[2] (6) > prices[1] (4). No discount yet. Push index 2. stack = [1, 2].
• Iteration 4 (i = 3):
  • prices[3] (2) <= prices[2] (6). Discount: answer[2] = 6 - 2 = 4. Pop stack. stack = [1].
  • prices[3] (2) <= prices[1] (4). Discount: answer[1] = 4 - 2 = 2. Pop stack. stack = [].
  • Push index 3. stack = [3].
• Iteration 5 (i = 4): prices[4] (3) > prices[3] (2). No discount yet. Push index 4. stack = [3, 4].

The final resulting array is [4, 2, 4, 2, 3].

Frequently Asked Questions

To further clarify the mechanics of this algorithm, here are some commonly asked questions regarding the monotonic stack approach:

What is the time complexity of the monotonic stack approach?

The time complexity is O(n) because each element is pushed and popped from the monotonic stack at most once during the iteration.

Why use a monotonic stack for the Final Prices problem?

A monotonic stack efficiently tracks elements for which we haven't found the next smaller or equal element, allowing us to find the discount in a single linear pass.

What happens if no discount is found for an item?

If no subsequent item has a price less than or equal to the current item's price, the original price is paid without any discount applied. The element's index simply remains in the stack.