did all the test cases pass?

Interesting. I implemented both - dynamic and this solution and found that performance is about the same, but it varies - in some cases dynamic solution is better, while in others your solution is.

how many candies did you give to the first child??

I have same solution working on given testcases but it doesn't work for hidden ones. I scored just 5 :-(

can thi algo traverse 9,8,7,7,6,6,5,4,3,

i think no????

Please check out this blog http://stackandqueue.com/?p=108, it explains why standard solution actually works. Trick is to understand why local minimas will get 1 candy and then you can get candies for other students

I did the same. Is O(N), so is optimal.

This is excellent solution. Note that two testcases may fail due to size of the resulting sum: Int vs Long

But this gives me answer of second test case =20. Please explain. How do you explain the overlapping answers?

I solved it in the same manner. O(2xN) is O(N). This does not need DP at all.

here is an explanation: We basically have to find sequences of numbers which are always increasing and those which are decreasing. initialise a count array of length n with all 1. then whenever u see an increasing pattern, set the bigger number count = smaller number count + 1 while traversing the array forward. then traverse the array backwards and check for the same increasing pattern (which would be decreasing since we are traversing backward). but only do the bigger number count = smaller number count + 1 when (bigger number count <= smaller number count). this is because we might already have set the value to something bigger before while traversing forward. here is an example, array : 2 4 5 6 7 8 9 5 4 count : 1 2 3 4 5 6 7 2 1 count array can look like a mountain. increase then decrease the peak of the mountain (9 here) is determined by which slope is longer, left or right. that is why u have that check while traversing backards. try manually doing this and u will see why: array : 2 9 8 6 4 3 2 1 count : 1 7 6 5 4 3 2 1

My solution is simmilar to yours. Logic behind this is that if you make a graph between marking and index of child then local minima will always have 1(min) candy. Then next on both sides of local minima will have 1(min) + 1 candy and so on. This approach can be easily implemented by the method you mentioned above.

candies[0] = 1;
for(int i = 1; i < markings.length; i++) {
    candies[i] = (markings[i] > markings[i-1]) ? (candies[i-1] + 1) : 1;
}
for(int i = markings.length - 2; i >= 0; i--) {
    candies[i] = (markings[i] > markings[i+1] && (markings[i+1] + 1) > markings[i])
        ? (candies[i+1] + 1) : candies[i];
}

I did it in same way, and this is my explanation :

consider two arrays 'stairr'(for stair right) and 'stairl'(for stair left). Initialize it by 1.

stairr[i] contains number of consecutive decreasing elements(or ratings) on the right side of element 'i'(inclusive of element itself. So value will be >= 1). Similarly, we can define stairl[i].

Now, the reason I am using word stairs is because If we notice a candy value of particular element(or rating), it will depend on how many consecutive decreasing elements(or ratings) are on its left and right side. This 'consecutiveness' is like steps of stairs. More precisely, candy value will be maximum of both of these values. But why is it so? Because -

(i) suppose an element has stairr and stairl value 1. So we can comfortably assign its candy value as 1.

(ii) Otherwise, suppose and element 'i' has stairr[i] > stairl[i]. Now, bottom elements of both right stair and left stair will have value 1, using (i) part. We can observe that to minimize the no of candies given, each 'step up' on the stair should increase the value of candy number by 1, if possible. This can be achieved it candie value of element 'i' is stairr[i] and candy value of each element in right stair of 'i' will decrease by 1 as we go down untill it reaches the bottom, which will have value 1. Similarly, if stairl[i] > stairr[i], then candy value of element 'i' will be stairl[i].

(iii) What if two consecutive elements have equal value(or rating) ? If 'i' and 'i + 1' have equal rating, then element 'i' enforce no constraint on element 'i + 1', so it is just like as if there is no stair step on left of 'i + 1' or stairl[i + 1] = 1(just the element itself). Similarly, stairr[i] = 1.

This is exactly the right method because what we need to do is to take chunks of three at a time and compare the middle first with the value at left and then with the value at right and according to that increase the value of the middle value... In the technique discussed above when we are traversing left to right we are actually comapring the value of that middle part with its left value and when we are traversing from right to left we are actually comparing value of middle with its right value.

Same, made 2 passes from left to right, then from right to left. All test passed. Think the variant with DP from editorial (implementation) is more complex. It's funny, but the "Problem Setter's code" is simplier and really close to my solution.

No such thing as O(2xN), it is simply a O(N) solution

Passed all tests in c++:

