Scale Engineer

Candy

Hard
#0135Time: O(n^2)Space: O(n)12 companies
Patterns
Greedy
Data structures
Array
Companies
AccentureFlipkartGoldman SachsMastercard

Prompt

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

 

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of satisfying the candy distribution rules. We start by giving each child one candy. Then, we make multiple passes over the children, correcting the number of candies whenever a rule is violated. We continue this process until a full pass occurs with no corrections needed, at which point we have found a stable and valid distribution.

Algorithm

  • Initialize a candies array of size n with all elements set to 1. This ensures every child gets at least one candy.
  • Use a boolean flag, hasChanged, to track if any updates are made in a pass through the array.
  • Repeatedly loop through the candies array as long as hasChanged is true.
  • In each pass:
    • Reset hasChanged to false.
    • Iterate through the children from left to right.
    • For each child i, check the two conditions:
      • If ratings[i] > ratings[i-1] and candies[i] <= candies[i-1], update candies[i] = candies[i-1] + 1 and set hasChanged = true.
      • If ratings[i] > ratings[i+1] and candies[i] <= candies[i+1], update candies[i] = candies[i+1] + 1 and set hasChanged = true.
  • The loop terminates when a full pass is completed with no changes to the candies array, which means all conditions are satisfied.
  • Finally, sum up all the values in the candies array to get the minimum total.

Walkthrough

The brute-force method involves initializing a candies array of the same size as ratings, with each child receiving one candy. We then enter a loop that continues as long as we are making changes to the candy allocation. Inside the loop, we iterate through each child and check if their candy allocation violates the rules with respect to their left and right neighbors. If a child has a higher rating than a neighbor but not more candies, we increment their candy count. This process is repeated until an entire pass over all children results in no changes, indicating that the rules are satisfied for everyone. The worst-case scenario for this approach is a long, strictly decreasing sequence of ratings, which would require O(n) passes, with each pass taking O(n) time.

public class Solution {    public int candy(int[] ratings) {        int n = ratings.length;        int[] candies = new int[n];        Arrays.fill(candies, 1);        boolean hasChanged = true;        while (hasChanged) {            hasChanged = false;            for (int i = 0; i < n; i++) {                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {                    candies[i] = candies[i - 1] + 1;                    hasChanged = true;                }                if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {                    candies[i] = candies[i + 1] + 1;                    hasChanged = true;                }            }        }        int totalCandies = 0;        for (int candy : candies) {            totalCandies += candy;        }        return totalCandies;    }}

Complexity

Time

O(n^2)

Space

O(n)

Trade-offs

Pros

  • Simple to understand and conceptualize.

Cons

  • Very inefficient, with a time complexity of O(n^2) in the worst case.

  • Likely to result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

public class Solution {    public int Candy(int[] ratings) {        int n = ratings.Length;        int[] left = new int[n];        int[] right = new int[n];        Array.Fill(left, 1);        Array.Fill(right, 1);        for (int i = 1; i < n; ++i) {            if (ratings[i] > ratings[i - 1]) {                left[i] = left[i - 1] + 1;            }        }        for (int i = n - 2; i >= 0; --i) {            if (ratings[i] > ratings[i + 1]) {                right[i] = right[i + 1] + 1;            }        }        int ans = 0;        for (int i = 0; i < n; ++i) {            ans += Math.Max(left[i], right[i]);        }        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem