Kids With the Greatest Number of Candies - Problem

Array Easy

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the i-th kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the i-th kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Input & Output

Example 1 — Basic Case

$ Input: candies = [2,3,5,1,3], extraCandies = 3

› Output: [true,true,true,false,true]

💡 Note: Maximum is 5. Kid 0: 2+3=5≥5 ✓, Kid 1: 3+3=6≥5 ✓, Kid 2: 5+3=8≥5 ✓, Kid 3: 1+3=4<5 ✗, Kid 4: 3+3=6≥5 ✓

Example 2 — All Can Be Greatest

$ Input: candies = [4,2,1,1,2], extraCandies = 1

› Output: [true,false,false,false,false]

💡 Note: Maximum is 4. Only kid 0: 4+1=5≥4 can be greatest. Others: 2+1=3<4, 1+1=2<4

Example 3 — Large Extra Candies

$ Input: candies = [12,1,12], extraCandies = 10

› Output: [true,true,true]

💡 Note: Maximum is 12. Kid 0: 12+10=22≥12 ✓, Kid 1: 1+10=11<12 ✗, Kid 2: 12+10=22≥12 ✓

Constraints

2 ≤ candies.length ≤ 100
1 ≤ candies[i] ≤ 100
1 ≤ extraCandies ≤ 50

Visualization

Tap to expand

Asked in

M Microsoft 15 a Amazon 12

The key insight is to find the maximum candy count first, then check if each kid can reach this maximum with extra candies. The optimal approach uses two passes: one to find the maximum and another to build the result. Time: O(n), Space: O(1).

Common Approaches

✓ Memoization

⏱️ Time: N/A Space: N/A

Brute Force - Check All Kids Each Time

⏱️ Time: O(n²) Space: O(1)

For each kid, we add the extra candies to their count and then compare against every other kid to see if they have the maximum. This requires checking all kids for each position.

Optimal - Find Max Once

⏱️ Time: O(n) Space: O(1)

Instead of comparing against all kids repeatedly, we first find the maximum number of candies any kid currently has. Then we check if each kid with extra candies can reach or exceed this maximum.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

bool* solution(int* candies, int candiesSize, int extraCandies) {
    int max_candies = candies[0];
    for (int i = 1; i < candiesSize; i++) {
        if (candies[i] > max_candies) {
            max_candies = candies[i];
        }
    }
    
    bool* result = malloc(candiesSize * sizeof(bool));
    
    for (int i = 0; i < candiesSize; i++) {
        if (candies[i] + extraCandies >= max_candies) {
            result[i] = true;
        } else {
            result[i] = false;
        }
    }
    
    return result;
}

int main() {
    char line1[1000], line2[100];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int candies[1000];
    int candiesSize;
    parseArray(line1, candies, &candiesSize);
    int extraCandies = atoi(line2);
    
    bool* result = solution(candies, candiesSize, extraCandies);
    
    printf("[");
    for (int i = 0; i < candiesSize; i++) {
        if (i > 0) printf(",");
        printf(result[i] ? "true" : "false");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ Linear Space

125.0K Views

Medium Frequency

~10 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen