Candy Problem in Java – Greedy O(n) Time and O(1) Space Solution

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:

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

arr = [1, 0, 2]

Distribution

Ratings : 1  0  2
Candies : 2  1  2

Total

2 + 1 + 2 = 5

Output

Example 2

Input

arr = [1, 2, 2]

Distribution

Ratings : 1  2  2
Candies : 1  2  1

Total

1 + 2 + 1 = 4

Output

Understanding the Problem

Consider:

Ratings:
1 2 3 4

Since ratings continuously increase:

Candies:
1 2 3 4

Total:

Now consider:

Ratings:
4 3 2 1

Candies must become:

4 3 2 1

Total:

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:

1 3 2 4

Keep adjusting candies until valid.

Complexity

O(n²)

This is too slow for:

n = 100000

Better Observation

Every rating pattern consists of:

Increasing slopes
Decreasing slopes
Flat regions

Example:

1 2 3 2 1

Visualization:

      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:

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

Right to Left

If the current rating is greater than the next rating:

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

Final Candy Count

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

This works in:

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

But the expected solution requires:

Space : O(1)

Optimal Greedy Idea

Instead of storing arrays, we track:

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

The idea:

Increasing ratings form an arithmetic progression.
Decreasing ratings form an arithmetic progression.
The peak should not be counted twice.

Visual Example

Ratings

1 2 3 2 1

Increasing Slope

1 2 3

Candies

1 + 2 + 3 = 6

Decreasing Slope

2 1

Candies

2 + 1 = 3

Total

Greedy State Variables

We maintain:

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:

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

Case 1: Increasing

arr[i] > arr[i - 1]

Increase:

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

Add:

1 + up

candies.

Case 2: Equal Ratings

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

Reset all slopes:

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

Give:

candy.

Case 3: Decreasing

arr[i] < arr[i - 1]

Increase:

down++;

Add candies according to the decreasing slope.

If:

down > peak

we need one extra candy for the peak child.

Dry Run

Input

[1,0,2]

Start:

candies = 1

i = 1

0 < 1

Down slope:

down = 1

Add:

Peak correction:

down > peak

Add:

Total:

i = 2

2 > 0

Up slope:

up = 1

Add:

Total:

Answer:

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

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.

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

O(n)

Single traversal.

Space Complexity

O(1)

Only a few variables are used.

Two-Array Solution

Time Complexity

O(n)

Space Complexity

O(n)

An extra array is required.

Why the Greedy Solution Works

The algorithm treats ratings as a sequence of:

Ascending slopes
Descending slopes
Flat regions

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

By tracking:

up
down
peak

we ensure:

Higher-rated children always receive more candies.
Peak elements are counted correctly.
Minimum candies are distributed.

Thus, the solution achieves:

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:

Increasing slopes contribute growing candy counts.
Decreasing slopes contribute descending candy counts.
Peak elements require special handling.

Using this approach, we obtain an optimal solution with:

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