algoadvance

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

Problem Statement

You are given an array prices where prices[i] is the price of the ith item in a shop. There is a special discount rule that can be applied to each item: if you buy the item at index i, then you will receive a discount equivalent to the price of the next item with a lesser or equal price than prices[i]. If there is no such item, you will not receive any discount for that item.

Implement a method that returns an array where the value at each index i is the final price you will pay for the item at index i, considering the special discount.

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

  1. Q: What are the constraints on the size of the prices array? A: Constraints are not strictly provided, but you may assume it can be reasonably large (up to 10^4).

  2. Q: Can the prices in the prices array be negative? A: No, prices are non-negative integers.

  3. Q: Can we have repeated prices in the prices array? A: Yes, prices can have repeated values.

  4. Q: What is the range of values for each element in prices? A: Each price will be a non-negative integer and can be reasonably large.

Strategy

To solve this problem, we can use a stack to optimize the search for the next lesser or equal price. The basic idea is to maintain a stack that helps in keeping track of the indices of prices in a way that allows us to efficiently check the next smaller or equal price for any given item.

  1. Initialize an empty stack.
  2. Iterate over the prices array from the end to the start.
  3. For each element:
    • While the stack is not empty and the top of the stack (price) is greater than the current price, pop elements from the stack.
    • If the stack is not empty at this point, the top of the stack is the next lesser or equal price.
    • Compute the final price and store it.
    • Push the current price onto the stack.

Time Complexity

The time complexity is O(n) where n is the length of the prices array. This is because each element is pushed and popped from the stack at most once.

Code

Here’s the Java implementation of the above strategy:

import java.util.Stack;

public class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        // Resultant array to hold the final prices
        int[] finalPrices = new int[n];
        // Stack to keep track of the indices
        Stack<Integer> stack = new Stack<>();
        
        // Iterate over the prices array from the end to the start
        for (int i = n - 1; i >= 0; i--) {
            // Remove elements from the stack that are greater than the current price
            while (!stack.isEmpty() && stack.peek() > prices[i]) {
                stack.pop();
            }
            // If stack is not empty, the top element is the next lesser or equal price
            finalPrices[i] = (stack.isEmpty()) ? prices[i] : prices[i] - stack.peek();
            // Push the current price onto the stack
            stack.push(prices[i]);
        }
        
        return finalPrices;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices1 = {8, 4, 6, 2, 3};
        int[] result1 = sol.finalPrices(prices1);
        for (int price : result1) {
            System.out.print(price + " ");
        }
        // Output: 4 2 4 2 3
        
        System.out.println();
        
        int[] prices2 = {1, 2, 3, 4, 5};
        int[] result2 = sol.finalPrices(prices2);
        for (int price : result2) {
            System.out.print(price + " ");
        }
        // Output: 1 2 3 4 5
        
        System.out.println();
        
        int[] prices3 = {10, 1, 1, 6};
        int[] result3 = sol.finalPrices(prices3);
        for (int price : result3) {
            System.out.print(price + " ");
        }
        // Output: 9 0 1 6
    }
}

By using stack, we efficiently find the next lesser or equal price for each item, reducing time complexity significantly compared to a naive approach.

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