devLap

LeetCode #135: Candy

javascript dev.to

LeetCode Question - 135. Candy 🍭

About the Series

Problem-solving is a key skill set for any tech-related stuff you might be working on.

When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.

So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. 🚀

Earlier in this series: LeetCode #376: Wiggle Subsequence.

Problem Statement

Candy 🍭

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second, and third child with 2, 1, 2 candies respectively.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second, and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4

Video Explanation

Watch on YouTube

Solution

Algorithm

  1. Create a new array of candies with all initial values as at least one candy will be given to all the children.
  2. Now, traverse from the left of the array to the right of the array and increase the count of the candies to be given based on the rating of the neighbor child. In this iteration, we are incrementing the candies count only based on the left neighbor.
  3. Now, repeat the above from right to left and also store the sum.
  4. Finally return the total sum of candies. 🍭

Code in JS 🧑‍💻

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
  var candies = Array(ratings.length).fill(1);
  for (var i = 1; i < ratings.length; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }
  var sum = candies[ratings.length - 1];
  for (var i = ratings.length - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
    sum += candies[i];
  }
  return sum;
};
Enter fullscreen mode Exit fullscreen mode

Time Complexity : O(n)

Space Complexity: O(n)

You can find me on the web 🌍

Add your solution or approach in the comments below. Also, show your love by Sharing the blog. 🤗

“Life is like riding a bicycle. To keep your balance, you must keep moving.”

~ Albert Einstein

Solving the problem is only half the interview. I built TechInView, a voice-first AI mock interview platform. An interviewer speaks, challenges your approach, and watches you code live, then hands you a five-dimension scorecard. Try a mock interview.

Originally published on July 4, 2022 at souravdey.space.

Source: dev.to

arrow_back Back to Tutorials