Find Minimum Cost to Remove Array Elements solution and explanation
Google
4 more videos on this problem
3469. Find Minimum Cost to Remove Array Elements | DP (Memoization)Aryan Mittal · 16:18 · 2K views
3469. Find Minimum Cost to Remove Array Elements (Leetcode Medium)Programming Live with Larry · 19:25 · 489 views
Find Minimum Cost to Remove Array Elements (Leetcode Biweekly 151)Soumya Bhattacharjee · 6:39 · 410 views
Leetcode Biweekly 151 : Q3. Find Minimum Cost to Remove Array ElementsWannaBeCM · 7:24 · 127 views
Biweekly Contest 151 | First 3 Problems - 3467, 3468 & 3469 | LeetcodeAmit Choraria · 27:34 · 120 views
The problem
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:
- Choose any two elements from the first three elements of
numsand remove them. The cost of this operation is the maximum of the two elements removed. - If fewer than three elements remain in
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].
- In the first operation, remove
nums[0] = 6andnums[2] = 8with a cost ofmax(6, 8) = 8. Now,nums = [2, 4]. - In the second operation, remove the remaining elements with a cost of
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].
- In the first operation, remove
nums[0] = 2andnums[1] = 1with a cost ofmax(2, 1) = 2. Now,nums = [3, 3]. - In the second operation remove the remaining elements with a cost of
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] <= 106
Approach overview
Problem 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| 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 |
Frequently asked questions
Is Find Minimum Cost to Remove Array Elements easy or hard?
The problem is rated Medium but has a relatively low acceptance rate because the optimal solution requires modeling the process as a dynamic programming state. Once the carry-over state and three-choice transition are recognized, the implementation becomes straightforward.
Find Minimum Cost to Remove Array Elements Python/Java solution
Implement a recursive DP with memoization. The function tracks the current index and the carried value, tries all valid removal pairs from the three available elements, and returns the minimum cost. The same logic translates directly across Python, Java, C++, and Go using maps or arrays for caching.
How to solve Find Minimum Cost to Remove Array Elements in O(n)?
Use a DP function such as dp(i, carry) representing the minimum cost starting at index i with a carried element from the previous step. At each step you form three candidates (carry, nums[i], nums[i+1]) and try removing any two. The cost of each operation is the maximum of the removed elements. Memoizing the results ensures each state is solved once, giving O(n) time complexity.
What is the best approach for Find Minimum Cost to Remove Array Elements?
The most effective solution uses dynamic programming with memoization. The state tracks the current index and the element carried from the previous step. For each state, evaluate the three possible pairs that can be removed from the first three elements and pick the minimum total cost. This reduces the complexity to roughly O(n) time with O(n) space.
Is Find Minimum Cost to Remove Array Elements asked at Google/Amazon/Meta?
Problems with this structure appear frequently in interviews at large tech companies because they test dynamic programming and state modeling. Variants involving minimizing cost while choosing elements from a sliding window or limited set are common at companies like Amazon, Google, and Meta.
What data structure is used in Find Minimum Cost to Remove Array Elements?
The main technique is dynamic programming with memoization, typically implemented using a hash map or a 2D DP table to cache states. The algorithm processes the array sequentially while tracking a carried element between steps.
What is the time complexity of Find Minimum Cost to Remove Array Elements?
The optimal dynamic programming solution runs in O(n) time because each index and carry state is computed once and stored using memoization. The brute force recursive approach is exponential, roughly O(3^n), because it explores all pair-removal combinations without caching results.