Log inSign up
hardLeetCodeNot Started

Candy

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

There are n children standing in a line. Each child has an integer rating given in ratings.

You must distribute candies according to two rules: 1. Each child must get at least 1 candy. 2. Children with a higher rating than their immediate neighbor (left or right) must get more candies than that neighbor.

Return the minimum total number of candies needed.

Example 1 · Example 1: Valley in Middle:

Input: ratings = [1, 0, 2]
Output: 5
Explanation: Candies given: [2, 1, 2]. Total = 2 + 1 + 2 = 5.\nChild 0 (rating 1) > Child 1 (rating 0) -> gets 2 candies.\nChild 2 (rating 2) > Child 1 (rating 0) -> gets 2 candies.

Example 2 · Example 2: Equal Ratings:

Input: ratings = [1, 2, 2]
Output: 4
Explanation: Candies given: [1, 2, 1]. Total = 1 + 2 + 1 = 4.\nChild 2 has equal rating to Child 1, so does not need more candies than Child 1.

Constraints:

  • 1 <= ratings.length <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand decoupling bidirectional dependencies into forward and backward passes.
  • Master the two-pass greedy array pattern.
  • Analyze the single-pass slope counting technique in O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array of values where each element must be greater than its neighbors if rating is higher.
  • Local relative order constraints affecting both adjacent sides.
  • Minimizing total assigned sum.

Algorithmic Decision Tree:

  • Decouple bidirectional neighbor dependencies into two unidirectional passes: forward and backward.

Connected Patterns:

Trapping Rain WaterGas StationWiggle Subsequence

1. Brute Force — Iterative Conflict Resolution

Intuition

Start with 1 candy per child. Loop over the array repeatedly: if ratings[i] > ratings[i-1] and candies[i] <= candies[i-1], increase candies[i]. If ratings[i] > ratings[i+1] and candies[i] <= candies[i+1], increase candies[i]. Repeat until a full pass makes zero updates.

When to apply: When N <= 50.

Algorithm

  1. Step 1: Initialize candies array of size N with all 1s.
  2. Step 2: Loop hasChanged = true.
  3. Step 3: While hasChanged: set hasChanged = false. For each i, check left and right neighbor constraints. If violated, update candies[i] and set hasChanged = true.
  4. Step 4: Sum all elements in candies and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8public:
9 int candy(vector<int>& ratings) {
10 int n = ratings.size();
11 vector<int> candies(n, 1);
12 bool changed = true;
13
14 while (changed) {
15 changed = false;
16 for (int i = 0; i < n; ++i) {
17 if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
18 candies[i] = candies[i - 1] + 1;
19 changed = true;
20 }
21 if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
22 candies[i] = candies[i + 1] + 1;
23 changed = true;
24 }
25 }
26 }
27 return accumulate(candies.begin(), candies.end(), 0);
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> ratings = {1, 0, 2};
34 cout << "Min candies: " << sol.candy(ratings) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2) — Strictly decreasing rating sequence causes O(N) passes of length N, taking O(N2) total operations.
  • Space complexity: O(N) — Candies array of size N.

Why Brute Force Doesn't Scale:

A descending ladder of 20,000 ratings takes 20,000 passes, reaching 4 * 108 operations. The two-pass O(N) solution runs in < 5ms.

For N = 20,000: Two-Pass O(N) requires exactly 40,000 operations, executing in ~2ms.

2. Better — Two-Pass Greedy (Left & Right Pass)

Intuition

Initialize an array with 1 candy for each child. Forward pass (i from 1 to N-1): if ratings[i] > ratings[i-1], candies[i] = candies[i-1] + 1. Backward pass (i from N-2 down to 0): if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1] + 1). Sum all values.

When to apply: Standard and most readable approach in interviews.

