LeetCode Q135: Candy

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?

	class Solution {
	public:
	int candy(vector<int>& ratings) {
	vector<int> forward(ratings.size(), 1);
	vector<int> backward(ratings.size(), 1);
	for(int i=1; i<ratings.size(); i++)
	if(ratings[i]>ratings[i-1]&&forward[i]<=forward[i-1])
	forward[i]=forward[i-1]+1;
	backward=forward;
	for(int i=ratings.size()-2; i>=0; i--)
	if(ratings[i]>ratings[i+1]&&backward[i]<=backward[i+1])
	backward[i]=backward[i+1]+1;
	int sum=0;
	for(int i=0; i<ratings.size(); i++)
	sum+=backward[i];
	return sum;
	}
	};

view raw Q135Candy.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int candy(vector<int>& ratings) {
	vector<int> candies(ratings.size(), 1);
	for(int i=1; i<ratings.size(); i++)
	candies[i] = ratings[i]>ratings[i-1]? candies[i-1]+1:candies[i];
	for(int i= ratings.size()-2; i>=0; i--)
	candies[i] = (ratings[i]>ratings[i+1]&&candies[i+1]+1>candies[i])? candies[i+1]+1:candies[i];
	int res=0;
	for(int i=0; i<ratings.size(); i++)
	res+=candies[i];
	return res;
	}
	};

view raw Q135.cpp hosted with ❤ by GitHub