int main() {
    int n;
    cin >> n;
    vector<int> r(n); // children ratings
    vector<int> c(n); // candies allocated to each child
    
    // take in r[] and parse left to right
    int numcandies=1; // num of candies to give
    c[0]=1;
    cin >> r[0];
    for (int i=1;i<n;i++) {
        cin >> r[i];
        if (r[i]>r[i-1]) numcandies++;
        else if (r[i]<=r[i-1]) numcandies=1;
        c[i]=numcandies;
    }

    // 2nd parse right to left and accumulate total
    numcandies=1;
    long total=c[n-1];
    for (int i=n-2;i>=0;i--) {
        if (r[i]>r[i+1]) numcandies++;
        else if (r[i]<=r[i+1]) numcandies=1;
        c[i]=(numcandies>c[i]?numcandies:c[i]); //use the larger of 2 parses
        total+=c[i];
    }    
    
    cout << total;
    return 0;
}

Yup! The same I have done and passed all the test cases.

i made my solution using the same logic, just in one for, without the need of using two as most of people here , just arr1 from left to right, and arr2 right to left.

    for (int i = 1; i < n; i++){
        arr1[i] = arr[i] <= arr[i-1] ? 1 : arr1[i-1] + 1;
        arr2[n-1-i] = arr[n-1-i] <= arr[n-i] ? 1 : arr2[n-i] + 1;
    }

// Thank you, I applied this logic in Javascript, here's the code if anyone's introuble with any test cases.

function candies(n, arr) {

        var candiesArray = new Array(n);

        //Declare how much the first person starts with.
        candiesArray[0]=1;

        var sumCandies = 0;

        //Loop forward -->
        for( var i = 1 ; i < n ; i++ ) {
                if( arr[i]>arr[i-1] ){
                        candiesArray[i]=candiesArray[i-1]+1;
                } else {
                        candiesArray[i]=1;
                }
        }

        //Loop back <--
        for (var i = n-2; i>=0; i--){

                if(arr[i]>arr[i+1] && candiesArray[i]<=candiesArray[i+1]){
                        candiesArray[i]=candiesArray[i+1]+1;
                }
                sumCandies += candiesArray[i];
        }

        sumCandies += candiesArray[n-1];

        return(sumCandies);

}

that is exactly what I did. Does not seem complicated at all.

Pass one, you only consider the neighbour to the left and make sure, the current who has a higher score get at least one candy more than the left; Pass two, do in from right to left, check if the neighbour on the left who has a greater score gets at least one more than the right.

I think this is minimal because each element is only affected by its nearest neighbours, i.e., left and right, so two passes from different direction should make sure that the cost is minimal.

does this algo can be called Greedy method? if not is there any other paradigm this algo will form under?

Passed all the cases, thanks! But how this even comes to your mind? I was stuck on trying to solve it using iterative dp solution.

The o/p for the first pass is that every child with higher rating than his left neighbour has more no.of candies. The Loop invariant can be that we are doing a safe move in giving a higher rated child 1 more candy than his left sided neighbour, because 1> the prob requires it to be done so 2> This the minimum possible increase (hence it is part of the optimal soln). Any other number of toffees must be >= this number.

The same argument can be given for your right sided pass

For 1 2 2 with that logic you would get 1 2 2 which is wrog becuase final expected output is 4 in this case.

I did something similar but I am failing to see why this problem is part of the dynamic programming section in the interview practice set. Any one could explain?

Virtual class or online course. ;)

they are tiny kids

Schools in India and China

This is under dynamic i guess because we solving it by dividing it smaller problem (getting numbers of candies by iterating it in one direction) and then using this partial solution to iterate in reverese direction

I solved this problem differently, but with what I believe is a Dynamic Programming solution. In DP questions, you are asked to calculate F[i] for some i. In this case, F[i] is the number of candies given to child i. (Then we sum the values.) The complexity is that the value F[i] depends on other values, in this case for values of i both smaller and larger. The key to Dynamic Programming is that you calculate the values F[i] in an order such that you always have the previous values (i.e., dependencies) you need. So in this problem, what values are needed to calculate F[i]? Well if Ratings[i] is a local minimum, that is, child #i has a lower rating than her neighbors, then we should give her only one candy. So her candy amount didn’t depend on other candy amounts. If Ratings[i] is a local maximum, then child #i gets one more candy than the larger amount of candy between her two neighbors. If Ratings[i] is between Ratings[i-1] and Ratings[i+1], then whichever neighbor has a lower rating, child #i gets one more candy than that neighbor. So in summary, F[i] depends on 0, 2, or 1 of the adjacent values depending on whether Ratings[i] is a local minimum, maximum, or neither, respectively. So to solve this problem, you can write helper functions is_min(), is_max(), get_next_min(), and get_next_max(), and use them to find the first two local mins; set their candies to 1. Find the single local max between them and iterate inward from the mins to the max (up the mountain), giving each child one more candy than the last. Then give the max child one more candy than the neighbor who got more than the other. Then repeat by finding the next local max and min. The other important thing is that if two neighbors have the same rating, then all the children can be split into 2 groups between them, and the two groups can be solved separately. So in a subproblem, adjacent children will never have the same rating. My solution is here: https://www.hackerrank.com/challenges/candies/submissions/code/20326952

