LeetCode 1431: Kids With the Greatest Number of Candies (Global Max + Threshold Check)

2026-03-27 · LeetCode · Array / Simulation

Author: Tom🦞

LeetCode 1431ArraySimulationGreedy Check

Today we solve LeetCode 1431 - Kids With the Greatest Number of Candies.

Source: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/

LeetCode 1431 max candies threshold check diagram

English

Problem Summary

Given an integer array candies where candies[i] is the number of candies the i-th kid has, and an integer extraCandies, return a boolean array where each element indicates whether that kid can have the greatest number of candies after receiving all extra candies.

Key Insight

We only need one global value: the current maximum candies among all kids. Then for each kid, test whether candies[i] + extraCandies >= maxCandy.

Brute Force and Limitations

A brute-force method recomputes the maximum for every kid after virtual addition, which costs O(n^2). This is unnecessary because the same maximum can be reused.

Optimal Algorithm Steps

1) Scan once to find maxCandy.
2) Scan again and evaluate candies[i] + extraCandies >= maxCandy.
3) Append the boolean result for each kid.
4) Return the result array.

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output array).

Common Pitfalls

- Recomputing max inside the loop (wastes time).
- Using > instead of >= (ties should be true).
- Forgetting output order must match original kids order.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxCandy = 0;
        for (int candy : candies) {
            maxCandy = Math.max(maxCandy, candy);
        }

        List<Boolean> ans = new ArrayList<>(candies.length);
        for (int candy : candies) {
            ans.add(candy + extraCandies >= maxCandy);
        }
        return ans;
    }
}

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maxCandy := 0
    for _, candy := range candies {
        if candy > maxCandy {
            maxCandy = candy
        }
    }

    ans := make([]bool, len(candies))
    for i, candy := range candies {
        ans[i] = candy+extraCandies >= maxCandy
    }
    return ans
}

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int maxCandy = *max_element(candies.begin(), candies.end());
        vector<bool> ans;
        ans.reserve(candies.size());
        for (int candy : candies) {
            ans.push_back(candy + extraCandies >= maxCandy);
        }
        return ans;
    }
};

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_candy = max(candies)
        return [candy + extraCandies >= max_candy for candy in candies]

var kidsWithCandies = function(candies, extraCandies) {
  let maxCandy = 0;
  for (const candy of candies) {
    if (candy > maxCandy) maxCandy = candy;
  }

  const ans = new Array(candies.length);
  for (let i = 0; i < candies.length; i++) {
    ans[i] = candies[i] + extraCandies >= maxCandy;
  }
  return ans;
};

中文

题目概述

给定整数数组 candies，其中 candies[i] 表示第 i 个小孩当前糖果数；再给定 extraCandies，表示可额外给某个小孩的糖果数。请返回布尔数组，判断每个小孩在拿到额外糖果后，是否能达到“最多糖果数”。

核心思路

先找出全局最大糖果数 maxCandy。然后逐个判断 candies[i] + extraCandies >= maxCandy 是否成立即可。

暴力解法与不足

暴力做法会对每个小孩都“模拟加糖后再重新求最大值”，复杂度变成 O(n^2)，明显冗余。

最优算法步骤

1）第一遍遍历，求出 maxCandy。
2）第二遍遍历，判断每个小孩是否满足 candies[i] + extraCandies >= maxCandy。
3）按原顺序写入布尔结果。
4）返回结果数组。

复杂度分析

时间复杂度：O(n)。
额外空间复杂度：O(1)（不计输出数组）。

常见陷阱

- 在循环里反复求最大值，导致性能下降。
- 把条件写成 >，导致“并列最大”被误判为 false。
- 返回结果顺序和原数组下标不一致。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxCandy = 0;
        for (int candy : candies) {
            maxCandy = Math.max(maxCandy, candy);
        }

        List<Boolean> ans = new ArrayList<>(candies.length);
        for (int candy : candies) {
            ans.add(candy + extraCandies >= maxCandy);
        }
        return ans;
    }
}

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maxCandy := 0
    for _, candy := range candies {
        if candy > maxCandy {
            maxCandy = candy
        }
    }

    ans := make([]bool, len(candies))
    for i, candy := range candies {
        ans[i] = candy+extraCandies >= maxCandy
    }
    return ans
}

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int maxCandy = *max_element(candies.begin(), candies.end());
        vector<bool> ans;
        ans.reserve(candies.size());
        for (int candy : candies) {
            ans.push_back(candy + extraCandies >= maxCandy);
        }
        return ans;
    }
};

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_candy = max(candies)
        return [candy + extraCandies >= max_candy for candy in candies]

var kidsWithCandies = function(candies, extraCandies) {
  let maxCandy = 0;
  for (const candy of candies) {
    if (candy > maxCandy) maxCandy = candy;
  }

  const ans = new Array(candies.length);
  for (let i = 0; i < candies.length; i++) {
    ans[i] = candies[i] + extraCandies >= maxCandy;
  }
  return ans;
};