This code is solving a variation of the **"Candy Distribution...

August 23, 2025 at 09:04 AM

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        
        // Step 1: give everyone 1 candy
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }

        boolean changed = true;

        // Step 2: keep looping until no changes
        while (changed) {
            changed = false;

            for (int i = 0; i < n; i++) {
                // Check left neighbor
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    changed = true;
                }

                // Check right neighbor
                if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    changed = true;
                }
            }
        }

        // Step 3: sum all candies
        int total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }
}

This code is solving a variation of the "Candy Distribution Problem", which is a common algorithmic problem.

What the code does:

The goal is to distribute a minimum number of candies to children sitting in a line based on their "ratings" such that:

Each child gets at least one candy.
Any child with a higher rating than their immediate neighbors (either left or right) gets more candies than that neighbor.

Key Steps:

Initialize candies for all children: Each child is initially given exactly one candy (candies[i] = 1).
Iteratively adjust candy distribution:
- The algorithm loops until there are no more changes made to the candies array (stabilizing the solution).
- For each child:
  - Compare the child's ratings[i] with their left neighbor (ratings[i - 1]) and right neighbor (ratings[i + 1]).
  - If ratings[i] > ratings[i - 1], ensure candies[i] > candies[i - 1] by setting candies[i] = candies[i - 1] + 1.
  - Similarly, if ratings[i] > ratings[i + 1], ensure candies[i] > candies[i + 1].
- If any change is made, the changed flag is set to true to continue iterating.
Sum up total candies: After all adjustments, the candies array will contain the minimum number of candies that satisfy the above conditions. The total number of candies is computed and returned.

Complexity:

The solution iterates through the array multiple times until the distribution stabilizes. In the worst case, this is O(n²), where n is the number of children.

Example:

Input: ratings = [1, 0, 2]

Execution:

Initialize: candies = [1, 1, 1]
Iteration 1:
- For i = 2: ratings[2] > ratings[1] → candies[2] = candies[1] + 1 = 2
- For i = 1: ratings[1] < ratings[2] (no change)
- For i = 0: ratings[0] > ratings[1] → candies[0] = candies[1] + 1 = 2
- Result: candies = [2, 1, 2]
Stabilized (no further changes).

Output: total = 2 + 1 + 2 = 5

The function returns 5, which is the minimum number of candies satisfying the rules.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr