There are N children standing in a line. Each child is assigned a rating value.

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.


What is the minimum candies you must give?

Example 1:


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


Example 2:


Input: [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.

Difficulty: interview

Starter code:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        

Solutions:
class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
 
         if not ratings:
             return 0
 
         total, pre, decrease = 1, 1, 0
         for i in range(1, len(ratings)):
             if ratings[i] >= ratings[i-1]:
                 if decrease > 0:
                     total += (1+decrease)*decrease // 2
                     if pre <= decrease:
                         total += decrease+1-pre
                     decrease, pre = 0, 1
                 if ratings[i] == ratings[i-1]:
                     total += 1
                     pre = 1
                 else:
                     pre += 1
                     total += pre
             else:
                 decrease += 1
 
         if decrease > 0:
             total += (1 + decrease) * decrease // 2
             if pre <= decrease:
                 total += decrease + 1 - pre
         return total


class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         current_min = 1
         current_max = 1
         desc_len = 1
         cnt = 1
         for i in range(1, len(ratings)):
             if ratings[i] < ratings[i - 1]:
                 if current_min == 1:
                     if desc_len >= current_max:
                         cnt += desc_len + 1
                     else:
                         cnt += desc_len
                 else:
                     current_max = current_min
                     current_min = 1
                     cnt += 1
                 desc_len += 1
             elif ratings[i] > ratings[i - 1]:
                 current_min += 1
                 current_max = current_min
                 cnt += current_min
                 desc_len = 1
             else:
                 cnt += 1
                 current_min = 1
                 current_max = 1
                 desc_len = 1
         return cnt

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         current_min = 1
         current_max = 1
         desc_len = 1
         cnt = 1
         for i in range(1, len(ratings)):
             if ratings[i] < ratings[i - 1]:
                 if current_min == 1:
                     cnt += desc_len
                     if desc_len < current_max:
                         cnt -= 1
                 else:
                     current_max = current_min
                     current_min = 1
                 desc_len += 1
             elif ratings[i] > ratings[i - 1]:
                 current_min += 1
                 current_max = current_min
                 cnt += current_min - 1
                 desc_len = 1
             else:
                 current_min = 1
                 current_max = 1
                 desc_len = 1
             cnt += 1
         return cnt

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         n = len(ratings)
         result = [1] * n
         
         for i in range(n-1):
             if ratings[i+1]> ratings[i]:
                 result[i+1] = result[i] + 1
         
         for i in range(n-1,0,-1):
             if ratings[i-1] > ratings[i]:
                 result[i-1] = max(result[i]+1, result[i-1])
                 
         return sum(result)

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         candy = [1 for i in range(len(ratings))]
         
         for i in range(1, len(ratings)):
             if ratings[i] > ratings[i - 1]:
                 candy[i] = candy[i - 1] + 1
         
         for i in range(len(ratings) -1)[::-1]:
             if ratings[i] > ratings[i + 1]:
                 candy[i] = max(candy[i], candy[i + 1] + 1)
                 
         return sum(candy)

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         if not ratings: return 0
         if len(ratings) == 1: return 1
         l2r = [1 for _ in ratings]
         for i in range(1, len(ratings)):
             if ratings[i] > ratings[i - 1]:
                 l2r[i] = l2r[i - 1] + 1
         res = l2r[-1]
         for i in range(len(ratings) - 2, -1, -1):
             if ratings[i] > ratings[i + 1]:
                 l2r[i] = max(l2r[i], l2r[i + 1] + 1)
             res += l2r[i]
         return res

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         if not ratings: return 0
         if len(ratings) == 1: return 1
         l2r = [1 for _ in ratings]
         r2l = [1 for _ in ratings]
         for i in range(1, len(ratings)):
             if ratings[i] > ratings[i - 1]:
                 l2r[i] = l2r[i - 1] + 1
         for i in range(len(ratings) - 2, -1, -1):
             if ratings[i] > ratings[i + 1]:
                 r2l[i] = r2l[i + 1] + 1
         res = 0
         for i in range(len(ratings)):
             res += max(l2r[i], r2l[i])
         return res

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         candies = [0] * len(ratings)
         
         from_left = [1] * len(ratings)
         cur_less_than = 1
         for idx in range(1, len(ratings)):
             if ratings[idx-1] < ratings[idx]:
                 cur_less_than += 1
             else:
                 cur_less_than = 1
             from_left[idx] = cur_less_than
         
         from_right = [1] * len(ratings)
         cur_less_than = 1
         idx = len(ratings)-2
         while idx >= 0:
             if ratings[idx+1] < ratings[idx]:
                 cur_less_than += 1
             else:
                 cur_less_than = 1
             from_right[idx] = cur_less_than
             idx -= 1
             
         for idx in range(0, len(ratings)):
             candies[idx] = max(from_left[idx], from_right[idx])
             
         return sum(candies)

class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         candies = [0] * len(ratings)
         # min candies at idx i = max of
         # 1) (number of decreasing ratings to the left) + 1
         # 2) (number of decreasing ratings to the right) + 1
         # By definition number after end of decreasing sequence will be greater than the end
         # => both sides of end of decreasing sequence will be greater than the rating at the end
         # => the min number of candies at the end of the decreasing sequence is 1
         # => min number of candies at the (end-n) of the decreasing sequence is 1+n        
         from_left = [1] * len(ratings)
         cur_less_than = 1
         for idx in range(1, len(ratings)):
             if ratings[idx-1] < ratings[idx]:
                 cur_less_than += 1
             else:
                 cur_less_than = 1
             from_left[idx] = cur_less_than
         
         from_right = [1] * len(ratings)
         cur_less_than = 1
         idx = len(ratings)-2
         while idx >= 0:
             if ratings[idx+1] < ratings[idx]:
                 cur_less_than += 1
             else:
                 cur_less_than = 1
             from_right[idx] = cur_less_than
             idx -= 1
             
         for idx in range(0, len(ratings)):
             candies[idx] = max(from_left[idx], from_right[idx])
             
         return sum(candies)