Skip to main content

Candy

Problem Description​

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.

Examples​

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.

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints​

  • n==ratings.lengthn == ratings.length
  • 1<=n<=2∗1041 <= n <= 2 * 10^4
  • 0<=ratings[i]<=2∗1040 <= ratings[i] <= 2 * 10^4

Solution for Candy Distribution Problem​

Intuition And Approach​

To solve this problem, we can use a greedy approach. We can start by assigning each child 1 candy. Then, we iterate over the ratings array twice, once from left to right and once from right to left, adjusting the number of candies as needed to satisfy the given conditions.

Code in Different Languages​

Written by @YourName
public class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];

// Initialize all candies to 1
for (int i = 0; i < n; i++) {
candies[i] = 1;
}

// Left to right pass
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}

// Right to left pass
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}

int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}

return totalCandies;
}

public static void main(String[] args) {
Solution solution = new Solution();
int[] ratings1 = {1, 0, 2};
int[] ratings2 = {1, 2, 2};

System.out.println(solution.candy(ratings1)); // Output: 5
System.out.println(solution.candy(ratings2)); // Output: 4
}
}

Complexity Analysis​

  • Time Complexity: O(n)O(n) where n is the number of children (length of the ratings array).
  • Space Complexity: O(n)O(n) for storing the candies array.

References​