2144. Minimum Cost of Buying Candies With Discount

EasyGreedyArraySorting
Leetcode Link

Problem Description

In this problem, we are working with a candy shop that has a particular discount scheme: for every two candies purchased, a third candy is given for free. The caveat is that the cost of the free candy can't exceed the cost of the least expensive candy bought among the two. We need to find out how much the customer will have to pay in total to buy all the candies available in the shop considering this discount.

The given data is an integer array cost which represents the price of each candy. The array is 0-indexed, meaning that the first element is at index 0, the second at index 1, and so on. Our task is to calculate the minimum total cost required to buy all candies while making the most out of the given discount.

Intuition

To minimize the total cost of buying all the candies while taking advantage of the discount, we should aim to get the more expensive candies for free when possible. Hence, the best strategy would be to sort the candies in descending order of their cost. That way, every time we pick two candies, they will be the most expensive ones available, and we can then choose one of the less expensive candies for free (following the rule that the free candy must be priced less than or equal to the cheaper of the two paid candies).

After sorting, we can observe that in every three consecutive candies starting from the first (index 0), the third one (at index 2) would be the free one if we adopt the purchasing pattern of buying in sets of three, so to speak. We continue this pattern throughout the array. Thus, by taking the sum of all candies' costs and subtracting the sum of every third candy post-sorting, we get the total minimum cost. This is exactly what the provided solution is doing: it sorts the list in reverse order, then sums up all elements, excluding every third element starting by the third (index 2, as the index is zero-based). That is the sum of all the costs of the free candies if we buy them in an optimal way.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution approach takes advantage of sorting and list slicing operations. Here's a step-by-step explanation of the implementation:

  1. Sorting the list in reverse order: We use the sort method with the reverse=True parameter to rearrange the elements of the cost list in descending order. Sorting is a common algorithmic pattern when we need to rearrange data for optimization purposes, such as minimizing or maximizing some value subject to constraints—in this case, the constraint is the "buy two, get one free" deal.

    cost.sort(reverse=True)

    After this operation, the most expensive candies are at the beginning of the list, and the least expensive ones are at the end.

  2. Calculating the total sum: The sum function calculates the total cost of the candies if there were no discounts. This serves as our starting point for finding the minimum cost.

    total_cost = sum(cost)

  3. Identifying the free candies using slicing: The third step uses list slicing to identify all the candies that would be free. The slice operation cost[2::3] takes every third candy from the list, starting with the one at index 2 (zero-based index, which is the third candy). This exploits a pattern that emerges from sorting the candies by cost: when they are sorted in descending order, each set of three contains two paid candies followed by one free candy.

    free_candies_cost = sum(cost[2::3])

  4. Subtracting the cost of free candies: By subtracting the sum of the free candies' costs from the total cost, we arrive at the minimum cost to buy all candies. This effectively applies the "buy two, get one free" discount across the entire list.

    minimum_cost = total_cost - free_candies_cost

Putting it all together, the provided solution is a compact representation of these steps, combining the total calculation and the subtraction of the free candies' costs into a single line:

return sum(cost) - sum(cost[2::3])

This approach is both elegant and efficient, as it avoids the need for explicit loops or additional data structures. The sorting algorithm behind the sort method typically has O(n log n) complexity, where n is the number of candies, and the slicing operation has O(n) complexity. Thus, the overall complexity of the solution is dominated by the sorting step.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's suppose we have the following candy prices:

1cost = [1, 3, 2, 8, 5, 7]

To understand the solution approach, let's walk through it step by step using this example:

  1. Sorting the list in reverse order: We sort the cost list in descending order to prioritize the purchase of the most expensive candies first.

    1cost.sort(reverse=True)  // After sorting: cost = [8, 7, 5, 3, 2, 1]

  2. Calculating the total sum: Before applying the discount, calculate the total cost of all candies.

    1total_cost = sum(cost)  // total_cost = 8 + 7 + 5 + 3 + 2 + 1 = 26

  3. Identifying the free candies using slicing: According to the discount, for every two candies purchased, the third one is free, starting from the least expensive of the paid ones. To find the free candies applying the discount optimally, we take every third candy in the sorted list, beginning with the one at index 2.

    1free_candies_cost = sum(cost[2::3])  // The free candies are at indices 2 and 5, so free_candies_cost = 5 + 1 = 6

  4. Subtracting the cost of free candies: Finally, to get the minimum cost after the discount, subtract the total cost of free candies from the total cost.

    1minimum_cost = total_cost - free_candies_cost  // minimum_cost = 26 - 6 = 20

So, the minimum total cost to buy all candies while taking full advantage of the discounts is 20.

