1 pass solution O(n) complexity O(1) space


  • 0
    M

    basic idea is:
    if it's increasing ( ratings[i]> ratings[i-1]), increase by 1
    if it's decreasing, decrease by 1 each node and count the number decreasing, finally when it increasing or equal again, the candy will be c (may be negative), then compensate the delta:
    if(c <=0) sum+= num*(1-c);
    else sum += (num-1)*(1-c);

    public class Solution {
    public int candy(int[] ratings) {
        int c = 1;
        int sum  = 1;
        int num = 1;
        for(int i = 1; i < ratings.length; i ++){
            if( ratings[i]> ratings[i-1]) {   ////increasing
                if(num > 1){   ////compensate the delta
                    if(c <=0)
                    sum+= num*(1-c);
                    else
                        sum += (num-1)*(1-c);
                    c = 2;  ///reset for current increasing candy
                }
                else
                    c++;
                sum+=c;
                num = 1;
            }
            else if(ratings[i] == ratings[i-1]) {
                if(num > 1){   ////compensate the delta
                    if(c <=0)
                        sum+= num*(1-c);
                    else
                        sum += (num-1)*(1-c);
                }
                c=1;
                sum+=c;
                num = 1;
            }
            else{
                c--; //keep decreasing
                sum+=c;
                num++;
            }
            
        }
        if(num > 1){
            if(c <=0)
                sum+= num*(1-c);
            else
                sum += (num-1)*(1-c);
        }
        return sum;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.