LeetCode Problem 3469

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking for the minimum total cost required to remove all elements from an integer array nums under a very specific set of operations. At each step, we can either remove any two elements from the first three elements of the array, and the cost for that operation is the maximum of the two elements removed, or if fewer than three elements remain, we remove all remaining elements with the cost being the maximum of those remaining. The goal is to sequence these operations in a way that the sum of all operation costs is minimized.

The input nums is an array of integers where 1 <= nums.length <= 1000 and 1 <= nums[i] <= 10^6. The output is a single integer representing the minimum cumulative cost to remove all elements.

Important edge cases include arrays of length 1, 2, or 3, where the second operation rule applies immediately, as well as arrays where selecting the wrong pair in early steps could lead to a higher total cost later. The problem guarantees at least one element, so we do not need to handle an empty input array. You are given an array nums, and you must remove all of its elements while paying the smallest possible total cost.

The key restriction is that when the array still contains at least three elements, you are only allowed to look at the first three elements. From those three elements, you choose any two and remove them. The cost of that operation is the larger of the two removed values.

Eventually the array becomes very short. When fewer than three elements remain, you must remove all remaining elements in a single operation, and the cost becomes the maximum value among those remaining elements.

The goal is to determine the minimum total cost needed to completely remove the array.

The input is a single integer array. The output is one integer representing the minimum achievable cost.

The constraints are:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^6

The array length is only 1000, which is small enough for dynamic programming with roughly O(n^2) states, but far too large for an exhaustive search of all possible removal sequences.

A very important observation is that after every operation, exactly one element from the current first three survives and remains at the front of the array. This means the future state can be represented much more compactly than storing the entire remaining array.

Several edge cases immediately stand out:

• Arrays of length 1 must be removed in one operation.
• Arrays of length 2 must also be removed in one operation.
• Arrays of length 3 have exactly three possible choices for which two elements to remove.
• Large values near 10^6 require careful cost calculations, but standard integer types are sufficient.
• Multiple equal values can create several equivalent removal choices.

Approaches

Brute Force

A brute-force approach would try all possible sequences of pair removals from the first three elements recursively. For each step, we would remove a pair, compute the cost, and recursively solve the problem for the smaller array, keeping track of the minimum cost across all sequences. While correct, this approach has exponential time complexity because for each array of length n, there are multiple ways to pick pairs from the first three elements, leading to O(2^(n/2)) possible sequences. This is impractical for n up to 1000.

Optimal Approach

The key observation for an optimal solution is that the problem can be solved using dynamic programming. Let dp[i] represent the minimum cost to remove elements from nums[i:] to the end. At each index i, we consider removing either the first two or the first three elements (if possible) as one operation and recursively compute the cost of the remaining array. The recurrence relation is:

dp[i] = min(
    max(nums[i], nums[i+1]) + dp[i+2],
    max(nums[i], nums[i+1], nums[i+2]) + dp[i+3]  # if i+2 exists
)

For arrays shorter than 3 at the end, we simply remove all remaining elements at once, taking the maximum as the cost. We can implement this iteratively in a bottom-up manner for efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(n/2))	O(n)	Recursively tries all valid pairs
Dynamic Programming	O(n)	O(n)	Bottom-up DP based on the first 2 or 3 elements

Algorithm Walkthrough

1. Initialize a DP array of length n+1 (where n = len(nums)) with all zeros. dp[i] represents the minimum cost to remove nums[i:].
2. Iterate i from n-1 down to 0.
3. At each i, consider removing the first two elements. Compute the cost as max(nums[i], nums[i+1]) plus dp[i+2].
4. If i+2 < n, also consider removing the first three elements. Compute the cost as max(nums[i], nums[i+1], nums[i+2]) plus dp[i+3].
5. Set dp[i] to the minimum of these options.
6. Return dp[0], which contains the minimum cost to remove the entire array.

Why it works: This works because dp[i] always represents the optimal solution for the subarray starting at index i. By considering all allowed removal operations at each step and taking the minimum, we ensure that every choice is optimal globally, which is the core idea of dynamic programming. A brute force solution would recursively try every valid removal choice.

Whenever at least three elements remain, there are exactly three possibilities:

• Remove the first and second.
• Remove the first and third.
• Remove the second and third.

For each choice, we generate the new array and recursively solve the remaining problem.

This approach is correct because it explores every possible sequence of operations and takes the minimum total cost among them.

