LeetCode 2144: Minimum Cost of Buying Candies With Discount (Greedy + Sorting)

2026-04-29 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 2144GreedySorting

Source: https://leetcode.com/problems/minimum-cost-of-buying-candies-with-discount/

Sort prices in descending order, pay for the first two candies in every group of three, and take the third as free.

LeetCode 2144 pay-two-get-one grouping diagram

English

Idea

To maximize discount, the free candy should be as expensive as possible, but it must be the cheapest inside its triple. So we sort descending and for indices 2,5,8... skip payment.

Complexity

Time: O(n log n) (sorting). Space: O(1) extra if sorting in-place.

Code Tabs (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        int ans = 0;
        int take = 0;
        for (int i = cost.length - 1; i >= 0; i--) {
            take++;
            if (take == 3) {
                take = 0;
                continue;
            }
            ans += cost[i];
        }
        return ans;
    }
}

func minimumCost(cost []int) int {
    sort.Ints(cost)
    ans, take := 0, 0
    for i := len(cost)-1; i >= 0; i-- {
        take++
        if take == 3 {
            take = 0
            continue
        }
        ans += cost[i]
    }
    return ans
}

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(), cost.end());
        int ans = 0, take = 0;
        for (int i = (int)cost.size() - 1; i >= 0; --i) {
            ++take;
            if (take == 3) {
                take = 0;
                continue;
            }
            ans += cost[i];
        }
        return ans;
    }
};

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort()
        ans = 0
        take = 0
        for i in range(len(cost) - 1, -1, -1):
            take += 1
            if take == 3:
                take = 0
                continue
            ans += cost[i]
        return ans

/**
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(cost) {
  cost.sort((a, b) => a - b);
  let ans = 0, take = 0;
  for (let i = cost.length - 1; i >= 0; i--) {
    take++;
    if (take === 3) {
      take = 0;
      continue;
    }
    ans += cost[i];
  }
  return ans;
};

中文

思路

要让优惠最大，免费的糖应该尽量贵，但它必须是每组三个里最便宜的那个。把价格降序后，每三个一组，前两个付费，第三个免费即可。

复杂度

时间复杂度：O(n log n)。空间复杂度：O(1) 额外空间（原地排序）。

代码标签（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        int ans = 0;
        int take = 0;
        for (int i = cost.length - 1; i >= 0; i--) {
            take++;
            if (take == 3) {
                take = 0;
                continue;
            }
            ans += cost[i];
        }
        return ans;
    }
}

func minimumCost(cost []int) int {
    sort.Ints(cost)
    ans, take := 0, 0
    for i := len(cost)-1; i >= 0; i-- {
        take++
        if take == 3 {
            take = 0
            continue
        }
        ans += cost[i]
    }
    return ans
}

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(), cost.end());
        int ans = 0, take = 0;
        for (int i = (int)cost.size() - 1; i >= 0; --i) {
            ++take;
            if (take == 3) {
                take = 0;
                continue;
            }
            ans += cost[i];
        }
        return ans;
    }
};

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort()
        ans = 0
        take = 0
        for i in range(len(cost) - 1, -1, -1):
            take += 1
            if take == 3:
                take = 0
                continue
            ans += cost[i]
        return ans

/**
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(cost) {
  cost.sort((a, b) => a - b);
  let ans = 0, take = 0;
  for (let i = cost.length - 1; i >= 0; i--) {
    take++;
    if (take === 3) {
      take = 0;
      continue;
    }
    ans += cost[i];
  }
  return ans;
};