Watch 5 video solutions for Find Minimum Cost to Remove Array Elements, a medium level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 2,565 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. Your task is to remove all elements from the array by performing one of the following operations at each step until nums is empty:
nums and remove them. The cost of this operation is the maximum of the two elements removed.nums, remove all the remaining elements in a single operation. The cost of this operation is the maximum of the remaining elements.Return the minimum cost required to remove all the elements.
Example 1:
Input: nums = [6,2,8,4]
Output: 12
Explanation:
Initially, nums = [6, 2, 8, 4].
nums[0] = 6 and nums[2] = 8 with a cost of max(6, 8) = 8. Now, nums = [2, 4].max(2, 4) = 4.The cost to remove all elements is 8 + 4 = 12. This is the minimum cost to remove all elements in nums. Hence, the output is 12.
Example 2:
Input: nums = [2,1,3,3]
Output: 5
Explanation:
Initially, nums = [2, 1, 3, 3].
nums[0] = 2 and nums[1] = 1 with a cost of max(2, 1) = 2. Now, nums = [3, 3].max(3, 3) = 3.The cost to remove all elements is 2 + 3 = 5. This is the minimum cost to remove all elements in nums. Hence, the output is 5.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 106Problem Overview: You are given an array where elements must be removed under a specific rule: at each step you remove two elements from the first three available elements, and the cost of that operation equals the max of the removed values. The process continues until fewer than three elements remain, and the final removal cost equals the maximum of the remaining elements. The goal is to minimize the total removal cost.
Approach 1: Brute Force Simulation with Recursion (Exponential Time, O(3^n) time, O(n) space)
The straightforward strategy is to simulate every possible removal choice. From the first three elements, you can remove any pair: (0,1), (0,2), or (1,2). After removing a pair, the remaining element becomes the first element of the next step when the next array element shifts in. A recursive function explores all valid choices and accumulates costs. This guarantees the correct answer but repeatedly recomputes the same states, causing exponential growth as the array grows.
Approach 2: Dynamic Programming with Memoization (Optimal) (O(n) time, O(n) space)
The key observation is that the process only depends on the current index and the single leftover element carried from the previous step. When you process position i, you effectively have three candidates: the carried element and nums[i], nums[i+1]. You remove any two of them and keep the third as the carry for the next state. This naturally forms overlapping subproblems.
Define a DP state like dp(i, carry) representing the minimum cost starting from index i when carry is the element left from the previous step. For each state, try all three possible pairs to remove, compute the operation cost using max, and recurse with the remaining value as the next carry. Memoizing this state avoids recomputation and reduces the complexity to linear in practice.
This approach relies on careful state transitions and caching. The number of states is bounded by the array length and possible carry positions, making it efficient even for larger inputs. The technique is a typical example of state compression in Dynamic Programming combined with sequential processing of an Array. You repeatedly evaluate small local choices while preserving the globally optimal result.
Recommended for interviews: The dynamic programming approach with memoization is what interviewers expect. Brute force shows that you understand the decision space, but recognizing overlapping subproblems and reducing them using DP demonstrates stronger problem-solving skill and familiarity with DP patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(3^n) | O(n) | Useful for understanding the decision tree and verifying small cases |
| Dynamic Programming with Memoization | O(n) | O(n) | Best general solution; avoids recomputation and handles large arrays efficiently |