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