Python O(N) time and O(1) space complexity solution


#1
def candy(a: List[int]):
    if not a:
        return 0
    res = 1

    prev_candy = 1
    descent_len = 1
    descent_top = 1
    for i, cur in enumerate(a[1:]):
        prev = a[i]
        if cur < prev:
            descent_len += 1
            res += descent_len - 1
            if descent_top < descent_len:
                descent_top += 1
                res += 1
            prev_candy = 1
        else:
            if cur == prev:
                prev_candy = 1
            else:
                prev_candy += 1
            res += prev_candy
            descent_len = 1
            descent_top = prev_candy

    return res

Explanation (cur and prev relate to the rates):

  • cur == prev: give cur 1
  • cur > prev : give cur what prev got + 1
  • cur < prev : give cur 1, and an extra 1 to all prevs on the current slope except the top (first) one. The top one minimal size is the slope length, therefore it should be incremented only it it’s less than the slope length.