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 atleast one candy.
	Children with a higher rating get more candies than neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
 
Example 1:
Input:
N = 3
ratings [ ] = {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:
N = 3
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 statisfies the above two conditions.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minCandy() which takes the interger N and integer array ratings[ ] as parameters and returns the minimum number of candies you need to have to distribute the candies to the children.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤  5*10^{4}
0 ≤ ratings_{i} ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Data structures

Divide and conquer

Starter code: #User function Template for python3



class Solution:

    def minCandy(self, N, ratings):

        # Code here

Solutions:
class Solution:

	def minCandy(self, N, ratings):
		L = [1] * len(ratings)
		R = [1] * len(ratings)
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				L[i] += L[i - 1]
		for i in range(len(ratings) - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				R[i] += R[i + 1]
		cnd = 0
		for i in range(len(ratings)):
			cnd += max(L[i], R[i])
		return cnd


class Solution:

	def minCandy(self, N, ratings):
		candies = [1] * N
		for i in range(1, N):
			if ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
				candies[i] = candies[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
				candies[i] = candies[i + 1] + 1
		return sum(candies)


class Solution:

	def minCandy(self, n, ratings):
		candies = [1] * n
		for i in range(1, n):
			if ratings[i] > ratings[i - 1]:
				candies[i] = candies[i - 1] + 1
		for i in range(n - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				candies[i] = max(candies[i], candies[i + 1] + 1)
		return sum(candies)


class Solution:

	def minCandy(self, N, ratings):
		left = [1] * (N + 1)
		right = [1] * (N + 1)
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				left[i] = left[i - 1] + 1
		for j in range(N - 2, -1, -1):
			if ratings[j] > ratings[j + 1]:
				right[j] = right[j + 1] + 1
		su = 0
		for i in range(0, N):
			su += max(right[i], left[i])
		return su


class Solution:

	def minCandy(self, N, ratings):
		left_candy = [1 for i in range(N)]
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				left_candy[i] = left_candy[i - 1] + 1
		right_candy = 1
		for j in range(N - 2, -1, -1):
			if ratings[j] > ratings[j + 1]:
				right_candy += 1
				left_candy[j] = max(left_candy[j], right_candy)
			else:
				right_candy = 1
		sum1 = 0
		for i in range(0, N):
			sum1 += left_candy[i]
		return sum1


class Solution:

	def minCandy(self, N, ratings):
		c = [1] * N
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				c[i] = c[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				c[i] = max(c[i], c[i + 1] + 1)
		res = 0
		for t in c:
			res += t
		return res


class Solution:

	def minCandy(self, N, ratings):
		left = [1] * len(ratings)
		right = [1] * len(ratings)
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				left[i] += left[i - 1]
		for i in range(len(ratings) - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				right[i] += right[i + 1]
		ans = 0
		for i in range(len(ratings)):
			ans += max(left[i], right[i])
		return ans


class Solution:

	def minCandy(self, N, ratings):
		left = [1] * N
		right = [1] * N
		res = [0] * N
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				left[i] = 1 + left[i - 1]
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				right[i] = 1 + right[i + 1]
		for i in range(N):
			res[i] = max(left[i], right[i])
		return sum(res)


class Solution:

	def minCandy(self, N, ratings):
		candies = [1 for i in range(len(ratings))]
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				candies[i] = candies[i - 1] + 1
		for i in range(len(ratings) - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				candies[i] = max(candies[i], candies[i + 1] + 1)
		ans = sum(candies)
		return ans


class Solution:

	def minCandy(self, N, ratings):
		l = [1 for _ in range(N)]
		r = [1 for _ in range(N)]
		for i in range(1, N):
			if ratings[i] > ratings[i - 1] and l[i] <= l[i - 1]:
				l[i] = l[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1] and r[i] <= r[i + 1]:
				r[i] = r[i + 1] + 1
		ans = 0
		for i in range(N):
			ans += max(l[i], r[i])
		return ans


class Solution:

	def minCandy(self, N, ratings):
		arr = [1 for i in range(N)]
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				arr[i] = max(arr[i], arr[i - 1] + 1)
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				arr[i] = max(arr[i], arr[i + 1] + 1)
		return sum(arr)


class Solution:

	def minCandy(self, N, ratings):
		left = [1] * N
		right = [1] * N
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				left[i] = left[i - 1] + 1
			if ratings[N - 1 - i] > ratings[N - i]:
				right[N - 1 - i] = right[N - i] + 1
		s = 0
		for i in range(N):
			if left[i] > right[i]:
				s += left[i]
			else:
				s += right[i]


class Solution:

	def minCandy(self, N, ratings):
		left = [1] * N
		for i in range(1, N):
			if ratings[i] > ratings[i - 1]:
				left[i] += left[i - 1]
		right = [1] * N
		for i in range(N - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				right[i] += right[i + 1]
		cand = [0] * N
		s = 0
		for i in range(N):
			cand[i] = max(left[i], right[i])
			s += cand[i]
		return s


class Solution:

	def minCandy(self, N, arr):
		left = [1] * len(arr)
		right = [1] * len(arr)
		res = []
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				left[i] = left[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				right[i] = right[i + 1] + 1
		for i in range(N):
			res.append(max(left[i], right[i]))
		return sum(res)


class Solution:

	def minCandy(self, N, ratings):
		candies = [1] * N
		prev_r = float('inf')
		for (i, r) in enumerate(ratings):
			if r > prev_r:
				candies[i] = candies[i - 1] + 1
			prev_r = r
		prev_r = float('inf')
		for i in reversed(range(N)):
			r = ratings[i]
			if r > prev_r:
				candies[i] = max(candies[i], candies[i + 1] + 1)
			prev_r = r
		return sum(candies)


class Solution:

	def minCandy(self, N, arr):
		n = len(arr)
		left = [1] * n
		right = [1] * n
		for i in range(1, len(arr)):
			if arr[i - 1] < arr[i]:
				left[i] += left[i - 1]
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				right[i] += right[i + 1]
		total = 0
		for i in range(len(arr)):
			total += max(left[i], right[i])
		return total


class Solution:

	def minCandy(self, N, ratings):
		L2R = [1 for i in range(len(ratings))]
		R2L = [1 for i in range(len(ratings))]
		ratings2 = ratings[::-1]
		total = 0
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				L2R[i] = L2R[i - 1] + 1
			if ratings2[i] > ratings2[i - 1]:
				R2L[i] = R2L[i - 1] + 1
		R2L = R2L[::-1]
		for i in range(len(ratings)):
			total += max(L2R[i], R2L[i])
		return total


class Solution:

	def minCandy(self, N, ratings):
		arr = ratings
		n = N
		sum = 0
		ans = [1] * n
		if n == 1:
			return 1
		for i in range(n - 1):
			if arr[i + 1] > arr[i]:
				ans[i + 1] = ans[i] + 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1] and ans[i] <= ans[i + 1]:
				ans[i] = ans[i + 1] + 1
			sum += ans[i]
		sum += ans[n - 1]
		return sum


class Solution:

	def minCandy(self, N, arr):
		s = 0
		ans = [1] * N
		if N == 1:
			return 1
		for i in range(N - 1):
			if arr[i] < arr[i + 1]:
				ans[i + 1] = ans[i] + 1
		for i in range(N - 2, -1, -1):
			if arr[i] > arr[i + 1] and ans[i] <= ans[i + 1]:
				ans[i] = ans[i + 1] + 1
			s += ans[i]
		s += ans[N - 1]
		return s


class Solution:

	def minCandy(self, N, rat):
		l2r = [1] * N
		r2l = [1] * N
		for i in range(1, N):
			if rat[i] > rat[i - 1]:
				l2r[i] = l2r[i - 1] + 1
		for i in range(N - 2, -1, -1):
			if rat[i] > rat[i + 1]:
				r2l[i] = r2l[i + 1] + 1
		total = 0
		for i in range(N):
			total += max(l2r[i], r2l[i])
		return total