C++ (23ms), Beats 99.83% sumission


  • 0
    F

    Comments in-line. O(N) solution, O(N) space.

    int candies = 0;
    if ( !ratings.size() ) return candies;
    vector<int> rat ( ratings.size(), 0);
    rat[0] = 1;
    for ( unsigned int i = 1; i < ratings.size(); i++ ) {
    	if ( ratings[i] > ratings[i-1] ) {
    		rat[i] = rat[i-1] + 1;
    	} else if ( ratings[i] == ratings[i-1] ){
    		rat[i] = 1;
    	} else {
    		// Correction factor if the i+1 is lesser than ith number.
    		rat[i] = 1;
    		// Go forward till you find the case where the sequence is decreasing.
    		unsigned int j,k;
    		for ( j = i; j < ratings.size() && ratings[j-1] > ratings[j]; j++ );
    		j--;
    		k = j;
    
    		rat[k] = 1;
    		k--;
    		// Come back in the order and assign the rating in reverse order
    		for ( ; k >= i ; k-- ) {
    			rat[k] = rat[k+1]+1;
    		}
    		/* check if the last number has a lower rating than it should have.
    		 * Increase it.
    		 */
    
    		if ( rat[k] <= rat[k+1] ) {
    			rat[k] = rat[k+1]+1;
    		}
    		i = j;
    	}
    }
    for ( unsigned int i = 0; i < ratings.size(); i++ ) {
    	candies += rat[i];
    }
    return candies;

Log in to reply
 

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