Candy - Practice Coding Problems

Candy - Problem

Array Greedy Hard

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Input & Output

Example 1 — Basic Case

$ Input: ratings = [1,0,2]

› Output: 5

💡 Note: Child 0: rating=1, gets 2 candies (higher than right neighbor). Child 1: rating=0, gets 1 candy. Child 2: rating=2, gets 2 candies (higher than left neighbor). Total: 2+1+2=5

Example 2 — All Same Rating

$ Input: ratings = [1,2,2]

› Output: 4

💡 Note: Child 0: rating=1, gets 1 candy. Child 1: rating=2, gets 2 candies (higher than left). Child 2: rating=2, gets 1 candy (same as left, no constraint). Total: 1+2+1=4

Example 3 — Decreasing Sequence

$ Input: ratings = [5,4,3,2,1]

› Output: 15

💡 Note: Decreasing sequence requires candies [5,4,3,2,1] to satisfy neighbor constraints. Each child must have more candies than the right neighbor. Total: 5+4+3+2+1=15

Constraints

n == ratings.length
1 ≤ n ≤ 2 × 10⁴
-1000 ≤ ratings[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Ratings

Children with their performance ratings

Apply Constraints

Higher rated children need more candies than neighbors

Minimum Candies

Calculate minimum total candies needed

Key Takeaway

🎯 Key Insight: Use two-pass greedy to handle left and right neighbor constraints optimally

Asked in

G Google 45 a Amazon 38 f Facebook 32 🍎 Apple 28

The key insight is to handle neighbor constraints with two passes: left-to-right for increasing sequences, right-to-left for decreasing sequences. The optimal two-pass greedy approach ensures minimum candies while satisfying all constraints. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ One Pass Greedy with Peak/Valley Detection	O(n)	O(1)	Single pass using peak and valley detection to calculate minimum candies
Brute Force - Iterative Adjustment	O(n²)	O(n)	Repeatedly adjust candy counts until all constraints are satisfied
Two Pass Greedy	O(n)	O(n)	Left-to-right pass then right-to-left pass to handle all neighbor constraints

One Pass Greedy with Peak/Valley Detection — Algorithm Steps

Step 1: Scan array to identify peaks (local maxima) and valleys
Step 2: For increasing sequences, candies increase linearly from 1
Step 3: For decreasing sequences, candies decrease linearly to 1
Step 4: Handle peaks by taking maximum of left and right requirements

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Patterns

Identify increasing/decreasing sequences

Calculate On-the-Go

Add candies based on pattern length

Adjust Peaks

Handle overlapping sequences at peaks

Code -

solution.c — C

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

int solution(int* ratings, int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int total = 1; // First child gets 1 candy
    int up = 0;    // Length of increasing sequence
    int down = 0;  // Length of decreasing sequence
    int peak = 0;  // Height at peak
    
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) { // Increasing
            down = 0;
            up++;
            total += 1 + up;
            peak = up;
        } else if (ratings[i] < ratings[i-1]) { // Decreasing
            up = 0;
            down++;
            total += down;
            if (peak < down) {
                total++; // Adjust peak
            }
        } else { // Equal ratings
            up = down = peak = 0;
            total++;
        }
    }
    
    return total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int ratings[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        ratings[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(ratings, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array to detect patterns

✓ Linear Growth

Space Complexity

O(1)

Only uses variables to track current state, no extra array needed

✓ Linear Space

285.0K Views

Medium Frequency

~35 min Avg. Time

3.4K 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One Pass Greedy with Peak/Valley Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler