One-pass constant space Java solution


  • 73
    S

    Hi guys!

    This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

    1. His/her rating is equal to the previous one -> give 1 candy.
    2. His/her rating is greater than the previous one -> give him (previous + 1) candies.
    3. His/her rating is less than the previous one -> don't know what to do yet, let's just count the number of such consequent cases.

    When we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

    Here's a pretty concise code below.


    public class Solution {
        public int candy(int[] ratings) {
            if (ratings == null || ratings.length == 0) return 0;
            int total = 1, prev = 1, countDown = 0;
            for (int i = 1; i < ratings.length; i++) {
                if (ratings[i] >= ratings[i-1]) {
                    if (countDown > 0) {
                        total += countDown*(countDown+1)/2; // arithmetic progression
                        if (countDown >= prev) total += countDown - prev + 1;
                        countDown = 0;
                        prev = 1;
                    }
                    prev = ratings[i] == ratings[i-1] ? 1 : prev+1;
                    total += prev;
                } else countDown++;
            }
            if (countDown > 0) { // if we were descending at the end
                total += countDown*(countDown+1)/2;
                if (countDown >= prev) total += countDown - prev + 1;
            }
            return total;
        }
    }
    

    Have a nice coding!


  • 0
    C

    very nice answer,thanks very much!


  • 1
    J

    nice ideas. I write a similar one using c++

        if (ratings.size() <= 1)
        return ratings.size();
    
        ratings.push_back(ratings.back()); // push last elements for easy computing
        int pre = 1, sum = 1;
        int len_decrease = 0;
        for (int i = 1; i < ratings.size(); ++i)
        {
            if (ratings[i] < ratings[i-1]) //if decreasing : count the length of decreasing segment
            {
                ++len_decrease;
                --pre;
            }
            else
            {
                if (len_decrease > 0) // if at the end of decreasing, compute sum candidate of the segment
                {
                    if (pre < 1)    // if length of decreasing segment is greater than the previous monotone segment
                        sum += (2+len_decrease)*(1+len_decrease)/2 - (len_decrease+pre);
                    else
                        sum += (1+len_decrease)*len_decrease/2;
                    pre = 1;
                    len_decrease = 0;
                }
                
                if (ratings[i] > ratings[i-1]) // if increasing
                    ++pre;
                else // if equal
                    pre = 1;
                sum += pre;
            }
        }
    
        return sum-1;

  • 5
    A

    This is efficient, but really difficult to understand. I wrote my blog for more explanation. Hope it helps to understand.


  • 0
    E

    haha...
    same as yours.


  • 0
    X

    Great job! I did the similar thing but failed to handle the desceding sequence properly. The way you treat the descending sequence as a whole and only add them & modify the peak once it ends is really nice.


  • 0
    F

    It's really clever to come up with this one-pass idea...


Log in to reply
 

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