Candy — Two-Pass Greedy
Sanjeev SharmaAdvertisement
Problem
Give at least 1 candy per child. Children with higher rating than neighbor get more candy. Minimize total.
Approach — Two Pass
Pass 1 (L→R): if rating[i] > rating[i-1], candy[i] = candy[i-1]+1. Pass 2 (R→L): if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1]+1).
Time: O(n) | Space: O(n)
Solutions
Python
class Solution:
def candy(self, ratings: list[int]) -> int:
n=len(ratings); candy=[1]*n
for i in range(1,n):
if ratings[i]>ratings[i-1]: candy[i]=candy[i-1]+1
for i in range(n-2,-1,-1):
if ratings[i]>ratings[i+1]: candy[i]=max(candy[i],candy[i+1]+1)
return sum(candy)
C++
class Solution {
public:
int candy(vector<int>& r){
int n=r.size(); vector<int> c(n,1);
for(int i=1;i<n;i++) if(r[i]>r[i-1]) c[i]=c[i-1]+1;
for(int i=n-2;i>=0;i--) if(r[i]>r[i+1]) c[i]=max(c[i],c[i+1]+1);
return accumulate(c.begin(),c.end(),0);
}
};
Complexity
- Time: O(n) | Space: O(n)
Advertisement
