3891. Minimum Increase to Maximize Special Indices

Description

You are given an integer array nums of length n.

An index i (0 < i < n - 1) is special if nums[i] > nums[i - 1] and nums[i] > nums[i + 1].

You may perform operations where you choose any index i and increase nums[i] by 1.

Your goal is to:

Maximize the number of special indices.
Minimize the total number of operations required to achieve that maximum.

Return an integer denoting the minimum total number of operations required.

Example 1:

Input: nums = [1,2,2]

Output: 1

Explanation:

Start with nums = [1, 2, 2].
Increase nums[1] by 1, array becomes [1, 3, 2].
The final array is [1, 3, 2] has 1 special index, which is the maximum achievable.
It is impossible to achieve this number of special indices with fewer operations. Thus, the answer is 1.

Example 2:

Input: nums = [2,1,1,3]

Output: 2

Explanation:

Start with nums = [2, 1, 1, 3].
Perform 2 operations at index 1, array becomes [2, 3, 1, 3].
The final array is [2, 3, 1, 3] has 1 special index, which is the maximum achievable. Thus, the answer is 2.

Example 3:

Input: nums = [5,2,1,4,3]

Output: 4

Explanation:

Start with nums = [5, 2, 1, 4, 3].
Perform 4 operations at index 1, array becomes [5, 6, 1, 4, 3].
The final array is [5, 6, 1, 4, 3] has 2 special indices, which is the maximum achievable. Thus, the answer is 4.

Constraints:

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹

Solutions

Solution 1: Memoized Search

We observe that if the array length is odd, then increasing all elements at odd indices so that each is $1$ greater than both adjacent elements yields the maximum possible number of special indices. If the array length is even, then among indices in the range $[1, n - 2]$, we skip exactly one index, and for the remaining indices, increase every other element so that each is $1$ greater than both adjacent elements; this also yields the maximum possible number of special indices.

Therefore, we design a function $\text{dfs}(i, j)$, which represents the minimum number of operations needed to obtain the maximum number of special indices starting from index $i$, with $j$ remaining skips. For each index $i$, we can either increase it so that it is $1$ greater than both neighbors, or skip it. We use memoized search to avoid repeated computation.

The implementation of $\text{dfs}(i, j)$ is as follows:

If $i \geq n - 1$, return $0$.
Compute the number of operations required to increase $nums[i]$ so that it is $1$ greater than both adjacent elements, denoted as $cost$.
Compute the total cost for choosing to increase $nums[i]$: $cost + \text{dfs}(i + 2, j)$.
If $j > 0$, compute the total cost for choosing to skip $nums[i]$: $\text{dfs}(i + 1, 0)$, and update $ans$ to the smaller of the two.

Finally, return $\text{dfs}(1, (n \bmod 2) \oplus 1)$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.

class Solution {
    private Long[][] f;
    private int[] nums;
    private int n;

    public long minIncrease(int[] nums) {
        n = nums.length;
        this.nums = nums;
        f = new Long[n][2];
        return dfs(1, n & 1 ^ 1);
    }

    private long dfs(int i, int j) {
        if (i >= n - 1) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);
        long ans = cost + dfs(i + 2, j);
        if (j > 0) {
            ans = Math.min(ans, dfs(i + 1, 0));
        }
        return f[i][j] = ans;
    }
}

class Solution {
private:
    vector<vector<long long>> f;
    vector<int> nums;
    int n;

public:
    long long minIncrease(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        f.assign(n, vector<long long>(2, -1));
        return dfs(1, (n & 1) ^ 1);
    }

    long long dfs(int i, int j) {
        if (i >= n - 1) {
            return 0;
        }
        if (f[i][j] != -1) {
            return f[i][j];
        }
        int cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);
        long long ans = cost + dfs(i + 2, j);
        if (j > 0) {
            ans = min(ans, dfs(i + 1, 0));
        }
        return f[i][j] = ans;
    }
};

class Solution:
    def minIncrease(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(nums) - 1:
                return 0
            cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])
            ans = cost + dfs(i + 2, j)
            if j:
                ans = min(ans, dfs(i + 1, 0))
            return ans

        return dfs(1, len(nums) & 1 ^ 1)

func minIncrease(nums []int) int64 {
	n := len(nums)

	f := make([][]int64, n)
	for i := range f {
		f[i] = []int64{-1, -1}
	}

	var dfs func(i, j int) int64
	dfs = func(i, j int) int64 {
		if i >= n-1 {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}

		cost := max(0, max(nums[i-1], nums[i+1])+1-nums[i])
		ans := int64(cost) + dfs(i+2, j)

		if j > 0 {
			if t := dfs(i+1, 0); t < ans {
				ans = t
			}
		}

		f[i][j] = ans
		return ans
	}

	return dfs(1, (n&1)^1)
}

function minIncrease(nums: number[]): number {
    const n = nums.length;

    const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-1));

    const dfs = (i: number, j: number): number => {
        if (i >= n - 1) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }

        const cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);
        let ans = cost + dfs(i + 2, j);

        if (j > 0) {
            ans = Math.min(ans, dfs(i + 1, 0));
        }

        f[i][j] = ans;
        return ans;
    };

    return dfs(1, (n & 1) ^ 1);
}

3891 - Minimum Increase to Maximize Special Indices

3891. Minimum Increase to Maximize Special Indices

Description

Solutions

Solution 1: Memoized Search

All Problems

All Solutions

Welcome to Subscribe On Youtube

3891. Minimum Increase to Maximize Special Indices

Description

Solutions

Solution 1: Memoized Search

All Problems

All Solutions