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?

This appears to be the official solution too (see the editorial after you've solved the problem). I somehow don't see how it is in any way related to DP - it is a pure greedy algorithm, and even the official solution states so.

I did this and it works perfectly. I'm kinda new, but the solution is dynamic programming right?

Forward-pass for all up-trends: Subproblem = test arr[i] > arr[i-1], candy[i] = candy[i-1] or candy[i]

Backwards-pass for all up-trends: Subproblem = test (candy[i] < candy[i+1]) and (arr[i] > arr[i+1]), candy[i] = candy[i+1] + 1

Just need to get the array referencing correct and you're good!

Nothing magic. Decreasing sequences have to descrease down to 1. And increasing sequences have to increase from 1. Reverse iteration or keeping two last value variables will do the job. The tricky point is determining values at the joint of increasing and decreasing values. Values at joint points can be determined after second iteration, say reverse, greater value will be kept of two iterations in joints.

This seemed so easy after this tip... Why didn't I remember this?! :(

static long candies(int n, int[] v) {
    int[] ca = new int[n];
    ca[0] = 1;
    for (int i = 1; i < n; i++)
        if (v[i] > v[i-1])
            ca[i] = ca[i-1] + 1;
        else
            ca[i] = 1;

    long res = ca[n-1];
    for (int i = n-2; i >= 0; i--) {
        if (v[i] > v[i+1])
            ca[i] = Math.max(ca[i], ca[i+1] + 1);
        res += ca[i];
    }

    return res;
}

what if they are equal? or there are equal peaks?

Thank you for the tips. Alternate left scan and right scan passes the one test case that I failed due to timeout.

hey this was brilliant, really very easy, simple and smart!! Thanks!

same thing i did

its a greedy approach ,thats maybe why you think that way

Your approach is correct but you have bad worded it here XO. Instead you can say that, make a count array of size n, initialized by 1.Now we have 2 arrays arr( rating array) and count array. Now we go from left to right in count array and if(arr[i+1]>arr[i]) count[i+1]=count[i]+1 . Now we go from right to left if(arr[i-1] > arr[i] ) and count[i-1] <= count[i] then count[i-1] =count[i] +1. Then just calculate the sum of count array i.e your answer.

use the test case

7

1 2 3 4 3 2 1

i hope u will get ur mistake.

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.

your words are confusing. It would be easier if i see ur code. Can u share your code please?