Final Prices With a Special Discount in a Shop

Final Prices With a Special Discount in a Shop – LeetCode Solution Explained

When tackling coding problems, it's important to understand the problem thoroughly and work through solutions step-by-step. In this blog, we will explore the LeetCode problem "1475 Final Prices With a Special Discount in a Shop". We'll walk through the problem statement, approach it with a beginner-friendly brute force solution, and analyze its time and space complexity. Finally, we'll discuss any possible optimizations to improve efficiency.

Problem Statement

You are given an integer array prices where prices[i] represents the price of the ith item in a shop. There is a special discount rule:

If you buy the ith item, you receive a discount equal to prices[j], where j is the smallest index such that j > i and prices[j] <= prices[i].
If no such j exists, you get no discount for that item.

Your task is to return a new array answer, where answer[i] is the final price you pay for the ith item after applying the discount.

Examples

Example 1:

Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]

Explanation:

For prices[0] = 8, the discount is prices[1] = 4, so the final price is 8 - 4 = 4.
For prices[1] = 4, the discount is prices[3] = 2, so the final price is 4 - 2 = 2.
For prices[2] = 6, the discount is prices[3] = 2, so the final price is 6 - 2 = 4.
For prices[3] = 2 and prices[4] = 3, no discount applies.

Example 2:

Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]

Explanation: In this case, no item has a valid discount available.

Example 3:

Input: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]

Explanation:

For prices[0] = 10, the discount is prices[1] = 1, so the final price is 10 - 1 = 9.
For prices[1] = 1, the discount is prices[2] = 1, so the final price is 1 - 1 = 0.
For prices[2] = 1 and prices[3] = 6, no discount applies.

Approach 1: Brute Force Solution

The most intuitive way to solve this problem is by using two nested loops. For each item in the array, we look for the first eligible discount in the remaining items.

Algorithm

Loop through each price in the array using index i.
For each i, iterate through the subsequent prices (from i+1 to the end) using index j.
If you find a price prices[j] such that prices[j] <= prices[i], apply the discount and break the inner loop.
If no such j exists, the price remains unchanged.
Return the modified prices array.

Code Implementation (CPP)

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

Time Complexity

Outer loop: Runs n times (for each price).
Inner loop: In the worst case, it runs up to n-i-1 times.

Space Complexity

The solution uses no additional data structures.

Optimized Approach: Using a Stack

While the brute force solution works, it’s inefficient for large inputs. We can optimize it using a monotonic stack, which allows us to keep track of potential discounts more efficiently.

Algorithm

Use a stack to store indices of prices in decreasing order.
Traverse the prices array from left to right.
For each price, check the top of the stack:
- If the current price is less than or equal to the price at the top index, calculate the discount and update the array.
- Pop the top index from the stack.
Push the current index onto the stack.
Return the modified prices array.

Code Implementation

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> st;
        for (int i = 0; i < prices.size(); i++) {
            while (!st.empty() && prices[st.top()] >= prices[i]) {
                int idx = st.top();
                st.pop();
                prices[idx] -= prices[i];
            }
            st.push(i);
        }
        return prices;
    }
};

Time Complexity

Each element is pushed onto the stack once and popped once.
O(n)

Space Complexity

The stack stores indices, which in the worst case can grow to .
O(n)

Comparison of Approaches

Approach			Notes
Brute Force ->			Simple but inefficient
Stack Optimization ->			Efficient for larger datasets

This problem highlights the power of monotonic stacks in optimizing problems that involve comparisons across array elements. By practicing this approach, you’ll develop skills applicable to many similar problems.

AlgoPush

Search This Blog