algoadvance

Leetcode 1475. Final Prices With a Special Discount in a Shop

Problem Statement

Given a list of prices for a shop, you need to compute the final prices after applying a special discount. The discount on the price of a particular item is equal to the price of the next item in the list which has a price less than or equal to the current item’s price. If there is no such item, then no discount is applied to the current item’s price.

Write a function vector<int> finalPrices(vector<int>& prices) that takes a list of integers prices where prices[i] is the price of the i-th item, and returns a list of integers representing the final prices after the discounts have been applied.

Clarifying Questions

  1. Are all the prices non-negative integers?
    • Yes, prices are guaranteed to be non-negative integers.
  2. What should be the return type?
    • The return type should be a vector of integers.
  3. Can there be repeated prices in the list?
    • Yes, there can be repeated prices.

Strategy

  1. Traverse the List: We will iterate through the list of prices.
  2. Find the Discount: For each item, find the first subsequent item whose price is less than or equal to the current item’s price.
  3. Apply the Discount: Subtract this value from the current item’s price.
  4. Build the Result: Store the final prices in a new list and return it.

We can use a stack to efficiently find the next smaller or equal price to the right for each item. This allows us to solve the problem in linear time complexity.

Code

#include <vector>
#include <stack>

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

Explanation

  1. Initialization:
    • result vector is initialized with the same elements as prices.
    • A stack st is used to keep track of indices where we are looking for a discount.
  2. Traversal and Discount Application:
    • We iterate over each element in the prices vector.
    • For each price, we check if the stack is not empty and the price at the top index of the stack is greater than or equal to the current price (prices[i]).
    • If true, it means we found a discount for the price at the index stored in the stack. We pop that index, and then reduce the result at that index by prices[i].
    • Push the current index i onto the stack.
  3. Return the result vector as the final prices after discount application.

Time Complexity

This approach efficiently computes the final prices after applying the described discounts.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI