Introduction

The Candy problem is a classic greedy algorithm interview question frequently asked by companies such as NPCI, Amazon, Google, and Microsoft.

The challenge is to distribute candies among children according to their ratings while minimizing the total number of candies distributed.

Although the problem appears straightforward, finding an optimal solution with O(n) time complexity and O(1) auxiliary space requires careful observation.

In this article, we'll explore the intuition, derive the optimal greedy approach, and implement it in Java.

Problem Statement

There are n children standing in a line.

Each child has a rating represented by:

Code
arr[i]

You must distribute candies according to the following rules.

Rule 1

Every child must receive at least one candy.

Rule 2

If a child has a higher rating than an adjacent neighbor, they must receive more candies than that neighbor.

Return the minimum number of candies required.

Example 1

Input

Code
arr = [1, 0, 2]

Distribution

Code
Ratings : 1  0  2
Candies : 2  1  2

Total

Code
2 + 1 + 2 = 5

Output

Code
5

Example 2

Input

Code
arr = [1, 2, 2]

Distribution

Code
Ratings : 1  2  2
Candies : 1  2  1

Total

Code
1 + 2 + 1 = 4

Output

Code
4

Understanding the Problem

Consider:

Code
Ratings:
1 2 3 4

Since ratings continuously increase:

Code
Candies:
1 2 3 4

Total:

Code
10

Now consider:

Code
Ratings:
4 3 2 1

Candies must become:

Code
4 3 2 1

Total:

Code
10

The problem becomes interesting when both increasing and decreasing sequences appear together.

Brute Force Approach

One approach is repeatedly updating candy counts until all constraints are satisfied.

Example:

Code
1 3 2 4

Keep adjusting candies until valid.

Complexity

Code
O(n²)

This is too slow for:

Code
n = 100000

Better Observation

Every rating pattern consists of:

Example:

Code
1 2 3 2 1

Visualization:

Code
      3
    /   \
  2       2
1           1

This forms a mountain.

If we can count candies contributed by increasing and decreasing slopes, we can solve the problem efficiently.

Two-Pass Solution

A common solution uses two arrays.

Left to Right

If the current rating is greater than the previous rating:

Java
left[i] = left[i - 1] + 1;

Right to Left

If the current rating is greater than the next rating:

Java
right[i] = right[i + 1] + 1;

Final Candy Count

Java
max(left[i], right[i])

This works in:

Code
Time  : O(n)
Space : O(n)

But the expected solution requires:

Code
Space : O(1)

Optimal Greedy Idea

Instead of storing arrays, we track:

Code
up   = length of increasing slope
down = length of decreasing slope
peak = longest increasing slope before descent

The idea:

Visual Example

Ratings

Code
1 2 3 2 1

Increasing Slope

Code
1 2 3

Candies

Code
1 + 2 + 3 = 6

Decreasing Slope

Code
2 1

Candies

Code
2 + 1 = 3

Total

Code
9

Greedy State Variables

We maintain:

Code
up
down
peak
candies

up

Current increasing sequence length.

down

Current decreasing sequence length.

peak

Length of the latest increasing sequence.

candies

Total candies distributed.

Algorithm

Initialize:

Java
candies = 1;
up = 0;
down = 0;
peak = 0;

Case 1: Increasing

Code
arr[i] > arr[i - 1]

Increase:

Java
up++;
peak = up;
down = 0;

Add:

Code
1 + up

candies.

Case 2: Equal Ratings

Code
arr[i] == arr[i - 1]

Reset all slopes:

Java
up = 0;
down = 0;
peak = 0;

Give:

Code
1

candy.

Case 3: Decreasing

Code
arr[i] < arr[i - 1]

Increase:

Java
down++;

Add candies according to the decreasing slope.

If:

Code
down > peak

we need one extra candy for the peak child.

Dry Run

Input

Code
[1,0,2]

Start:

Code
candies = 1

i = 1

Code
0 < 1

Down slope:

Code
down = 1

Add:

Code
1

Peak correction:

Code
down > peak

Add:

Code
1

Total:

Code
3

i = 2

Code
2 > 0

Up slope:

Code
up = 1

Add:

Code
2

Total:

Code
5

Answer:

Code
5

Java Solution (O(n) Time, O(1) Space)

Java
class Solution {

    public int minCandy(int[] arr) {

        int n = arr.length;

        if (n == 1)
            return 1;

        int candies = 1;

        int up = 0;
        int down = 0;
        int peak = 0;

        for (int i = 1; i < n; i++) {

            if (arr[i] > arr[i - 1]) {

                up++;
                peak = up;
                down = 0;

                candies += 1 + up;
            }
            else if (arr[i] == arr[i - 1]) {

                up = 0;
                down = 0;
                peak = 0;

                candies += 1;
            }
            else {

                up = 0;
                down++;

                candies += down;

                if (down > peak) {
                    candies += 1;
                }
            }
        }

        return candies;
    }
}

Alternative Two-Array Solution

This solution is easier to understand.

Java
class Solution {

    public int minCandy(int[] arr) {

        int n = arr.length;

        int[] candies = new int[n];

        Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                candies[i] =
                    Math.max(candies[i],
                             candies[i + 1] + 1);
            }
        }

        int total = 0;

        for (int c : candies) {
            total += c;
        }

        return total;
    }
}

Complexity Analysis

Optimal Greedy Solution

Time Complexity

Code
O(n)

Single traversal.

Space Complexity

Code
O(1)

Only a few variables are used.

Two-Array Solution

Time Complexity

Code
O(n)

Space Complexity

Code
O(n)

An extra array is required.

Why the Greedy Solution Works

The algorithm treats ratings as a sequence of:

Instead of storing candy counts for every child, it directly calculates how many candies each slope contributes.

By tracking:

Code
up
down
peak

we ensure:

Thus, the solution achieves:

Code
Time  : O(n)
Space : O(1)

which matches the expected complexity.

Conclusion

The Candy problem is an excellent greedy algorithm challenge because a simple-looking requirement hides several edge cases involving increasing and decreasing rating sequences.

The key insight is to view ratings as mountains and valleys:

Using this approach, we obtain an optimal solution with:

Code
Time Complexity: O(n)
Space Complexity: O(1)