Kids With the Greatest Number of Candies - Video Solutions

Problem Overview: You are given an integer array candies where candies[i] represents the number of candies each kid has, and an integer extraCandies. For every kid, check if giving them all the extra candies would make their total at least as large as the current maximum among all kids. Return a boolean array indicating which kids could end up with the greatest number.

The key observation: a kid can have the greatest number of candies if candies[i] + extraCandies >= max(candies). The entire problem reduces to identifying the current maximum and comparing each value against it.

Approach 1: Brute Force Comparison (O(n²) time, O(1) space)

For each kid, temporarily assume they receive extraCandies. Then iterate through the entire array to verify whether any other kid still has more candies. If none do, that kid qualifies for the result array. This approach uses nested iteration: the outer loop selects a kid and the inner loop checks every other kid. No additional data structures are required beyond the result list, so auxiliary space remains O(1) (excluding output).

This method demonstrates the core logic clearly but performs unnecessary repeated scans of the array. Every candidate forces a full comparison against all other values. With n kids, that leads to n × n comparisons, resulting in O(n²) time complexity.

Approach 2: One-Pass Conditional Check (O(n) time, O(1) space)

A more efficient strategy computes the maximum value in the array first. Once you know maxCandies, the problem becomes a simple condition check: for each index i, evaluate candies[i] + extraCandies >= maxCandies. If true, that kid could reach or exceed the current maximum after receiving the extra candies.

The algorithm works in two lightweight passes. The first pass scans the array to find the maximum value. The second pass evaluates the condition for each kid and builds the boolean result list. Both passes are linear, so the total runtime is O(n), while space overhead remains O(1) aside from the output.

This pattern appears frequently in array problems: compute a global statistic (like maximum or minimum) and reuse it during a second traversal. Compared to naive nested comparisons, the improvement from O(n²) to O(n) is significant even for moderately sized inputs.

Recommended for interviews: Interviewers expect the maximum-scan strategy. The brute force approach shows you understand the condition being checked, but the optimized solution demonstrates awareness of redundant work and how to remove it. Recognizing when a global value (like a maximum) can simplify repeated comparisons is a common optimization pattern in array, brute-force, and greedy-style reasoning problems.