Using our approach, we've paired the most expensive candies first ([8, 7], [5, 3]), then we get the least expensive candies as the free items ([2] and [1]). The 2 and 1 correspond to the third items in each buying set, which are the free items according to our sorted cost list.

By following these steps, the provided solution effectively minimizes the total cost, ensuring that customers get the highest-priced candies possible for free, in compliance with the shop's discount policy.

Solution Implementation

1class Solution:
2    def minimumCost(self, costs: List[int]) -> int:
3        # Sort the list of costs in descending order
4        costs.sort(reverse=True)
5
6        # Initialize the minimum cost to the sum of all costs
7        min_cost = sum(costs)
8
9        # Subtract the cost of every third item starting from the third item
10        # because it would be the free item as per the typical "buy two, get one free" offer.
11        min_cost -= sum(costs[2::3])
12
13        # Return the calculated minimum cost
14        return min_cost
15
1class Solution {
2  
3    /**
4     * Calculates the minimum cost to purchase all the items given that
5     * every third item is free after sorting the array in non-decreasing order.
6     *
7     * @param costs Array of individual costs of items.
8     * @return The minimum total cost to purchase all items.
9     */
10    public int minimumCost(int[] costs) {
11        // Sort the array of costs in non-decreasing order.
12        Arrays.sort(costs);
13      
14        int totalCost = 0; // Initialize total cost to 0.
15        // Start purchasing items from the most expensive one.
16        for (int i = costs.length - 1; i >= 0; i -= 3) {
17            totalCost += costs[i]; // Purchase the most expensive item.
18            if (i > 0) { // Check if there is a second item to purchase.
19                totalCost += costs[i - 1]; // Purchase the second item.
20            }
21        }
22        return totalCost; // Return the total minimum cost.
23    }
24}
25
1#include <vector>
2#include <algorithm> // Included for std::sort
3
4class Solution {
5public:
6    /**
7    * Calculate the minimum cost of buying items based on the offer to pay for two
8    * items and get one free, optimizing to always get the most expensive item for free.
9    * 
10    * @param costs Vector of individual item costs.
11    * @return The minimum total cost with the offer applied.
12    */
13    int minimumCost(vector<int>& costs) {
14        // Sort the costs in descending order to prioritize the most expensive items.
15        std::sort(costs.rbegin(), costs.rend());
16      
17        int totalCost = 0; // Initialize total cost to 0
18      
19        // Iterate over every three items to apply the "buy two get one free" offer
20        for (int i = 0; i < costs.size(); i += 3) {
21            totalCost += costs[i]; // Always add the cost of the first item (most expensive)
22          
23            // Check if there is a second item to also add its cost
24            if (i + 1 < costs.size()) {
25                totalCost += costs[i + 1]; // Add the cost of the second item
26            }
27          
28            // The third item is free, so it is not added to the total
29        }
30      
31        // Return the calculated minimum total cost
32        return totalCost;
33    }
34};
35
1function minimumCost(cost: number[]): number {
2    // Sort the array in ascending order to ensure that the minimum values are skipped
3    cost.sort((a, b) => a - b);
4
5    let totalCost = 0; // Initialize the total cost variable
6
7    // Start iterating from the end of array towards the front
8    // We jump three steps at a time since every third flower is free
9    for (let i = cost.length - 1; i >= 0; i -= 3) {
10        totalCost += cost[i]; // Add the cost of the current flower
11        // If there is another flower before the current one, add that cost too
12        if (i > 0) {
13            totalCost += cost[i - 1];
14        }
15    }
16
17    // Return the total cost after applying the discount for every third flower
18    return totalCost;
19}
20
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The given Python code aims to calculate the minimum cost of purchasing items given that every third item is free when items are purchased in descending order of cost. We will analyze the time and space complexity of the provided code.

Time Complexity:

  1. The sort function on the list cost has a time complexity of O(n log n) where n is the number of elements in the list cost. This is because Python's Timsort algorithm is used for sorting, which has this time complexity.
  2. The sum function iterates over the entire list, resulting in O(n) time complexity.
  3. The slicing operation cost[2::3] generates a new list containing every third element from the list cost, leading to O(n/3) complexity, which simplifies to O(n).

Combining these operations, the dominant term is the sorting operation. Thus, the total time complexity of the code is O(n log n).

Space Complexity:

  1. The sorting is done in-place, so there is no additional space required for this operation.
  2. The sum function operates on the list without creating new structures, so it uses O(1) space.
  3. The slicing operation cost[2::3] creates a new list, which in the worst case, could be O(n/3) space complexity. However, since constants are dropped in Big O notation, it simplifies to O(n) space complexity.

Therefore, the space complexity of the code is O(n), accounting for the space needed to store the new list generated by the slicing operation.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