Java O(n) solution


  • 1
    public int candy(int[] ratings) {
      if (ratings == null || ratings.length == 0) return 0;
      
      int n = ratings.length;
      
      // a[i] stores the num of candies of i-th kid
      int[] a = new int[n]; a[0] = 1;
      
      // scan from left to right
      for (int i = 1; i < n; i++)
        a[i] = (ratings[i] > ratings[i - 1]) ? a[i - 1] + 1 : 1;
      
      // scan from right to left
      int sum = a[n - 1];
      
      for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1])
          a[i] = Math.max(a[i], a[i + 1] + 1);
            
        sum += a[i];
      }
      
      return sum;
    }

  • 0
    M

    How can you make sure only two scans are needed? Is it any chance that after your scan right to left, there is still candy assigned wrong?


  • 0

    Hi mo10, when we scan from left to right, we make sure that the kid who has higher rating on the right always has (at least) one more candy than the kid on his/her left-hand side.

    When we scan from right to left, notice that we use Math.max( ) to make sure that the number of candy will not decrease, so that it won't break what we have done in the first scan.

    If you want to ask why we need to scan from right to left? We can take a look at the following example, let's say we have some kids and their ratings are:

    [1, 2, 5, 4, 3, 2, 1]

    after scan from left to right, we get the following candies for each kid:

    [1, 2, 3, 1, 1, 1, 1]

    as you can see the kid who has rating 4 should have more candies than the kid who has rating 3, to fix that, we need to scan from right to left, finally we get the candies:

    [1, 2, 5, 4, 3, 2, 1]


  • 0
    M

    Great! Understood. Thank you very much ! It seems you are really good at dynamic programming problems. Most of the elegant solutions to DP problems I found are yours~


Log in to reply
 

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