3891. Minimum Increase to Maximize Special Indices

MediumGreedyArrayDynamic ProgrammingPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

An index i (where 0 < i < n - 1) is called special if it is strictly greater than both of its neighbors. In other words, index i is special when both of the following conditions hold:

nums[i] > nums[i - 1]
nums[i] > nums[i + 1]

You are allowed to perform operations on the array. In each operation, you may pick any index i and increase nums[i] by 1. You can perform as many operations as you like.

Your task has two goals, considered in order of priority:

Maximize the number of special indices in the array.
Among all ways to achieve that maximum number of special indices, minimize the total number of operations used.

Return an integer representing the minimum total number of operations required to reach the maximum possible number of special indices.

A few important details to keep in mind:

Special indices must lie strictly inside the array, so the first index (0) and the last index (n - 1) can never be special.
Two adjacent indices cannot both be special at the same time, since a special index must be strictly greater than its neighbor (so its neighbor cannot also be greater than it). This means special indices are naturally spaced apart.
Because increasing a value can only help an index become special (and never hurts the index itself), you may need to raise certain elements just enough to be 1 greater than both of their neighbors.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

A memoized DP with a skip budget minimizes operations to maximize special indices, choosing between making an index special or skipping it.

Open in Flowchart

Intuition

The first thing to notice is that special indices cannot be adjacent. If index i is special, it must be greater than nums[i + 1], which means index i + 1 cannot be greater than nums[i], so i + 1 cannot be special. This tells us that special indices must be spaced at least two positions apart.

Since special indices live in the range [1, n - 2] and must be separated by gaps, the maximum number of special indices we can hope for is limited by how many non-adjacent positions fit into that range. Let's think about the two cases based on the parity of n:

When n is odd, the range [1, n - 2] contains an odd count of positions, and we can make every odd index special by picking indices 1, 3, 5, .... There is exactly one clean way to pack them tightly, so no position needs to be skipped.
When n is even, the tightly packed pattern of every-other index does not perfectly fill the range. We end up needing to skip exactly one index somewhere in [1, n - 2], and from that skip point onward, the parity of the chosen indices shifts. This gives us flexibility: we can choose where to place that single skip to minimize the total cost.

For any index i we decide to make special, the number of operations needed is determined by how much we must raise nums[i] so it exceeds both neighbors. The cost is:

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])

If nums[i] is already greater than both neighbors, the cost is 0; otherwise we lift it to max(nums[i - 1], nums[i + 1]) + 1.

This naturally leads to a decision process that walks across the array. At each index we have two choices:

Make this index special, pay its cost, and jump ahead by 2 (since the next index cannot also be special).
Skip this index (only allowed if we still have a skip available), and move ahead by 1, shifting the pattern.

Because the same (position, remaining skips) state can be reached through different earlier choices, we use memoized search to avoid recomputing overlapping subproblems. We define dfs(i, j) as the minimum operations needed starting from index i with j skips remaining, and we start the search at index 1 with j = (n mod 2) ^ 1 — meaning 0 skips when n is odd and 1 skip when n is even. This setup directly encodes the maximum-special-count requirement into the search, so minimizing the cost over all valid choices gives us the answer.

Pattern Learn more about Greedy, Dynamic Programming and Prefix Sum patterns.

Solution Approach

We use Memoized Search (dynamic programming via recursion with caching) to explore all valid ways of choosing special indices while tracking the minimum cost.

Building on the observations above:

When the array length is odd, increasing all elements at odd indices so each is 1 greater than both neighbors yields the maximum number of special indices. No skip is needed.
When the array length is even, we must skip exactly one index in the range [1, n - 2]. For the rest, we increase every other element so each is 1 greater than both neighbors. This also yields the maximum number of special indices.

We design the function dfs(i, j), which returns the minimum number of operations needed to obtain the maximum number of special indices starting from index i, where j is the number of remaining skips allowed.

The logic inside dfs(i, j) works as follows:

Base case: If i >= n - 1, we have reached or passed the last valid position, so there is nothing more to do. Return 0.
Compute the cost of making index i special. To be special, nums[i] must be strictly greater than both neighbors, so we lift it to max(nums[i - 1], nums[i + 1]) + 1 if it is not already large enough:

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])
Choice 1 — make index i special: Pay cost, then jump ahead by 2 (since index i + 1 cannot also be special):

ans = cost + dfs(i + 2, j)
Choice 2 — skip index i (only available when j > 0): Move forward by 1 and use up the skip by setting it to 0. We take the better of the two options:

ans = min(ans, dfs(i + 1, 0))
Return ans.

Starting the search: We call dfs(1, (n & 1) ^ 1).

