5ms O(n) AC solution with comments


  • 3
    M

    public int candy(int[] ratings) {

    int candies[] = new int[ratings.length];
    candies[0] = 1;//no need to initialize whole array, we only need the first for the first pass
    
    // left to right
    for (int i = 1; i < ratings.length; i++) {
        // left neighbor
        if (ratings[i - 1] < ratings[i])
    	candies[i] = candies[i - 1] + 1;
        else
    	candies[i] = 1;
    }
    
    int candy = candies[ratings.length - 1]; // second pass, now we add up the candies for the return value
    
    // right to left
    for (int i = ratings.length - 2; i >= 0; i--) {
        // right neighbor
        if (ratings[i + 1] < ratings[i] && (candies[i] < candies[i + 1] + 1))//right neighbor could have lower have less candy than i already has
    	candies[i] = candies[i + 1] + 1;
    
        candy += candies[i];
    }
    return candy;
    

    }


Log in to reply
 

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