The problem is that the number of possible removal sequences grows exponentially. At every step we branch into three new possibilities, making the overall complexity roughly O(3^(n/2)). This becomes completely infeasible for n = 1000.

Dynamic Programming

The crucial observation is that we do not need to remember the entire remaining array.

Suppose we are processing the array from left to right. After each operation involving the first three elements, exactly one of those three survives.

At any point, the current state can be described by:

• One surviving element from earlier operations.
• The next unprocessed elements in the original array.

Therefore, the future only depends on:

• Which element survived.
• Which index we are currently processing.

This allows us to build a memoized dynamic programming solution where each state represents the surviving element and the current position.

Instead of exploring exponentially many arrays, we reuse overlapping subproblems and reduce the complexity to O(n^2).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^(n/2))	O(n) recursion	Tries every possible removal sequence
Optimal DP	O(n²)	O(n²)	Memoizes states defined by survivor and position

Algorithm Walkthrough

Assume we have a state dp(last, i).

Here:

• last is the index of the surviving element carried from previous operations.
• i is the first new element that has not yet been processed.

The current first three available elements are:

nums[last], nums[i], nums[i + 1]

1. Define the base cases

If i == n, only the survivor remains.

The cost is simply:

nums[last]

If i == n - 1, two elements remain:

nums[last], nums[i]

They must be removed together.

The cost is:

max(nums[last], nums[i])

2. Consider the three valid removals

When at least three elements are available, we have exactly three choices.

Current candidates:

nums[last], nums[i], nums[i + 1]

3. Remove nums[i] and nums[i + 1]

The survivor becomes nums[last].

Cost:

max(nums[i], nums[i + 1])

Transition:

dp(last, i + 2)

4. Remove nums[last] and nums[i]

The survivor becomes nums[i + 1].

Cost:

max(nums[last], nums[i])

Transition:

dp(i + 1, i + 2)

5. Remove nums[last] and nums[i + 1]

The survivor becomes nums[i].

Cost:

max(nums[last], nums[i + 1])

Transition:

dp(i, i + 2)

6. Take the minimum

The optimal answer for the state is:

min(choice1, choice2, choice3)

7. Memoize results

Many states repeat through different paths.

Store each computed result so every state is solved only once.

8. Start from the initial configuration

Initially the first three elements are:

nums[0], nums[1], nums[2]

Therefore:

dp(0, 1)

represents the entire problem.

Why it works

At every stage, the future depends only on two pieces of information:

• Which element survived from previous operations.
• Which portion of the original array has not yet been exposed.

