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?


  • 0
    K

    @cdai : we can classify this problem in DP also.. since every cell value(candies) depends on adjacent neighbour


  • 0
    K

    @keshavk said in Very Simple Java Solution with detail explanation:
    here in this code if rating of earlier person is greater ,then we are comparing the candies....so if the number of candies of earlier one is "EQUAL OR LESS THAN" the i+ith....then it should be incremented....
    below in inner if statement condition there shouldn't be "<=" ???

    i think it should be there.. thanks

    if(ratings[i-1]>ratings[i])
    {
    if(a[i-1]<=(a[i]+1))
    {
    a[i-1]=a[i]+1;
    }
    }


Log in to reply
 

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