Very Simple Java Solution with detail explanation


  • 39
    K
    We take ratings array as [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
    

    In the given problem each student will have at least 1 candy. So distribute 1 candy to each.

    ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
    candies:     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    

    Now traverse the array from left to right. If the rating of (n+1) child is greater than (n) child then set the candy of (n+1) child as one candy more than the (n) child candies.

    ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
    candies:     [1, 2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 1]
    

    Now traverse the array from right to left. If the (n) child rating is more than (n+1) child and (n) child candies is less than one more than (n+1) child candies then update the candies of (n) child as 1+ (n+1) candies.

    ratings:     [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
    candies:     [1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 2, 1]
    

    Total minimum candies: 23

    public int candy(int[] ratings) {
            int sum=0;
            int[] a=new int[ratings.length];
            for(int i=0;i<a.length;i++)
            {
                a[i]=1;
            }
            for(int i=0;i<ratings.length-1;i++)
            {
                if(ratings[i+1]>ratings[i])
                {
                    a[i+1]=a[i]+1;
                }
            }
            for(int i=ratings.length-1;i>0;i--)
            {
                if(ratings[i-1]>ratings[i])
                {
                    if(a[i-1]<(a[i]+1))
                    {
                        a[i-1]=a[i]+1;
                    }
                }
            }
            for(int i=0;i<a.length;i++)
            {
                sum+=a[i];
            }
            return sum;
        }

  • 1
    D

    I am inspired by your solution, and figure out that: every local minimum point is always 1. and there is a hill between two local minimum points. along the hill to the top is simply increasing. the peak of the hill needs some consideration but also simple.


  • 2

    Great! I'm really wondering why this is correct and what category should this kinda of problem fall into? Just a brainteaser? Thanks for your sharing!


  • 0
    J

    @cdai said in Very Simple Java Solution with detail explanation:

    Great! I'm really wondering why this is correct and what category should this kinda of problem fall into? Just a brainteaser? Thanks for your sharing!

    I have the same question too, this greedy approach ensures correctness, but does this solution achieve minimum?


Log in to reply
 

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