10 lines of C++, O(n) time complexity, O(n) space w/ explanation of algorithm


  • 1
    J

    Idea: envision the sequence of ratings as uphill (increase) and downhill (decrease) segments. Here the valley points (lower than both neighbors, and the index 0 and n-1 can be treated as special case) are the key to solve the problem. We make the following observations:
    [1] The valley points should be given only 1 candy for minimum candies
    [2] The valley points won't be affected by neighbors
    [3] So we start from each valley point, and walk uphills on both sides (could be only one side for index 0 and n-1) and update the minimum candies required for each rating we met.

    Thus, T(n) = O(n)

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int n = ratings.size();
            vector<int> C(n, 1);
            for (int i = 0; i < n; i++)
                if ((i-1<0 || ratings[i-1] >= ratings[i]) && (i+1 == n || ratings[i+1] >= ratings[i])) {
                    for (int j = i-1; j >= 0 && ratings[j] > ratings[j+1]; j--)
                        C[j] = max(C[j], 1+C[j+1]);
                    for (int j = i+1; j < n && ratings[j] > ratings[j-1]; j++)
                        C[j] = max(C[j], 1+C[j-1]);
                }
            return accumulate(C.begin(), C.end(), 0);
        }
    };

Log in to reply
 

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