DEV Community

Cover image for LeetCode Challenge: 135. Candy - JavaScript Solution ๐Ÿฌ
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

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].
Enter fullscreen mode Exit fullscreen mode

Example 2

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

๐Ÿ† 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);
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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]

Candy
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

Image of Timescale

๐Ÿš€ pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applicationsโ€”without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post โ†’

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up