Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.
The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.
4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.
Example 1:
Input: cost = [1,2,3] Output: 5 Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free. The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies. Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free. The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.
Example 2:
Input: cost = [6,5,7,9,2,2] Output: 23 Explanation: The way in which we can get the minimum cost is described below: - Buy candies with costs 9 and 7 - Take the candy with cost 6 for free - We buy candies with costs 5 and 2 - Take the last remaining candy with cost 2 for free Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.
Example 3:
Input: cost = [5,5] Output: 10 Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free. Hence, the minimum cost to buy all candies is 5 + 5 = 10.
Constraints:
1 <= cost.length <= 1001 <= cost[i] <= 100Problem summary: A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free. The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought. For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4. Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Greedy
[1,2,3]
[6,5,7,9,2,2]
[5,5]
array-partition)minimum-absolute-difference)minimum-number-of-operations-to-satisfy-conditions)check-if-grid-satisfies-conditions)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2144: Minimum Cost of Buying Candies With Discount
class Solution {
public int minimumCost(int[] cost) {
Arrays.sort(cost);
int ans = 0;
for (int i = cost.length - 1; i >= 0; i -= 3) {
ans += cost[i];
if (i > 0) {
ans += cost[i - 1];
}
}
return ans;
}
}
// Accepted solution for LeetCode #2144: Minimum Cost of Buying Candies With Discount
func minimumCost(cost []int) (ans int) {
sort.Ints(cost)
for i := len(cost) - 1; i >= 0; i -= 3 {
ans += cost[i]
if i > 0 {
ans += cost[i-1]
}
}
return
}
# Accepted solution for LeetCode #2144: Minimum Cost of Buying Candies With Discount
class Solution:
def minimumCost(self, cost: List[int]) -> int:
cost.sort(reverse=True)
return sum(cost) - sum(cost[2::3])
// Accepted solution for LeetCode #2144: Minimum Cost of Buying Candies With Discount
struct Solution;
impl Solution {
fn minimum_cost(mut cost: Vec<i32>) -> i32 {
cost.sort_unstable();
let mut i = 0;
let mut res = 0;
while let Some(x) = cost.pop() {
i += 1;
i %= 3;
if i != 0 {
res += x;
}
}
res
}
}
#[test]
fn test() {
let cost = vec![1, 2, 3];
let res = 5;
assert_eq!(Solution::minimum_cost(cost), res);
let cost = vec![6, 5, 7, 9, 2, 2];
let res = 23;
assert_eq!(Solution::minimum_cost(cost), res);
let cost = vec![5, 5];
let res = 10;
assert_eq!(Solution::minimum_cost(cost), res);
}
// Accepted solution for LeetCode #2144: Minimum Cost of Buying Candies With Discount
function minimumCost(cost: number[]): number {
cost.sort((a, b) => a - b);
let ans = 0;
for (let i = cost.length - 1; i >= 0; i -= 3) {
ans += cost[i];
if (i) {
ans += cost[i - 1];
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.