algoadvance

Leetcode 2144. Minimum Cost of Buying Candies With Discount

Problem Statement

You are given an integer array cost where cost[i] is the cost of the i-th candy. Return the minimum cost of buying all the candies where you can get a discount: for every two candies you buy, you get a third candy for free (the lowest-priced candy among the three).

Clarifying Questions

  1. Q: Are all elements in the cost array positive integers? A: Yes, all costs are positive integers.

  2. Q: What if the number of candies (n) is less than 3? A: If n < 3, no discount applies, and the total cost is the sum of all elements in cost.

  3. Q: Can the array be empty? A: No, the array won’t be empty based on the problem constraints.

Strategy

  1. Sort the Cost Array: To minimize the total cost, sort the cost array in descending order. By doing this, we can ensure that we buy the two most expensive candies in each group of three, thus getting the third (cheaper or equal) one for free.

  2. Accumulate the Cost: Traverse the sorted array and add the cost of every third candy to our total cost, skipping the third candy (as it is free).

  3. Traverse in Groups of Three: Iterate through the sorted list with a step size of three, adding the first two elements of each group to the total cost.

Code Implementation

Here’s the Java implementation for the described strategy:

import java.util.Arrays;

public class MinimumCostCandies {
    
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        
        int totalCost = 0;
        
        // Traverse the array from the end to the start
        for (int i = cost.length - 1; i >= 0; i--) {
            // Buy the first and second candy in this group of three
            totalCost += cost[i];
            if (i - 1 >= 0) {
                totalCost += cost[i - 1];
            }
            
            // Skip the third candy (i - 2) as it's free
            i -= 2;
        }
        
        return totalCost;
    }

    public static void main(String[] args) {
        MinimumCostCandies mcc = new MinimumCostCandies();
        
        int[] cost1 = {1, 2, 3};
        System.out.println(mcc.minimumCost(cost1));  // Output: 5
        
        int[] cost2 = {6, 5, 7, 9, 2, 2};
        System.out.println(mcc.minimumCost(cost2));  // Output: 23
        
        int[] cost3 = {8, 4, 6, 5};
        System.out.println(mcc.minimumCost(cost3));  // Output: 19
    }
}

Time Complexity

  1. Sorting the Array: The time complexity of sorting the array is (O(n \log n)), where (n) is the length of the cost array.

  2. Traversing the Array: The traversal over the array has a time complexity of (O(n)).

Thus, the overall time complexity of the solution is (O(n \log n)) due to the sorting step.

Space Complexity

The space complexity is (O(1)) additional space, disregarding the space used by the sorting algorithm (which can be (O(n)) depending on the sorting implementation).

This should provide a clear and efficient solution to the given problem.

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