Candy

LeetCode 135: Candy Solution & Explanation

Problem Overview

TL;DR: Sort the children by their ratings in ascending order and process them sequentially, assigning each child the minimum candies required based on their already-processed lower-rated neighbors.

The problem asks us to distribute candies to n children standing in a line, where each child has a specific rating. The distribution must satisfy two rules: every child receives at least one candy, and any child with a higher rating than their immediate neighbor must receive more candies than that neighbor. We must find the minimum total number of candies required to satisfy these constraints for LeetCode 135.

Brute Force Approach for Candy

The naive approach involves repeatedly iterating through the array of children and fixing any violations of the candy distribution rules. We start by giving every child 1 candy. Then, we scan the array. If a child has a higher rating than a neighbor but not more candies, we increment their candy count to match the neighbor plus one. We repeat this full scan until a pass completes with no changes.

1# Pseudo-code for Brute Force
2candies = [1] * n
3has_changed = True
4while has_changed:
5    has_changed = False
6    for i from 0 to n-1:
7        # Check left neighbor
8        if i > 0 and ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]:
9            candies[i] = candies[i-1] + 1
10            has_changed = True
11        # Check right neighbor
12        if i < n-1 and ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
13            candies[i] = candies[i+1] + 1
14            has_changed = True
15return sum(candies)

Time Complexity: $O(N^2)$. In the worst case (e.g., a strictly increasing sequence like [1, 2, 3, 4, ...]), updates might propagate one step at a time, requiring $N$ passes for an array of size $N$. Why it fails: The constraints allow n up to $2 \times 10^4$. An $O(N^2)$ solution involves up to $4 \times 10^8$ operations, which results in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Greedy - Sorting Based

1. Initialization: Create a candies array of size n initialized to 1. Every child gets at least one candy.
2. Sort Indices: Create a list of indices 0 to n-1 and sort them based on the ratings at those indices. We process from the lowest rating to the highest.
3. Iterate Sorted Indices: Loop through the sorted indices. For each index i:
   • Check the left neighbor (i-1): If ratings[i] > ratings[i-1], ensure candies[i] is at least candies[i-1] + 1.
   • Check the right neighbor (i+1): If ratings[i] > ratings[i+1], ensure candies[i] is at least candies[i+1] + 1.
   • Update candies[i] to the maximum required value.
4. Result: Sum the candies array.

By processing in sorted order, whenever we check a neighbor with a lower rating, that neighbor's candy count is guaranteed to be final. Neighbors with higher ratings are ignored for now (they will handle the constraint when it's their turn in the sorted loop).

Execution Flow

Consider ratings = [1, 0, 2].

1. Init: candies = [1, 1, 1].
2. Sort Indices:
   • (Rating 0, Index 1)
   • (Rating 1, Index 0)
   • (Rating 2, Index 2)
   • Sorted Order: [1, 0, 2]
3. Process Index 1 (Rating 0):
   • Left neighbor (Index 0, Rating 1): Rating 0 is not > 1. Ignore.
   • Right neighbor (Index 2, Rating 2): Rating 0 is not > 2. Ignore.
   • candies[1] remains 1.
4. Process Index 0 (Rating 1):
   • Left neighbor: None.
   • Right neighbor (Index 1, Rating 0): Rating 1 > 0.
   • Constraint: candies[0] must be > candies[1].
   • Update: candies[0] = max(1, candies[1] + 1) = 2.
5. Process Index 2 (Rating 2):
   • Left neighbor (Index 1, Rating 0): Rating 2 > 0.
   • Constraint: candies[2] must be > candies[1].
   • Update: candies[2] = max(1, candies[1] + 1) = 2.
6. Final Sum: 2 + 1 + 2 = 5.

Proof of Correctness

Let $C(i)$ be the number of candies for child $i$. The algorithm is correct if for every $i$, $C(i) \ge 1$ and if $ratings[i] > ratings[j]$ (where $j$ is a neighbor), then $C(i) > C(j)$.

