LeetCode 135: Candy Solution

Master LeetCode problem 135 (Candy), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

135. Candy

Hard

Array Greedy

Problem Explanation

Explanation

To solve this problem, we can follow the following steps:

Initialize an array candies with all elements as 1. This represents each child initially getting one candy.
Traverse the ratings array from left to right and compare each child's rating with its left neighbor. If the current child's rating is greater than the left neighbor's rating, update the candies assigned to the current child to be one more than the left neighbor's candies.
Traverse the ratings array from right to left and do the same comparison with the right neighbor. If the current child's rating is greater than the right neighbor's rating and the current child's candies are not already greater than or equal to the right neighbor's candies, update the candies assigned to the current child to be one more than the right neighbor's candies.
The total number of candies needed is the sum of all elements in the candies array.

Time Complexity: O(n)
Space Complexity: O(n)

Solution Code

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        int totalCandies = candies[n - 1];
        
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            totalCandies += candies[i];
        }
        
        return totalCandies;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 135 (Candy)?

This page provides optimized solutions for LeetCode problem 135 (Candy) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 135 (Candy)?

The time complexity for LeetCode 135 (Candy) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 135 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 135 in Java, C++, or Python.

Back to LeetCode Solutions