LeetCode Challenge: 135. Candy - JavaScript Solution 🍬

Top Interview 150

Distributing candies while respecting certain rules is a great problem to test greedy algorithms. Let’s solve LeetCode 135: Candy, where the goal is to determine the minimum number of candies needed to satisfy the given constraints.

---

🚀 Problem Description

You are given an array ratings, where each element represents a child’s rating. You need to distribute candies to these children while meeting the following rules:

1. Each child must get at least 1 candy.
2. Children with higher ratings must receive more candies than their neighbors. Return the minimum number of candies required.

---

💡 Examples

Example 1

Input: ratings = [1,0,2]  
Output: 5  
Explanation: The distribution is [2,1,2].

Example 2

Input: ratings = [1,2,2]  
Output: 4  
Explanation: The distribution is [1,2,1].  

---

🏆 JavaScript Solution

This problem can be efficiently solved using a two-pass greedy approach:

1. Start by assigning 1 candy to everyone.
2. Traverse the array left-to-right to ensure each child has more candies than the one on the left if their rating is higher.
3. Traverse the array right-to-left to ensure each child has more candies than the one on the right if their rating is higher.

---

Implementation

var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    return candies.reduce((total, num) => total + num, 0);
};

---

🔍 How It Works

1. Initialize candies:
   • Every child starts with 1 candy because each must have at least one.
2. Left-to-right pass:
   • If a child’s rating is higher than their left neighbor, give them more candies than the left neighbor.
3. Right-to-left pass:
   • If a child’s rating is higher than their right neighbor, ensure they have more candies than the right neighbor.
   • Use Math.max() to ensure both conditions are satisfied.
4. Sum up candies:
   • Calculate the total candies needed after both passes.

---

🔑 Complexity Analysis

• > Time Complexity: O(n), where n is the number of children.
  • The two passes (left-to-right and right-to-left) each take O(n).
• > Space Complexity: O(n), for the candies array.

---

📋 Dry Run

Input: ratings = [1,0,2]

Output: 5

---

✨ Pro Tips for Interviews

1. Understand constraints: Clarify the rules and confirm if ratings can have duplicates (yes, they can).
2. Explain the two-pass approach: Highlight why two passes are necessary to satisfy both left and right neighbor conditions.
3. Edge cases:
   • Single child (ratings = [1] → 1).
   • Increasing or decreasing ratings (ratings = [1,2,3] → 6).

---

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 Gas Station- JavaScript Solution

How would you optimize this further? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!