Problem Statement in English

You’re given an array of integers nums. An index i is called a special index if nums[i] is strictly greater than its neighbors. i must have two neighbors to be a special index. You can increase the value of any element of nums by 1 any number of times. Each increment counts as one operation.

Return the minimum number of operations required to make the number of special indices in nums maximum.

Approach

Since we don’t know what the optimal distribution of peaks is, we can try all possibilities using a recursive function. We can either take the current index as a peak or skip it.

If we take it as a peak, we need to make sure that it’s greater than its neighbors. We can calculate the number of operations required to make it a peak and add that to the result of the recursive call for the next index. If we skip it, we simply move to the next index without any operations.

There is a true DP version which can solve this in O(n) time and O(1) space, but I didn’t really understand it, so I went with the recursive approach with memoization.

And we’re done!

Solution in Python


class Solution:
    def minIncrease(self, nums: List[int]) -> int:
        N = len(nums)

        def getOps(i):
            return max(max(nums[i - 1], nums[i + 1]) + 1, nums[i]) - nums[i]
        
        @cache
        def dfs(i, prevI):

            if i >= N:
                return 0, 0
            
            skipPeaks, skipOps = dfs(i + 1, 0)
            takePeaks, takeOps = 0, 0

            if 0 < i < N - 1 and prevI == 0:
                takePeaks, takeOps = dfs(i + 1, i)
                takeOps += getOps(i)
                takePeaks += 1

            if (takePeaks > skipPeaks) or (takePeaks == skipPeaks and takeOps < skipOps):
                return takePeaks, takeOps
            
            return skipPeaks, skipOps

        peaks, ops = dfs(0, 0)
        return ops

Complexity

  • Time: $O(n^2)$
    Since our cache is 2D and we have two parameters that can take n values each.

  • Space: $O(n^2)$
    Since our cache is 2D and we have two parameters that can take n values each.

Mistakes I Made

I had to look this up :(

And we are done.