Simple O(n) Java solution with comments


  • 58
    public int candy(int[] ratings) {
        int candies[] = new int[ratings.length];        
        Arrays.fill(candies, 1);// Give each child 1 candy 
        	
        for (int i = 1; i < candies.length; i++){// Scan from left to right, to make sure right higher rated child gets 1 more candy than left lower rated child
            if (ratings[i] > ratings[i - 1]) candies[i] = (candies[i - 1] + 1);
        }
         
        for (int i = candies.length - 2; i >= 0; i--) {// Scan from right to left, to make sure left higher rated child gets 1 more candy than right lower rated child
    	    if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], (candies[i + 1] + 1));
        }
        
        int sum = 0;        
        for (int candy : candies)  
        	sum += candy;        
        return sum;
    }

  • 1
    C

    New kind of solution. Good one. :)


  • 0
    S
    This post is deleted!

  • 0
    A

    Best solution I have seen so far


  • 0
    H

    Best that I've ever seen


  • 1
    T

    Can you please provide a proof of correctness please - I couldn't come up with one :(


  • 0

    I came up with the same solution, I think you can combine the second and third pass since candies[i] is already finalized in the second pass.


Log in to reply
 

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