c++ concise but tricky one-pass solution with explanation


  • 1
    Q

    Had the same so called mountain idea as Here, but struggled to get it right. Then realized I did not handle the first index of streaks right.
    Anyway following is the code

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if(ratings.size()==1) return 1;
            int inc=0, dec=0, res=0;
            
            for(int i=1; i<ratings.size(); i++)
            {
                if(ratings[i]>ratings[i-1]) //increasing
                {
                    //not max(dec,inc)+1 to skip the first inc index  if the previous streak is dec;
                    //since it already been counted;
                    if(dec>0)
                    {
                        res+=max(dec, inc);
                        dec=inc=0;
                    }
                    
                    inc++;
                    
                    res+=inc; 
                }
                else if(ratings[i]<ratings[i-1]) //decreasing
                {
                    dec++;
                    res+=dec;
                }
                else //equal
                {
                    // skip the first equal since it has already been counted by inc or dec;
                    if(dec || inc) 
                    {
                        res+=max(dec, inc)+1;
                        dec=inc=0;
                    }
                    else res+=1;
                }
            }
            
            if(dec || inc) res+=max(dec, inc)+1;
            else res+=1; //add last uncounted equal;
            
            return res;
            
        }
    };

Log in to reply
 

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