The first candidate special index is 1, so we start there.
The expression (n & 1) ^ 1 computes (n mod 2) ^ 1, which evaluates to 0 skips when n is odd and 1 skip when n is even — exactly matching the two cases described.

Why memoization helps: The same state (i, j) can be reached through different sequences of earlier decisions. By caching results with @cache, each unique (i, j) pair is computed only once.

Complexity Analysis:

Time Complexity: O(n). There are O(n) index values and only 2 possible values of j (0 or 1), giving O(n) distinct states, each solved in constant time.
Space Complexity: O(n), for the recursion stack and the cache that stores the computed states.

Example Walkthrough

Let's trace through the solution approach using a small example.

Input: nums = [1, 1, 1, 1], so n = 4.

Since n = 4 is even, we are allowed exactly one skip. We start the search with dfs(1, (4 & 1) ^ 1) = dfs(1, 1) — meaning we begin at index 1 with 1 skip available.

The valid candidate positions are indices 1 and 2 (since 0 and n - 1 = 3 can never be special).

Step 1: dfs(1, 1) — at index 1, 1 skip remaining

First, compute the cost of making index 1 special. We need nums[1] to exceed both neighbors:

cost = max(0, max(nums[0], nums[2]) + 1 - nums[1])
     = max(0, max(1, 1) + 1 - 1)
     = max(0, 2 - 1)
     = 1

We now explore both choices:

Choice 1 — make index 1 special: Pay cost = 1, then jump to dfs(1 + 2, 1) = dfs(3, 1).
Choice 2 — skip index 1 (allowed, since j = 1 > 0): Move to dfs(1 + 1, 0) = dfs(2, 0).

We need to resolve both branches before deciding.

Step 2a: dfs(3, 1) — at index 3

Here i = 3 and n - 1 = 3, so i >= n - 1. This is the base case, return 0.

So Choice 1 total = cost + dfs(3, 1) = 1 + 0 = 1.

Step 2b: dfs(2, 0) — at index 2, 0 skips remaining

Compute the cost of making index 2 special:

cost = max(0, max(nums[1], nums[3]) + 1 - nums[2])
     = max(0, max(1, 1) + 1 - 1)
     = 1

Choices:

Choice 1 — make index 2 special: Pay 1, jump to dfs(4, 0). Since 4 >= n - 1 = 3, base case returns 0. Total = 1 + 0 = 1.
Choice 2 — skip: Not allowed, since j = 0.

So dfs(2, 0) returns 1.

Back in Step 1, Choice 2 total = dfs(2, 0) = 1.

Step 3: Combine results at dfs(1, 1)

ans = min(Choice 1, Choice 2)
    = min(1, 1)
    = 1

Result: The minimum number of operations is 1.

This makes sense: with n = 4, the two candidate positions 1 and 2 are adjacent, so at most one of them can be special. Picking either one requires raising it from 1 to 2 (one operation) to exceed its neighbors. The single skip lets us choose whichever placement is cheapest — and here both cost the same, yielding a final answer of 1.

Solution Implementation

1from functools import cache
2from typing import List
3
4
5class Solution:
6    def minIncrease(self, nums: List[int]) -> int:
7        n = len(nums)
8
9        @cache
10        def dfs(index: int, can_skip: int) -> int:
11            # Reached the last element or beyond: no further cost needed
12            if index >= n - 1:
13                return 0
14
15            # Cost to raise nums[index] so that it is strictly greater
16            # than both of its neighbors (clamped at 0 if already greater)
17            cost = max(0, max(nums[index - 1], nums[index + 1]) + 1 - nums[index])
18
19            # Option 1: pay the cost here and jump two positions ahead
20            result = cost + dfs(index + 2, can_skip)
21
22            # Option 2: if a skip is still available, skip this position
23            # (move one step forward) and consume the skip allowance
24            if can_skip:
25                result = min(result, dfs(index + 1, 0))
26
27            return result
28
29        # The initial skip allowance depends on the parity of n:
30        # (n & 1 ^ 1) == 1 when n is even, 0 when n is odd
31        return dfs(1, n & 1 ^ 1)
32