1. Base Case: All $C(i)$ are initialized to 1, satisfying the minimum requirement.
2. Inductive Step: We iterate through indices $i$ in non-decreasing order of $ratings[i]$.
   • If $ratings[i] > ratings[neighbor]$, the $neighbor$ must have appeared earlier in the sorted list (since $ratings[neighbor] < ratings[i]$).
   • Therefore, $C(neighbor)$ is already computed and final.
   • Setting $C(i) = \max(C(i), C(neighbor) + 1)$ satisfies the constraint immediately.
   • If $ratings[i] <= ratings[neighbor]$, no constraint is imposed on $C(i)$ by this neighbor.
3. Termination: After iterating all children, all local constraints where $ratings[i] > ratings[neighbor]$ have been explicitly satisfied.

Pattern Reuse Notes

The Greedy - Sorting Based pattern used here is a powerful technique for satisfying local constraints dependent on relative magnitude.

• LeetCode 455: Assign Cookies: Uses sorting to match the smallest cookie to the child with the minimum greed factor, optimizing satisfaction.
• LeetCode 406: Queue Reconstruction by Height: Sorts people by height to determine their correct insertion positions, processing tallest to shortest (or vice versa).
• LeetCode 1029: Two City Scheduling: Sorts by the difference in costs between two options to make the optimal greedy choice for the global sum.

Reference Implementation

C++ Solution for LeetCode 135

1#include <vector>
2#include <numeric>
3#include <algorithm>
4
5class Solution {
6public:
7    int candy(std::vector<int>& ratings) {
8        int n = ratings.size();
9        // Store pairs of (rating, index)
10        std::vector<std::pair<int, int>> sorted_indices(n);
11        for (int i = 0; i < n; ++i) {
12            sorted_indices[i] = {ratings[i], i};
13        }
14        
15        // Sort based on ratings
16        std::sort(sorted_indices.begin(), sorted_indices.end());
17        
18        std::vector<int> candies(n, 1);
19        
20        for (const auto& p : sorted_indices) {
21            int rating = p.first;
22            int i = p.second;
23            
24            // Check left neighbor
25            if (i > 0 && ratings[i] > ratings[i - 1]) {
26                candies[i] = std::max(candies[i], candies[i - 1] + 1);
27            }
28            
29            // Check right neighbor
30            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
31                candies[i] = std::max(candies[i], candies[i + 1] + 1);
32            }
33        }
34        
35        return std::accumulate(candies.begin(), candies.end(), 0);
36    }
37};

Java Solution for LeetCode 135

1import java.util.Arrays;
2import java.util.Comparator;
3import java.util.stream.IntStream;
4
5class Solution {
6    public int candy(int[] ratings) {
7        int n = ratings.length;
8        Integer[] indices = new Integer[n];
9        for (int i = 0; i < n; i++) {
10            indices[i] = i;
11        }
12        
13        // Sort indices based on rating values
14        Arrays.sort(indices, Comparator.comparingInt(i -> ratings[i]));
15        
16        int[] candies = new int[n];
17        Arrays.fill(candies, 1);
18        
19        for (int i : indices) {
20            // Check left neighbor
21            if (i > 0 && ratings[i] > ratings[i - 1]) {
22                candies[i] = Math.max(candies[i], candies[i - 1] + 1);
23            }
24            
25            // Check right neighbor
26            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
27                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
28            }
29        }
30        
31        int totalCandies = 0;
32        for (int c : candies) {
33            totalCandies += c;
34        }
35        return totalCandies;
36    }
37}

Python Solution for LeetCode 135

1class Solution:
2    def candy(self, ratings: List[int]) -> int:
3        n = len(ratings)
4        # Create a list of indices sorted by their corresponding rating
5        sorted_indices = sorted(range(n), key=lambda i: ratings[i])
6        
7        candies = [1] * n
8        
9        for i in sorted_indices:
10            # Check left neighbor
11            if i > 0 and ratings[i] > ratings[i - 1]:
12                candies[i] = max(candies[i], candies[i - 1] + 1)
13            
14            # Check right neighbor
15            if i < n - 1 and ratings[i] > ratings[i + 1]:
16                candies[i] = max(candies[i], candies[i + 1] + 1)
17                
18        return sum(candies)