Algorithm

  1. Step 1: Initialize candies array of size N with all 1s.
  2. Step 2: Iterate i from 1 to N - 1: if ratings[i] > ratings[i - 1], candies[i] = candies[i - 1] + 1.
  3. Step 3: Iterate i from N - 2 down to 0: if ratings[i] > ratings[i + 1], candies[i] = max(candies[i], candies[i + 1] + 1).
  4. Step 4: Sum all elements in candies array and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int candy(vector<int>& ratings) {
11 int n = ratings.size();
12 vector<int> candies(n, 1);
13
14 for (int i = 1; i < n; ++i) {
15 if (ratings[i] > ratings[i - 1]) {
16 candies[i] = candies[i - 1] + 1;
17 }
18 }
19
20 for (int i = n - 2; i >= 0; --i) {
21 if (ratings[i] > ratings[i + 1]) {
22 candies[i] = max(candies[i], candies[i + 1] + 1);
23 }
24 }
25
26 return accumulate(candies.begin(), candies.end(), 0);
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> ratings = {1, 0, 2};
33 cout << "Min candies: " << sol.candy(ratings) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Two linear passes of length N.
  • Space complexity: O(N) — Candies array of size N.

3. Optimal — Single-Pass Slope Tracking (O(1) Space)

Intuition

Interpret the ratings array as alternating ascending slopes, descending slopes, and flat segments. On an up-slope, candy increases by 1 each step. On a down-slope, each step adds to total candies, and if the down-slope exceeds peak height, the peak child must retroactively receive an extra candy. On a flat segment, reset slope to 1.

When to apply: When memory is strictly constrained to O(1) auxiliary space.

Algorithm

  1. Step 1: If n == 0 return 0. Initialize total = 1, up = 0, down = 0, peak = 0.
  2. Step 2: For i from 1 to n - 1: compare ratings[i] with ratings[i - 1].
  3. Step 3: If ratings[i] > ratings[i - 1]: up++, peak = up, down = 0, total += 1 + up.
  4. Step 4: If ratings[i] == ratings[i - 1]: up = 0, down = 0, peak = 0, total += 1.
  5. Step 5: If ratings[i] < ratings[i - 1]: down++, up = 0, total += 1 + down + (down > peak ? 1 : 0).
  6. Step 6: Return total.

Interactive Trace for Candy (Two-Pass)

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Left-to-right pass
Visual state
Values and pointers at this exact step
pointers
S
1
1
2
0
1
2
↑ L2R_complete
Check / comparison
ratings[2] > ratings[1] (2 > 0)
Decision / next transition
Set candies[2] = 2. Array becomes [1, 1, 2].
Why this step matters

Step 1: Left-to-right pass. For i=2, rating 2 > 0, so candies[2] = candies[1] + 1 = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int candy(vector<int>& ratings) {
9 int n = ratings.size();
10 if (n == 0) return 0;
11
12 int total = 1;
13 int up = 0, down = 0, peak = 0;
14
15 for (int i = 1; i < n; ++i) {
16 if (ratings[i] > ratings[i - 1]) {
17 up++;
18 peak = up;
19 down = 0;
20 total += 1 + up;
21 } else if (ratings[i] == ratings[i - 1]) {
22 up = 0;
23 down = 0;
24 peak = 0;
25 total += 1;
26 } else {
27 down++;
28 up = 0;
29 total += 1 + (down - 1) + (down > peak ? 1 : 0);
30 }
31 }
32 return total;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> ratings = {1, 0, 2};
39 cout << "Min candies: " << sol.candy(ratings) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) — Single pass of length N with O(1) state variables.
  • Space complexity: O(1) auxiliary — Uses only integers: up, down, peak, and total.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Iterative Violation FixingO(N^2)O(N)Initialize all children with 1 candy. Repeatedly loop through array and increase candy count when a rating violation is found, until no changes occur.Repeated full-array scans.
2.Better — Two-Pass Greedy (Left & Right)O(N)O(N)Initialize array with 1. Left-to-right pass updates candies[i] when ratings[i] > ratings[i-1]. Right-to-left pass updates candies[i] = max(candies[i], candies[i+1] + 1) when ratings[i] > ratings[i+1].Auxiliary array allocation.
3.Optimal — Single-Pass Peak-Valley Slope TrackingOptimalO(N)O(1) auxiliaryTrack contiguous rising slopes (up), falling slopes (down), and previous peak heights in a single pass to accumulate candies in O(1) space.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Giving more candies to equal ratings

If ratings[i] == ratings[i-1], the problem does NOT mandate more candies; 1 is sufficient.

Updating in a single pass without slope logic

A single left-to-right pass cannot know how long a future descending sequence will be, leading to undercounted candies for peaks.

Crucial Edge Cases to Validate:

  • N = 1 — Single child gets exactly 1 candy; returns 1.
  • All equal ratings (e.g. [3, 3, 3]) — Rule states equal neighbors do NOT require strictly more candies, so each child gets 1 candy; returns N.
  • Strictly increasing (e.g. [1, 2, 3, 4]) — Candies: 1, 2, 3, 4; sum is N * (N + 1) / 2.
  • Strictly decreasing (e.g. [4, 3, 2, 1]) — Candies: 4, 3, 2, 1; sum is N * (N + 1) / 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the two-pass algorithm first: it is easy to understand, easy to code correctly under pressure, and has optimal O(N) time.
  2. Mention the O(1) slope tracking approach as a space-optimization follow-up.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the two-pass approach take max(leftPass[i], rightPass[i]) instead of min or sum?

Back to DSA Sheet