C, 19 lines of code, one pass, O(n), O(1) solution


  • 1
    L

    'c' is number of candies, 'a' is length of ascending sequence, 'd' is length of descending sequence.

    int candy( int* r, int n )
    {
        int c = 1, a = 1, d = 1;
        for( int i = 1; i < n; ++i )
        {
            if( r[i] < r[i-1] )
            {
                ++d;
                continue;
            }
            c += d * (d - 1) / 2 + (d > a ? d - a : 0);
            if( r[i] == r[i-1] )
                a = 0, d = 1;
            else if( d > 1 )
                a = 1, d = 1;
            c += ++a;
        }
        return c + d * (d - 1) / 2 + (d > a ? d - a : 0);
    }
    

    and it is a concision of below code which is more easy to understand.

    int candy( int* r, int n )
    {
        int c = 1, a = 1, d = 1;
        for( int i = 1; i < n; ++i )
        {
            if( r[i] > r[i-1] ) // in a ascending sequence
            {
                if( d > 1 ) // a descending sequence ended here?
                {
                    // add candies for the descending sequence but exclude the first child,
                    //  the formula is simplified from '((d - 1) + 1) * (d - 1) / 2'
                    c += d * (d - 1) / 2;
                    // adjust candies for the last child in previous ascending sequence if needed,
                    // note he is also the first child in the descending sequence
                    if( d > a )
                        c += d - a;
                    a = d = 1; // reset length of ascending & descending sequence
                }
                ++a; // update length of ascending sequence
                c += a; // add candies for current child
            }
            else if( r[i] == r[i-1] )
            {
                // same as the start of ascending sequence,
                // add candies for the descending sequence if this end a descending sequence,
                // note this will be '0' if 'd' is 1
                c += d * (d - 1) / 2;
                if( d > a )
                    c += d - a;
                // add candy for current child, always '1'
                // (poor child, he scores same as his neighbour but get less) 
                ++c;
                a = d = 1;  // reset length of ascending & descending sequence
            }
            else
            {
                ++d; // update the length of descending sequence
            }
        }
        c += d * (d - 1) / 2; // handle the last descending sequence
        if( d > a )
            c += d - a;
        return c;
    }

  • 0
    F

    can you explain your solution? i cant understand


  • 0
    L

    i've added my previous version with comment, the latest version is a concision of this version


Log in to reply
 

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