Problem Statement
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.
Intuition 1
gyan_pelo There is no minimum set before, it is important to know previous candy value, can we normalize the ratings, that can be one way to get minimum candy value, the difference between rating doesn’t matter, just for greater rating than neighbours, the current child will get more candy so it can be one more than neighbours, what if left neighbour has less rating and right neighbour has more rating? Assign one candy to first element, move to next, assign one and check if neighbours are smaller, if yes left candy + 1 else move to next element. Need to check the output to decide next approach.
- attempt_before_checking_answer Theconstraints allow value only upto 2000 so itstime_complexity of answer may be high.
Approach 1
rating = [5, 20, 10, 4, 100, 1]