The remaining elements always preserve their original order, so no additional information is needed. The dynamic programming state captures the complete information required to make future decisions. Since every valid choice is explored and the minimum cost is taken, the algorithm always returns the optimal answer.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def minCost(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        
        for i in range(n - 1, -1, -1):
            # Remove first two elements
            if i + 1 < n:
                cost_two = max(nums[i], nums[i+1]) + dp[i+2]
            else:
                cost_two = nums[i]
            
            # Remove first three elements
            if i + 2 < n:
                cost_three = max(nums[i], nums[i+1], nums[i+2]) + dp[i+3]
            else:
                cost_three = float('inf')
            
            dp[i] = min(cost_two, cost_three)
        
        return dp[0]

This implementation initializes a DP array of size n+1 to handle indexing safely. We iterate backwards, calculating the minimum cost at each index considering the two removal options. Edge cases where fewer than 2 or 3 elements remain are handled directly. Finally, dp[0] gives the minimum total cost.

    if n == 1:
        return nums[0]

    @lru_cache(None)
    def dp(last: int, i: int) -> int:
        if i == n:
            return nums[last]

        if i == n - 1:
            return max(nums[last], nums[i])

        option1 = max(nums[i], nums[i + 1]) + dp(last, i + 2)

        option2 = max(nums[last], nums[i]) + dp(i + 1, i + 2)

        option3 = max(nums[last], nums[i + 1]) + dp(i, i + 2)

        return min(option1, option2, option3)

    return dp(0, 1)

The implementation follows the dynamic programming formulation directly.

The memoized function `dp(last, i)` represents the minimum cost for the remaining problem when `nums[last]` is the surviving carried element and `i` points to the next unprocessed position.

The first two `if` statements implement the base cases. When only one or two elements remain, the problem rules force a single final operation, so the answer can be computed immediately.

For larger states, the code evaluates all three legal removal choices. Each choice adds the operation cost and recursively solves the resulting subproblem.

The `lru_cache` decorator ensures that every state is computed only once, turning an exponential search into a polynomial-time solution.

## Go Solution

```go
package main

import "math"

func minCost(nums []int) int {
    n := len(nums)
    dp := make([]int, n+1)

    for i := n - 1; i >= 0; i-- {
        costTwo := 0
        if i+1 < n {
            if nums[i] > nums[i+1] {
                costTwo = nums[i]
            } else {
                costTwo = nums[i+1]
            }
            costTwo += dp[i+2]
        } else {
            costTwo = nums[i]
        }

        costThree := math.MaxInt64
        if i+2 < n {
            maxVal := nums[i]
            if nums[i+1] > maxVal {
                maxVal = nums[i+1]
            }
            if nums[i+2] > maxVal {
                maxVal = nums[i+2]
            }
            costThree = maxVal + dp[i+3]
        }

        if costTwo < costThree {
            dp[i] = costTwo
        } else {
            dp[i] = costThree
        }
    }

    return dp[0]
}

In Go, we handle integer maximum values carefully and use slices for the DP array. The logic mirrors the Python version, with explicit comparisons to determine the maximum values among two or three elements.

Worked Examples

Example 1: nums = [6,2,8,4]

Step	Operation	Remaining nums	Cost	DP Value at i
0	Remove 6,8	[2,4]	8	12
1	Remove 2,4	[]	4	12

Total cost = 12

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

Step	Operation	Remaining nums	Cost	DP Value at i
0	Remove 2,1	[3,3]	2	5
1	Remove 3,3	[]	3	5

Total cost = 5 func minCost(nums []int) int { n := len(nums)

if n == 1 {
	return nums[0]
}

mem := make([][]int, n+1)
for i := range mem {
	mem[i] = make([]int, n+1)
	for j := range mem[i] {
		mem[i][j] = -1
	}
}

var max func(int, int) int
max = func(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var min3 func(int, int, int) int
min3 = func(a, b, c int) int {
	res := a
	if b < res {
		res = b
	}
	if c < res {
		res = c
	}
	return res
}

var dp func(int, int) int

dp = func(last, i int) int {
	if i == n {
		return nums[last]
	}

	if i == n-1 {
		return max(nums[last], nums[i])
	}

	if mem[last][i] != -1 {
		return mem[last][i]
	}

	option1 := max(nums[i], nums[i+1]) +
		dp(last, i+2)

	option2 := max(nums[last], nums[i]) +
		dp(i+1, i+2)

	option3 := max(nums[last], nums[i+1]) +
		dp(i, i+2)

	mem[last][i] = min3(option1, option2, option3)
	return mem[last][i]
}

return dp(0, 1)

}

The Go implementation mirrors the Python solution closely.

Since Go does not provide built in memoization, a two dimensional slice is used to store previously computed states. Every entry is initialized to `-1`, which is safe because all valid costs are positive.

Go's `int` type is sufficient because the maximum possible answer is at most `1000 * 10^6`, which comfortably fits within a 64 bit integer and also fits on modern 64 bit Go platforms.

## Worked Examples

### Example 1

Input:

nums = [6, 2, 8, 4]

Initial state:

dp(0, 1)

Candidates: 6, 2, 8

| Choice | Removed | Cost | Survivor | Next State |
| --- | --- | --- | --- | --- |
| A | 2, 8 | 8 | 6 | dp(0, 3) |
| B | 6, 2 | 6 | 8 | dp(2, 3) |
| C | 6, 8 | 8 | 2 | dp(1, 3) |

Evaluate each branch:

| State | Remaining Elements | Cost |
| --- | --- | --- |
| dp(0,3) | [6,4] | 6 |
| dp(2,3) | [8,4] | 8 |
| dp(1,3) | [2,4] | 4 |

Totals:

| Choice | Immediate Cost | Future Cost | Total |
| --- | --- | --- | --- |
| A | 8 | 6 | 14 |
| B | 6 | 8 | 14 |
| C | 8 | 4 | 12 |

Minimum:

12

### Example 2

Input:

nums = [2, 1, 3, 3]

Initial state:

dp(0, 1)

Candidates: 2, 1, 3

| Choice | Removed | Cost | Survivor | Next State |
| --- | --- | --- | --- | --- |
| A | 1, 3 | 3 | 2 | dp(0,3) |
| B | 2, 1 | 2 | 3 | dp(2,3) |
| C | 2, 3 | 3 | 1 | dp(1,3) |

Future costs:

| State | Remaining Elements | Cost |
| --- | --- | --- |
| dp(0,3) | [2,3] | 3 |
| dp(2,3) | [3,3] | 3 |
| dp(1,3) | [1,3] | 3 |

Totals:

| Choice | Immediate | Future | Total |
| --- | --- | --- | --- |
| A | 3 | 3 | 6 |
| B | 2 | 3 | 5 |
| C | 3 | 3 | 6 |

Answer:

5

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | We iterate through the array once and compute max for at most three elements at each step. |
| Space | O(n) | DP array of size n+1 stores the minimum cost for each subarray starting index. |

The solution is efficient because the DP approach avoids redundant computations of overlapping subproblems.
| Time | O(n²) | There are O(n²) possible `(last, i)` states, each solved once |
| Space | O(n²) | Memoization table stores O(n²) states |

The state is defined by two indices. The survivor index can take at most `n` values, and the processing index can also take at most `n` values. Therefore the total number of states is `O(n²)`. Each state performs only constant work because it evaluates exactly three transitions.

## Test Cases

Provided examples

assert Solution().minCost([6,2,8,4]) == 12 # Example 1 assert Solution().minCost([2,1,3,3]) == 5 # Example 2

Edge cases

assert Solution().minCost([1]) == 1 # Single element assert Solution().minCost([5,5]) == 5 # Two equal elements assert Solution().minCost([1,2,3]) == 3 # Three increasing elements assert Solution().minCost([10,1,10,1]) == 12 # Alternating high-low assert Solution().minCost([1]*1000) == 500 # Large uniform array

| Test | Why |
| --- | --- |
| `[6,2,8,4]` | Provided example to validate basic DP calculation |
| `[2,1,3,3]` | Provided example with repeated elements |
| `[1]` | Edge case: minimum length array |
| `[5,5]` | Edge case: two elements with same value |
| `[1,2,3]` | Edge case: three elements where max removal affects final cost |
| `[10,1,10,1]` | Alternating high-low values, ensures optimal pairing |
| `[1]*1000` | Stress test with large array, tests efficiency |

## Edge Cases

**Single element array:** If the array has only one element, the removal cost is simply the value of that element. The implementation handles this with the base case in DP where `dp[i] = nums[i]` if there is no second element.

**Two elements array:** The only valid operation is to remove both
sol = Solution()

assert sol.minCost([6, 2, 8, 4]) == 12  # provided example 1
assert sol.minCost([2, 1, 3, 3]) == 5   # provided example 2

assert sol.minCost([5]) == 5            # single element
assert sol.minCost([4, 9]) == 9         # two elements

assert sol.minCost([1, 2, 3]) == 4      # exactly three elements

assert sol.minCost([10, 10, 10]) == 20  # all equal values

assert sol.minCost([1, 100, 1, 100]) == 101  # alternating extremes

assert sol.minCost([8, 1, 2, 3]) == 10  # survivor choice matters

assert sol.minCost([7, 6, 5, 4, 3]) == 14  # odd length array

assert sol.minCost([1, 2, 3, 4, 5, 6]) == 9  # increasing sequence

assert sol.minCost([6, 5, 4, 3, 2, 1]) == 12  # decreasing sequence

Test Summary

Test	Why
[6,2,8,4]	Official example
[2,1,3,3]	Official example
[5]	Smallest valid input
[4,9]	Two element base case
[1,2,3]	Exactly three elements
[10,10,10]	Duplicate values
[1,100,1,100]	Large value differences
[8,1,2,3]	Tests survivor selection
[7,6,5,4,3]	Odd length processing
[1,2,3,4,5,6]	Increasing order
[6,5,4,3,2,1]	Decreasing order

Edge Cases

One important edge case is when the array contains only one element. A buggy implementation might still try to form a group of three elements and access invalid indices. The solution handles this naturally through the base case, returning the single value as the final cost.

Another important case occurs when exactly two elements remain. According to the rules, they must be removed together in one operation. The implementation explicitly checks i == n - 1 and returns the maximum of those two remaining values.

A third edge case involves arrays with many equal values. Multiple removal choices can produce identical immediate costs, which may cause redundant exploration in a naive recursive solution. Memoization ensures that repeated states are computed only once, preventing exponential blowup.

A fourth subtle case is when keeping a large value alive temporarily leads to a smaller overall answer. Greedy strategies often fail because the cheapest immediate removal is not always globally optimal. The dynamic programming approach evaluates all valid survivor choices and therefore correctly finds the minimum total cost regardless of future consequences.