Is there a solution with O(n) time and O(1) space?


  • 1
    Z

    I see people use an extra array to store the candy give out to each kid, and use one or two more passes to adjust the number of candies and sum them up. I'm more concerned with any O(1) space solution.

    Here's my code, and I think the comment is self-explanatory. I have problem handling the case when two neighbors have the same rating. Any sparks? Thanks!

    public int candy(int[] ratings) {
        if(ratings.length == 1) return 1;
        //total number of candy
        int total = 0;
        //current number of candies we give. suppose first kid get 1 candy. we will adjust it after the loop.
        int cur = 1;
        //previous kid's rating
        int prevRating = ratings[0];
        //minmum candy we give out to one kid
        int mincandy = 1;
        for(int i = 0;i < ratings.length; i++){
            //I have problem here. I do not know how to handle the case where previous kid has the same rating as current one
            if(prevRating == ratings[i]){
                //cur = 1;? Is there a way to adjust variable cur and mincandy to get the result we want?
                total += cur;
            }
            //if previous kid has larger rating, we decrease the current number of candy by 1
            else if(prevRating > ratings[i]){
                cur--;
                //set minmum candy we give to a kid if necessary
                if(mincandy > cur) mincandy = cur;
                total += cur;
            }
            //if previous kid has smaller rating, we increase the current number of candy by 1
            else if(prevRating < ratings[i]){
                cur++;
                total += cur;
            }
            prevRating = ratings[i];
        }
        //after the loop, we can adjust the total number of candies according to the minmum candy we give out to a single kid.
        //for example, [4, 3, 2, 1], mincandy will be -2 here. total is -2. after the statement below, total will be 10.
        total += (1-mincandy)*ratings.length;
        return total;
    }

  • 0
    N

    Even there is no contiguous equal ratings, your solution still cannot get minimum. For example [1,3,4,5,2], the minimum candies should be {1,2,3,4,1} total is 11. Your answer is {1,2,3,4,3} total is 13.


  • 3
    T

    Guaranteed O(N) time (pass once) and O(1) storage (4 int on stack)

    No math formula or multiplication needed. Only basic "addition" operation.

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            
    /***  The solution is O(N) && space O(1) ***/
    /***  only one pass for time && only 4 int on stack for storage ***/
    
            int current, peak, back, sum;
            
            if (ratings.empty()) return 0;
            
            current=1;
            sum=1;
            back=1;
            peak=INT_MAX;
            
            for (int i=1;i<ratings.size();i++) {
                if (ratings[i]>ratings[i-1]) {
                    current++;
                    sum += current;
                }
                
                else if (ratings[i]==ratings[i-1]) {   
                    
                /**  Take care of equal case: equal ratings does not need equal candy. 
                thus, when ratings[i]==ratings[i-1]  simply give child i 1 candy. no need 
                to store i-1's candy as peak because i can go up infinitely without the 
                necessity to bump i-1 up **/
                
                    peak=INT_MAX; // no need to check
                    current=1;
                    sum +=current;
                    back=1;
                }
                else {
                    if (current!=1) {// drop to 1 
                        peak=current;
                        current=1;
                        sum += current;
                        back=1;
                    }
                    
                    else { // bump all previous (all the way to back's position) up by 1
                        back++;
                        sum += back;
                        if (back==peak) {   // can only be true when dropping to 1 happen when ratings[i]<
                                                 // ratings[i-1],  for equal case, we set peak to INT_MAX to 
                                                 //prevent it from happening here
                            sum++; peak++;
                        }
                    }
                }
            }
            
            return sum;
        }
    };

  • 13
    F

    I've got the solution with O(n) time complexity with O(constant) space in One pass with similar idea,

    Algorithm

    Start having given one candy to each kid i.e. sum = N candies to N children, Now, adjusting the sum in single pass. Repeat until End of ratings sequence

    1. Check increasing peak move until max-peak -> add the additional
      candies
    2. Check the decreasing of peak -> move to depression, add the
      additional candies for only the decreasing sequence after the
      peak
      ,
    3. Then check the range of decreasing & previous increasing sequence,
      adjust the max-peak candies [by adding additional candies to sum]
      only if the range of decreasing is > range of increasing and that would = (decreasing range - increasing range) [ otherwise, everything's in place, Note: you only need to adjust the peak if
      depression range is greater than inclination range]
    4. If it's flat [i.e adjacent ratings are same], just move on,
      everything's in place. [Note: the case where adjacent rating is
      same, it takes care of whether it's on top -peak or bottom, also
      since we're just moving on, it does not add additional candies
      than initial allotted unless it's declination which is handled in
      step 2] [i.e. example test case : [1, 3, 3, 2, 1] =>min no. candies
      = [1, 2, 3, 2, 1] , sum = 9 ]

    [PS: You need to know sum of numbers sequence 1 2, 3...n = (n * (n+1)) / 2, we need this when adjusting /adding number of candies in increasing or decreasing subsequence]


    I hope my code is elegant & readable enough....

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            int n = ratings.size();
            int min_candies = n;
            
            int range = 0;
            for (size_t i = 0; i < n - 1; ) {
                int start = i;
                while (ratings[i] < ratings[i+1] && i < n-1) ++i;
                range = i - start;
                min_candies += (range * (range + 1)) / 2;
                if (i == n-1) break;
                
                start = i;
                while (ratings[i] > ratings[i+1] && i < n-1) ++i;
                int k = i - start - 1;
                min_candies += (k * (k + 1)) / 2;
                if (i - start > range) min_candies += (i - start - range);
                if (ratings[i] == ratings[i+1]) ++i;
            }
            return min_candies;
        }
    };
    

  • 1
    S

    I came up with solution which is similar to TimeArrow's one. O(n) time complexity with O(1) space complexity. I have given an example in code comment for better understanding.

    Here is my code:

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            if (ratings.size() < 1) {
                return 0;
            }
            // e.g.
            // 123654321
            // i    ratings[i]  </=/>   backward    diff    previous    candy_no    total
            // 0    1           >       0           0       1           1           1
            // 1    2           >       0           0       2           12          1 + 2 = 3
            // 2    3           >       0           0       3           123         3 + 3 = 6
            // 3    6           >       0           0       4           1234        6 + 4 = 10
            // 4    5           <       1           3       1           12341       10 + 1 = 11
            // 5    4           <       2           2       1           123421      11 + 2 - 1 + 1 = 13
            // 6    3           <       3           1       1           1234321     13 + 3 - 1 + 1 = 16
            // 7    2           <       4           0       1           12354321    16 + 4 + 1 = 21
            // 8    1           <       5           0       1           123654321   21 + 5 + 1 = 27
            int total = 1;
            int backward = 0;
            int previous = 1;
            int diff = 0;
            for (int i = 1; i < ratings.size(); ++i) {
                if (ratings[i - 1] > ratings[i]) {
                    ++backward;
                    if (previous < 2) {
                        total += backward;
                        if (diff > 1) {
                            --total;
                        }
                    }
                    if (diff > 0) {
                        --diff;
                    }
                    else {
                        diff = previous - 1;
                    }
                    previous = 1;
                }
                else if (ratings[i - 1] < ratings[i]) {
                    backward = 0;
                    diff = 0;
                    total += previous;
                    ++previous;
                }
                else {
                    backward = 0;
                    diff = 0;
                    previous = 1;
                }
                ++total;
            }
            return total;
        }
    };

  • 1
    H

    Here you are, O(n) time and O(1) space, no fancy data structure is used, should be easy to understand.

    int candy( vector<int> & ratings ) {
        int n = ratings.size();
        
        int lastCount = 1;
        int lastHighestIdx = 0;
        int lastHighestCount = 1;
        int total = 1;
        
        for ( int i = 1; i < n; i++ ) {
            if ( ratings[i - 1] == ratings[i] ) {
                lastCount = 1;
                lastHighestIdx = i;
                lastHighestCount = lastCount;
                total += lastCount;
            } else if ( ratings[i - 1] < ratings[i] ) {
                lastCount++;
                lastHighestIdx = i;
                lastHighestCount = lastCount;
                total += lastCount;
            } else {
                int newElems = i - lastHighestIdx;
                
                lastCount = 1;
                if ( lastHighestCount == newElems ) {
                    lastHighestCount++;
                    total++;
                }
                
                total += newElems;
            }
        }
        
        return total;
    }

  • 0
    S

    Nice solution


  • 0
    N

    the best ever


  • 0
    N

    nice solution!


  • 0
    B

    if ( lastHighestCount == newElems ) {
    lastHighestCount++;
    total++;
    }
    Clever solution!


Log in to reply
 

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