1class Solution {
2    // Memoization table: memo[index][parityFlag] caches the minimum cost
3    // for the subproblem starting at position 'index' with the given parity flag.
4    private Long[][] memo;
5    // Reference to the input array.
6    private int[] values;
7    // Length of the input array.
8    private int length;
9
10    public long minIncrease(int[] nums) {
11        length = nums.length;
12        values = nums;
13        memo = new Long[length][2];
14        // Start the recursion at index 1.
15        // (length & 1 ^ 1) yields 1 when length is even, 0 when length is odd.
16        // This flag tracks whether we still have the option to "skip" one element.
17        return dfs(1, length & 1 ^ 1);
18    }
19
20    /**
21     * Computes the minimum total cost for the subproblem starting at 'index'.
22     *
23     * @param index      the current position being considered
24     * @param skipOption a flag (1 or 0) indicating whether the option to skip
25     *                   the current element (advancing by one) is still available
26     * @return the minimum accumulated cost from this state onward
27     */
28    private long dfs(int index, int skipOption) {
29        // Base case: once we reach the second-to-last element or beyond,
30        // there is nothing more to process.
31        if (index >= length - 1) {
32            return 0;
33        }
34        // Return the cached result if this state was already computed.
35        if (memo[index][skipOption] != null) {
36            return memo[index][skipOption];
37        }
38
39        // Cost required to make values[index] strictly greater than both neighbors.
40        // If it is already large enough, the cost is 0.
41        int cost = Math.max(0, Math.max(values[index - 1], values[index + 1]) + 1 - values[index]);
42
43        // Option 1: pay the cost here and jump two positions forward,
44        // keeping the current skipOption flag.
45        long result = cost + dfs(index + 2, skipOption);
46
47        // Option 2: if the skip option is still available, advance by one
48        // position and consume the skip option (set flag to 0).
49        if (skipOption > 0) {
50            result = Math.min(result, dfs(index + 1, 0));
51        }
52
53        // Cache and return the best result for this state.
54        return memo[index][skipOption] = result;
55    }
56}
57

1class Solution {
2private:
3    // memo[i][canSkip] caches the minimum cost starting at index i,
4    // where canSkip indicates whether we still have a "skip" operation available
5    vector<vector<long long>> memo;
6    // Reference copy of the input array for use inside the recursion
7    vector<int> values;
8    // Total number of elements
9    int size;
10
11public:
12    long long minIncrease(vector<int>& nums) {
13        values = nums;
14        size = nums.size();
15        // Initialize the memo table with -1 (meaning "not computed yet").
16        // Second dimension has 2 states: 0 = no skip left, 1 = skip available.
17        memo.assign(size, vector<long long>(2, -1));
18        // Start the recursion from index 1.
19        // The initial skip availability depends on the parity of size:
20        // (size & 1) ^ 1 is 1 when size is even, 0 when size is odd.
21        return dfs(1, (size & 1) ^ 1);
22    }
23
24    long long dfs(int index, int canSkip) {
25        // Base case: once we reach the last element (or beyond),
26        // there is nothing more to process, so the cost is 0.
27        if (index >= size - 1) {
28            return 0;
29        }
30        // Return the cached result if it has already been computed.
31        if (memo[index][canSkip] != -1) {
32            return memo[index][canSkip];
33        }
34        // Cost required to make values[index] strictly greater than both
35        // its neighbors values[index - 1] and values[index + 1].
36        // If it is already large enough, the cost is 0.
37        int cost = max(0, max(values[index - 1], values[index + 1]) + 1 - values[index]);
38        // Option 1: take this element (pay the cost) and jump two steps ahead.
39        long long best = cost + dfs(index + 2, canSkip);
40        // Option 2: if a skip is still available, move one step ahead and
41        // consume the skip (set canSkip to 0).
42        if (canSkip > 0) {
43            best = min(best, dfs(index + 1, 0));
44        }
45        // Cache and return the optimal result for this state.
46        return memo[index][canSkip] = best;
47    }
48};
49

1/**
2 * Computes the minimum total increase needed based on a DP over positions.
3 *
4 * The DP walks through the array considering pairs of indices. At each index `i`
5 * we may either "pay" a cost to make `nums[i]` strictly greater than both of its
6 * neighbors and then jump two steps ahead, or (when the budget flag `j` allows)
7 * skip one step ahead without paying.
8 *
9 * @param nums - The input array of numbers.
10 * @returns The minimum accumulated cost.
11 */
12function minIncrease(nums: number[]): number {
13    // Total number of elements.
14    const length = nums.length;
15
16    // Memoization table: memo[i][j] caches the result of dfs(i, j).
17    // Second dimension has size 2 because `j` is a 0/1 flag.
18    // Initialized to -1 to mark "not yet computed".
19    const memo: number[][] = Array.from({ length }, () => Array(2).fill(-1));
20
21    /**
22     * Recursive depth-first search with memoization.
23     *
24     * @param index - Current position being processed.
25     * @param flag  - Remaining "skip" budget (0 or 1).
26     * @returns The minimum cost from this state onward.
27     */
28    const dfs = (index: number, flag: number): number => {
29        // Base case: reaching the last element (or beyond) incurs no further cost.
30        if (index >= length - 1) {
31            return 0;
32        }
33
34        // Return cached result if already computed for this state.
35        if (memo[index][flag] !== -1) {
36            return memo[index][flag];
37        }
38
39        // Cost to raise nums[index] above both neighbors (never negative).
40        const cost = Math.max(
41            0,
42            Math.max(nums[index - 1], nums[index + 1]) + 1 - nums[index],
43        );
44
45        // Option 1: pay the cost here, then continue two positions ahead.
46        let result = cost + dfs(index + 2, flag);
47
48        // Option 2: if there is remaining skip budget, advance one step
49        // without paying, consuming the budget (flag becomes 0).
50        if (flag > 0) {
51            result = Math.min(result, dfs(index + 1, 0));
52        }
53
54        // Cache and return the best result for this state.
55        memo[index][flag] = result;
56        return result;
57    };
58
59    // Start at index 1. The initial flag depends on the parity of the length:
60    // (length & 1) ^ 1 yields 1 for even lengths and 0 for odd lengths.
61    return dfs(1, (length & 1) ^ 1);
62}
63

