The “Candy” problem on LeetCode

This is a classic algorithmic problem that can be solved using various approaches, such as greedy algorithms or dynamic programming. Here’s a brief overview of the problem and a common solution strategy

Problem Statement:

Given an array of integers representing the ratings of children in a line, you need to distribute candy to these children such that each child receives at least one candy and children with a higher rating get more candies than their neighbors. You need to minimize the total number of candies distributed.

Input: [1, 0, 2]
Output: 5
Explanation: The minimum number of candies given to the children are [2, 1, 2], which sums up to 5.

Approach:

A common strategy to solve this problem is to use two passes over the ratings array. In the first pass, you start by initializing an array with all elements set to 1 (since each child should get at least one candy). Then, you iterate over the ratings array from left to right and adjust the number of candies allocated based on the ratings relative to their neighbors.

Similarly, in the second pass, you iterate from right to left and adjust the number of candies allocated again. This ensures that you satisfy both conditions: each child gets at least one candy, and children with higher ratings get more candies than their neighbors.

1. Initialize an array candies[] with all elements set to 1.
2. Iterate over the ratings array from left to right:
   - If the current rating is greater than the previous one, update candies[i] = candies[i-1] + 1.
3. Iterate over the ratings array from right to left:
   - If the current rating is greater than the next one, update candies[i] = max(candies[i], candies[i+1] + 1).
4. Return the sum of candies[].

Complexity Analysis:

• Time complexity: O(n) where n is the number of elements in the ratings array.
• Space complexity: O(n) since we are using an additional array of size n to store the number of candies allocated to each child.

You can implement this approach in your preferred programming language and submit it to LeetCode to solve the problem.

Java implementation of the solution approach for the “Candy” problem on LeetCode:

public class CandyProblem {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        
        // Initialize all candies to 1
        Arrays.fill(candies, 1);
        
        // Scan from left to right
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        // Scan from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        
        // Calculate total candies
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }
        
        return totalCandies;
    }

    public static void main(String[] args) {
        CandyProblem candyProblem = new CandyProblem();
        int[] ratings = {1, 0, 2};
        System.out.println("Minimum number of candies: " + candyProblem.candy(ratings));
    }
}