Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Think of each increment operation as starting a horizontal layer that can continue across later positions. The first height requires that many layers. A rise requires new layers to begin, while a fall merely ends some existing layers without starting more.

Approach

Initialize the answer with target[0]. For each subsequent position, add the positive part of its increase over the preceding height. Return the sum. Every counted rise is unavoidable because operations reaching the previous position cannot supply the extra height, and extending or ending existing layers constructs the target using exactly this many operations, establishing optimality.

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        res = target[0]

        for i in range(1, len(target)):
            if target[i] > target[i - 1]:
                res += target[i] - target[i - 1]

        return res

Complexity analysis

For n = target.length, the adjacent-difference scan takes O(n) time and O(1) auxiliary space.