Time and Space Complexity

Time Complexity: O(n)

The recursion is memoized via @cache based on the state (i, j). The parameter i ranges over the valid indices of the array (at most n distinct values), and the parameter j only takes two possible values (0 or 1). Therefore, the total number of distinct states is O(n) × 2 = O(n). Each state performs only O(1) work (constant-time computation of cost and a fixed number of recursive lookups). Hence, the overall time complexity is O(n), where n is the length of the array.

Space Complexity: O(n)

The space is dominated by the memoization cache, which stores results for up to O(n) distinct (i, j) states. Additionally, the recursion depth can reach O(n) in the worst case, contributing O(n) to the call stack. Combining both factors, the total space complexity is O(n), where n is the length of the array.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Updating `nums` in place when computing the cost

A very tempting mistake is to actually mutate nums[index] when you "make it special," for example:

cost = max(0, max(nums[index - 1], nums[index + 1]) + 1 - nums[index])
nums[index] += cost          # ❌ WRONG: mutating shared state
result = cost + dfs(index + 2, can_skip)

Why this is wrong:

The cost of making index i special depends on its neighbors' original values, not on values that have already been raised by some earlier branch of the recursion. Because dfs explores multiple decision paths (especially in the even case where a skip can shift the chosen indices), mutating nums lets one branch corrupt the input that another branch relies on. The cached results then reflect inconsistent array states, producing wrong answers.

Solution: Treat nums as read-only. The key insight that makes this safe is that special indices never sit next to each other, so a special index i only ever depends on its two immediate neighbors, which are themselves never raised (they are the "low" elements). Therefore you never need to mutate the array at all — just compute cost from the original values and pass it up the recursion.

Pitfall 2: Misjudging the number of skips for even-length arrays

It is easy to assume the even case behaves like the odd case (no skip) or to allow an unlimited number of skips. Both are incorrect.

With odd n, picking indices 1, 3, 5, …, n-2 gives (n-1)/2 special indices with no gap wasted — every interior "odd" slot is used, so 0 skips is optimal.
With even n, you cannot tile [1, n-2] perfectly with step-2 picks; you are forced to "waste" exactly one position. Allowing more than one skip would reduce the special count below the maximum, violating goal 1; allowing zero skips is geometrically impossible.

return dfs(1, n & 1 ^ 1)   # 1 skip when n even, 0 when n odd

Solution: Lock the skip budget to exactly (n & 1) ^ 1. Note the operator precedence: & binds tighter than ^ in Python, so n & 1 ^ 1 parses as (n & 1) ^ 1, which is the intended value. If you are unsure, add the parentheses explicitly for clarity.

Pitfall 3: Off-by-one errors in the base case and index range

Two boundary conditions are easy to get wrong:

Base case index >= n - 1 — index n - 1 is the last element and can never be special, so the recursion must stop before reaching it. Writing index >= n instead would allow dfs to try making nums[n-1] special and access nums[n], causing an out-of-bounds error.
Starting at index = 1 — index 0 can never be special, so the search must begin at 1, not 0.

Solution: Anchor the recursion to the valid interior range [1, n-2]. The base case index >= n - 1 correctly excludes the final index, and the neighbor accesses nums[index - 1] and nums[index + 1] stay in bounds because index is always in [1, n-2] whenever the cost is computed.

Pitfall 4: Forgetting memoization (or caching across calls)

Without @cache, the even case branches into two recursive calls at each step (make special vs. skip), and although only one skip exists, the overlapping subproblems can still cause redundant recomputation. Conversely, using a module-level cache that persists across different nums inputs is dangerous — stale results from a previous test case would leak in.

Solution: Use @cache on the inner dfs defined inside minIncrease. Because dfs is redefined each call, its cache is fresh per input, and nums is captured by closure rather than passed as a (cached) argument — keeping the cache keyed only on (index, can_skip).

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know