Approach: Two passes

def candy(ratings):
    n = len(ratings)
    c = [1]*n
    for i in range(1, n):
        if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]: c[i] = max(c[i], c[i+1] + 1)
    return sum(c)

Complexity: O(n) time, O(n) space.

Full Solution — all languages

class Solution:
    def candy(self, nums):
        n = len(nums)
        c = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                c[i] = c[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                c[i] = max(c[i], c[i + 1] + 1)
        return sum(c)

import java.util.*;
class Solution {
    public int candy(int[] nums) {
        int n = nums.length;
        int[] c = new int[n];
        Arrays.fill(c, 1);
        for (int i = 1; i < n; i++) if (nums[i] > nums[i - 1]) c[i] = c[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--) if (nums[i] > nums[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
        int total = 0;
        for (int x : c) total += x;
        return total;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int candy(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> c(n, 1);
        for (int i = 1; i < n; i++) if (nums[i] > nums[i - 1]) c[i] = c[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--) if (nums[i] > nums[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
        int total = 0;
        for (int x : c) total += x;
        return total;
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */ var candy = function(nums) {
    const n = nums.length;
    const c = new Array(n).fill(1);
    for (let i = 1; i < n; i++) if (nums[i] > nums[i - 1]) c[i] = c[i - 1] + 1;
    for (let i = n - 2; i >= 0; i--) if (nums[i] > nums[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
    return c.reduce((s, x) => s + x, 0);
};

Candy

Example 1

Example 2

Constraints