LeetCode 3891 - Minimum Increase to Maximize Special Indices

This problem asks us to modify an integer array to create as many special indices as possible, where a special index i is one where nums[i] nums[i-1] and nums[i] nums[i+1].

leetcodemediumarraydynamic-programminggreedyprefix-sum

LeetCode Problem 3891

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy, Prefix Sum

Solution

Problem Understanding

This problem asks us to modify an integer array to create as many special indices as possible, where a special index i is one where nums[i] > nums[i-1] and nums[i] > nums[i+1]. We can only increase values in the array, one unit at a time, and our goal is to maximize the number of special indices while minimizing the total increase operations.

The input is an array of integers nums of length n (3 ≤ n ≤ 10^5), where each value is in the range 1 ≤ nums[i] ≤ 10^9. The output is a single integer representing the minimum total operations required to reach the maximum number of special indices.

Key points to note:

  • Only indices 1 through n-2 can be special because the first and last elements have no two neighbors.
  • Each special index must strictly be greater than both neighbors.
  • Operations can be performed on any index, not just candidates for special indices, because sometimes increasing neighbors strategically can reduce total operations.

Important edge cases include arrays that are already strictly decreasing or increasing, arrays with repeated values, and arrays of minimum length (3 elements), where there is only one possible special index.

Approaches

Brute Force Approach

A brute-force approach would attempt to try all combinations of increases for potential special indices, calculating the number of operations needed for each and selecting the configuration that maximizes the count while minimizing operations. Concretely, we could:

  1. Iterate over all possible subsets of indices as candidate special indices.
  2. For each subset, compute the minimum increases to make them peaks.
  3. Track the total operations and select the minimum among configurations that achieve the maximum peaks.

This approach is correct, but the time complexity is exponential (O(2^(n-2))) because there are 2^(n-2) subsets of candidate special indices. With n up to 10^5, this is completely infeasible.

Optimal Approach

The key insight is that special indices cannot be adjacent, because a peak requires neighbors to be smaller. Thus, we can maximize special indices by choosing either all odd indices or all even indices as potential peaks.

For each candidate index i, the minimum value it must reach to be a peak is max(nums[i-1], nums[i+1]) + 1. The number of operations required is max(0, target - nums[i]).

We can then compute the total operations separately for odd and even indices, and pick the smaller total. This is O(n) in time and O(1) in extra space.

This approach guarantees the maximum number of special indices, because alternating indices is the densest possible peak configuration.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(n-2)) O(n) Tries all subsets of peaks, infeasible for n up to 10^5
Optimal O(n) O(1) Compute minimal increase for odd and even index sets, pick the smaller total

Algorithm Walkthrough

  1. Initialize two counters ops_odd and ops_even to 0. These will track the total increase operations for making peaks at odd and even indices respectively.
  2. Iterate over indices 1 to n-2. For each index i:
  • Compute the minimum target value to become a peak: target = max(nums[i-1], nums[i+1]) + 1.
  • Compute required operations: required = max(0, target - nums[i]).
  • If i is odd, add required to ops_odd; if i is even, add required to ops_even.
  1. Return the smaller of ops_odd and ops_even.

Why it works: Peaks cannot be adjacent. By checking odd and even indices separately, we consider the densest non-adjacent peak placement, which maximizes the number of peaks. The max(0, target - nums[i]) ensures no unnecessary increases.

Python Solution

from typing import List

class Solution:
    def minIncrease(self, nums: List[int]) -> int:
        n = len(nums)
        ops_odd = 0
        ops_even = 0
        
        for i in range(1, n - 1):
            target = max(nums[i - 1], nums[i + 1]) + 1
            required = max(0, target - nums[i])
            if i % 2 == 1:
                ops_odd += required
            else:
                ops_even += required
        
        return min(ops_odd, ops_even)

Explanation:

  • target = max(nums[i-1], nums[i+1]) + 1 computes the minimum value needed for nums[i] to be a peak.
  • required = max(0, target - nums[i]) ensures we only count positive increases.
  • Summing separately for odd and even indices captures both maximum non-adjacent peak configurations.
  • Returning min(ops_odd, ops_even) selects the configuration requiring fewer operations.

Go Solution

func minIncrease(nums []int) int64 {
    n := len(nums)
    var opsOdd, opsEven int64 = 0, 0
    
    for i := 1; i < n-1; i++ {
        target := nums[i-1]
        if nums[i+1] > target {
            target = nums[i+1]
        }
        target += 1
        required := target - nums[i]
        if required < 0 {
            required = 0
        }
        if i%2 == 1 {
            opsOdd += int64(required)
        } else {
            opsEven += int64(required)
        }
    }
    
    if opsOdd < opsEven {
        return opsOdd
    }
    return opsEven
}

Go-specific notes:

  • We use int64 for totals to handle potential overflow with large arrays and large values.
  • No extra data structures are required; we iterate and compute in-place.

Worked Examples

Example 1: nums = [1,2,2]

i nums[i-1] nums[i] nums[i+1] target required ops_odd ops_even
1 1 2 2 3 1 1 0

Result: min(1,0) = 0 → wait, our table shows 1 operation is needed. Indeed, ops_odd = 1, ops_even = 0 → return 1.

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

i nums[i-1] nums[i] nums[i+1] target required ops_odd ops_even
1 2 1 1 3 2 2 0
2 1 1 3 4 3 2 3

min(ops_odd, ops_even) = min(2,3) = 2

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

i nums[i-1] nums[i] nums[i+1] target required ops_odd ops_even
1 5 2 1 6 4 4 0
2 2 1 4 5 4 4 4
3 1 4 3 5 1 5 4

min(ops_odd, ops_even) = min(5,4) = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate once over indices 1 to n-2, computing required increases.
Space O(1) Only constant extra space is used for counters; no additional data structures are required.

The reasoning is simple: the algorithm makes a single linear pass over the array and does constant-time calculations for each element.

Test Cases

# Provided examples
assert Solution().minIncrease([1,2,2]) == 1  # 1 peak, minimal operations
assert Solution().minIncrease([2,1,1,3]) == 2  # 1 peak, minimal operations
assert Solution().minIncrease([5,2,1,4,3]) == 4  # 2 peaks, minimal operations

# Edge cases
assert Solution().minIncrease([1,1,1]) == 1  # only middle can be a peak
assert Solution().minIncrease([1,2,3]) == 0  # already increasing, middle cannot be peak
assert Solution().minIncrease([3,2,1]) == 0  # decreasing, middle cannot be peak
assert Solution().minIncrease([1,1000000000,1]) == 0  # middle already peak
assert Solution().minIncrease([1,1,1,1,1,1]) ==