Problem Statement in English

You’re given an array of positive integers target and an array initial of the same length as an initial configuration.

Your goal is to transform initial into target using a series of operations. In one operation, you can choose any subarray of initial and increment each element in that subarray by 1.

Return the minimum number of operations required to form target from initial.

Approach

This is straight from NeetCode. He is back!!! 🥳

Once you get the diagram the problem just unravels on itself. It’s absolutely crazy.

Imagine that this array represents the target array [1,1,2,3,3,3,2,1,1,2,3,3,3,2]. The height of each column represents the value at that index.

Notice how when you choose to do an operation, you’ll do it until you hit a peak (a column with a heigth greater than the previous one). This new height that you climb to will be valid even as you go downwards into a valley, with no new operations needed.

Also notice how you only need to do new operations when you start going back up again.

Each time you go up, you need to do the difference between the previous height and the new height.

And that’s actually pretty much it.

I thoroughly recommend watching NeetCode’s video on this one. The guy’s just plain awesome.

Solution in Python


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

        for t in target:
            if t > prev:
                res += t - prev
            prev = t

        return res

Complexity

  • Time: $O(n)$
    Since we iterate over the array.

  • Space: $O(1)$
    Since we don’t use any extra space.

Mistakes I Made

I had to look this one up :(

The flip side is that NeetCode is back!!! 🥳

And we are done.