3469. Find Minimum Cost to Remove Array Elements LeetCode Solution
In this guide, you will get 3469. Find Minimum Cost to Remove Array Elements LeetCode Solution with the best time and space complexity. The solution to Find Minimum Cost to Remove Array Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Minimum Cost to Remove Array Elements
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 nums and 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.
In the first operation, remove nums[0] = 6 and nums[2] = 8 with a cost of max(6, 8) = 8. Now, nums = [2, 4].
In the second operation, remove the remaining elements with a cost of max(2, 4) = 4.
In the first operation, remove nums[0] = 2 and nums[1] = 1 with a cost of max(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 <= 1000
1 <= nums[i] <= 106
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
3469. Find Minimum Cost to Remove Array Elements LeetCode Solution in C++
class Solution {
public:
// Main function to start the calculation
int minCost(vector<int>& nums) {
const int n = nums.size();
vector<vector<int>> mem(n + 1, vector<int>(n + 1, -1));
return minCost(/*last=*/0, 1, nums, mem);
}
private:
int minCost(int last, int i, vector<int>& nums, vector<vector<int>>& mem) {
const int n = nums.size();
if (i == n) // Single element left.
return nums[last];
if (i == n - 1) // Two elements left.
return max(nums[last], nums[i]);
if (mem[i][last] != -1)
return mem[i][last];
const int a = max(nums[i], nums[i + 1]) + minCost(last, i + 2, nums, mem);
const int b = max(nums[last], nums[i]) + minCost(i + 1, i + 2, nums, mem);
const int c = max(nums[last], nums[i + 1]) + minCost(i, i + 2, nums, mem);
return mem[i][last] = min({a, b, c});
}
}; /* code provided by PROGIEZ */
3469. Find Minimum Cost to Remove Array Elements LeetCode Solution in Java
class Solution {
public int minCost(int[] nums) {
final int n = nums.length;
Integer[][] mem = new Integer[n + 1][n + 1];
return minCost(/*last=*/0, 1, nums, mem);
}
private int minCost(int last, int i, int[] nums, Integer[][] mem) {
final int n = nums.length;
if (i == n) // Single element left.
return nums[last];
if (i == n - 1) // Two elements left.
return Math.max(nums[last], nums[i]);
if (mem[i][last] != null)
return mem[i][last];
final int a = Math.max(nums[i], nums[i + 1]) + minCost(last, i + 2, nums, mem);
final int b = Math.max(nums[last], nums[i]) + minCost(i + 1, i + 2, nums, mem);
final int c = Math.max(nums[last], nums[i + 1]) + minCost(i, i + 2, nums, mem);
return mem[i][last] = Math.min(a, Math.min(b, c));
}
} // code provided by PROGIEZ
3469. Find Minimum Cost to Remove Array Elements LeetCode Solution in Python
class Solution:
def minCost(self, nums: list[int]) -> int:
n = len(nums)
@functools.lru_cache(None)
def dp(last: int, i: int) -> int:
if i == n: # Single element left.
return nums[last]
if i == n - 1: # Two elements left.
return max(nums[last], nums[i])
a = max(nums[i], nums[i + 1]) + dp(last, i + 2)
b = max(nums[last], nums[i]) + dp(i + 1, i + 2)
c = max(nums[last], nums[i + 1]) + dp(i, i + 2)
return min(a, b, c)
return dp(0, 1) # code by PROGIEZ
