My o(n) time o(1) space c++ solution with 39ms


  • 1
    Y
    class Solution {
    public:
        int candy(vector<int> &ratings) {
            int size = ratings.size();
            int res = 0;
            
            if(size == 0) return 0;
            
            res += 1;
            int last = 1;
            for(int i = 1; i < size; ) {
                if(ratings[i] > ratings[i - 1]) {
                    res += last + 1;
                    last += 1;
                    i ++;
                }
                else if(ratings[i] == ratings[i - 1]) {
                    last = 1;
                    res += last;
                    i ++;
                }
                else {
                    int c = 1;
                    for( ; i < size; i ++) {
                        if(ratings[i] >= ratings[i - 1]) {
                            break;
                        }
                        c ++;
                    }
                    if(last >= c) res += c * (c - 1) / 2;
                    else {
                        res -= last;
                        res += (1 + c) * c / 2;
                    }
                    last = 1;
                }
            }
            return res;
        }
    };

  • 0
    P

    This is O(n^2) due to the nested for loop.


  • 0
    Y

    not exactly. every element in the array will be check only once. As you can see from my code I use an 'i' to reverse the array the nested loop also use 'i', SO the i will be 0 to n - 1.


Log in to reply
 

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