Candy Distribution Problem: Greedy Two-Pass Solution Explained with Examples

The Candy Distribution Problem is a popular algorithmic challenge often asked in coding interviews and competitive programming contests. It tests your ability to apply greedy algorithms effectively. The most efficient and widely accepted approach for solving this problem is the two-pass greedy solution, which guarantees both correctness and minimal candy allocation.

Table of Contents

Problem Statement

You are given an array ratings[] where each element represents the performance rating of a child standing in a line. You need to distribute candies to these children such that:

Each child gets at least one candy.
Any child with a higher rating than their immediate neighbor must get more candies.

Your goal is to determine the minimum number of candies needed to satisfy the above conditions.

Greedy Two-Pass Solution: Key Idea

The greedy approach works by scanning the children in two passes:

Left to Right Pass: Ensure that each child with a higher rating than their left neighbor gets more candies.
Right to Left Pass: Ensure that each child with a higher rating than their right neighbor also gets more candies, while preserving the conditions from the first pass.

After these two traversals, we sum up the candies given to find the final minimum distribution.

Step-by-Step Example

Consider the ratings array:

ratings = [1, 0, 2]

Initialization

Every child gets at least one candy:

candies = [1, 1, 1]

Left to Right Pass

Compare ratings[1] = 0 with ratings[0] = 1 → No change.
Compare ratings[2] = 2 with ratings[1] = 0 → Child at index 2 gets more candies: candies[2] = candies[1] + 1 = 2.

candies = [1, 1, 2]

Right to Left Pass

Compare ratings[1] = 0 with ratings[2] = 2 → No change.
Compare ratings[0] = 1 with ratings[1] = 0 → Child at index 0 gets more candies: candies[0] = candies[1] + 1 = 2.

candies = [2, 1, 2]

Total Candies

Sum = 2 + 1 + 2 = 5

So the minimum candies needed = 5.

Python Implementation

Here is the Python implementation of the greedy two-pass approach:


def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    
    # Left to right pass
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    
    # Right to left pass
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    
    return sum(candies)

# Example
print(candy([1,0,2]))  # Output: 5
print(candy([1,2,2]))  # Output: 4

Visual Example: Ratings [1, 2, 2]

Step-by-step execution:

ratings = [1, 2, 2]
Initial candies = [1, 1, 1]

Pass 1: [1, 2, 1]
Pass 2: [1, 2, 1] (No changes)
Total = 4

Complexity Analysis

Time Complexity: O(n) because we traverse the ratings array twice.
Space Complexity: O(n) due to storing candies distribution.

Key Insights

The two-pass greedy method ensures all children satisfy both left and right conditions.
It minimizes the total candies by always giving the smallest valid number.
Unlike brute-force methods, it avoids unnecessary adjustments and ensures optimality.

Try It Yourself

You can experiment with different rating arrays to visualize how candies are distributed. For example:


print(candy([5, 3, 4, 5, 2]))  
print(candy([1, 3, 4, 5, 2, 2, 1]))

Conclusion

The Candy Distribution Problem demonstrates how a two-pass greedy strategy can solve a seemingly complex problem in O(n) time. With its blend of simplicity and efficiency, this approach is a must-learn technique for coding interviews and algorithm design.