thanks bro. i learned a lot from it.

i try this， but it can not pass all the cases. it looks like stack overflow.

To figure out the candies a child gets, is an equation involving the number of candies its neightbours get and this equation depends on their relative ranking. DP version is to calulate the candies count of neighbours if it hasn't been done so far and storing it and reusing again later while calculating candy count of another child. In your code, you are calculating 'c' array multiple times which you shouldn't be doing. Calculate the value once and save it.

Thanks. helped me a lot

its not working for most of the cases

def candies(n, arr):
sum = 0
i = 0
pre = 1
while i < n:
    j = i+1
    l = []
    no = 0
    if j < n:
        if arr[i] >= arr[j]:
            no += 1
            j += 1
    while j < n:
        if arr[j] < arr[j-1]:
            no = no+1
        elif arr[j] == arr[j-1]:
            l.append(no)
        else:
            break
        j += 1
    if i+1 < n and arr[i] == arr[i+1] :
        fi = no
    elif i+1 < n:
        fi = no+1
    else :
        fi = 0
    sum += max(pre, fi)
    sum1 = int((no*(no+1))/2)
    for ite in l:
        sum1 += no-ite+1
    sum = sum+sum1
    if i == j-1:
        pre = pre+1
    else:
        pre = 2
    i = j
return int(sum)

Do all of your test cases pass? I am getting 5 that could not pass

nice work

Nice one. Some improvements:

• Only need one working array, not three
• Can do the max inline

Python2 version:

def candies(n, arr):
    count = [1]
    for i,x in enumerate(arr[1:],1):
        if x <= arr[i-1]:
            count.append(1)
        else:
            count.append(count[i-1]+1)
    for i,x in enumerate(arr[-2::-1],2):
        if x <= arr[n-i+1]:
            count[n-i] = max(count[n-i], 1)
        else:
            count[n-i] = max(count[n-i], count[n-i+1]+1)
    return sum(count)

nice

Thanks. Helped a lot to find the bug :)

Why is it that I get the wrong answer for test cases 11 and 12? do you get that as well?

What is the need of reverse sequence? Please explain.

You must be a programmer for pokemon go with all of those candies

All test cases passed but Exception for this case 3 3 2 1 ...... Or any other case in descending order of ratings.

hey, I tried ur logic but it giving wrong output for testcases #3,5, & 7. I m not getting what I missed. please help. here is my code. public class Solution {

public static int canGet(Vector<Integer> r, Vector<Integer> c, int i){
    if(r.get(i)<=r.get(i-1) && r.get(i)<=r.get(i+1)){
        return 1;
    }
    if(r.get(i)<=r.get(i-1) && r.get(i)>r.get(i+1)){
        if(c.get(i+1)==0){
            int temp = canGet(r,c,i+1);
            c.set(i+1,temp);
        }
        return 1 + c.get(i+1);
    }
    if(r.get(i)>r.get(i-1) && r.get(i)<=r.get(i+1)){
        if(c.get(i-1)==0){
            int temp = canGet(r,c,i-1);
            c.set(i-1,temp);
        }
        return 1 + c.get(i-1);
    }
    if(r.get(i)>r.get(i-1) && r.get(i)>r.get(i+1)){
        if(c.get(i-1)==0){
            int temp = canGet(r,c,i-1);
            c.set(i-1,temp);
        }
        if(c.get(i+1)==0){
            int temp = canGet(r,c,i+1);
            c.set(i+1,temp);
        }
        return 1 + Math.max(c.get(i-1),c.get(i+1));
    }
    return 0;
}

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    Vector<Integer> rank = new Vector<Integer>(n);
    for(int i=0;i<n;i++){
        int t = in.nextInt();
        rank.add(i,t);
    }
    Vector<Integer> cand = new Vector<>(n);
    for(int i=0;i<n;i++){
        cand.add(i,0);
    }

    if(rank.get(0)<rank.get(1)){
        cand.set(0,1);
    }
    if(rank.get(n-1)<=rank.get(n-2)){
        cand.set(n-1,1);
    }
    if(rank.get(0)>=rank.get(1)){
        int c = canGet(rank,cand,1);
        cand.set(0,c+1);
    }
    if(rank.get(n-1)>rank.get(n-2)){
        int c = canGet(rank,cand,n-2);
        cand.set(n-1,c+1);
    }
    for(int i=0;i<n;i++){
        if(cand.get(i)==0){
            int c = canGet(rank,cand,i);
            cand.set(i,c);
        }
    }
    long result = 0;
    Enumeration e = cand.elements();
    while(e.hasMoreElements()){
        int t = (Integer)e.nextElement();
        result = result + t;
    }
    System.out.println(result);
}

}