1959. Minimum Total Space Wasted With K Resizing Operations LeetCode Solution
In this guide, you will get 1959. Minimum Total Space Wasted With K Resizing Operations LeetCode Solution with the best time and space complexity. The solution to Minimum Total Space Wasted With K Resizing Operations 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 Minimum Total Space Wasted With K Resizing Operations
You are currently designing a dynamic array. You are given a 0-indexed integer array nums, where nums[i] is the number of elements that will be in the array at time i. In addition, you are given an integer k, the maximum number of times you can resize the array (to any size).
The size of the array at time t, sizet, must be at least nums[t] because there needs to be enough space in the array to hold all the elements. The space wasted at time t is defined as sizet – nums[t], and the total space wasted is the sum of the space wasted across every time t where 0 <= t < nums.length.
Return the minimum total space wasted if you can resize the array at most k times.
Note: The array can have any size at the start and does not count towards the number of resizing operations.
Input: nums = [10,20], k = 0
Output: 10
Explanation: size = [20,20].
We can set the initial size to be 20.
The total wasted space is (20 – 10) + (20 – 20) = 10.
Example 2:
Input: nums = [10,20,30], k = 1
Output: 10
Explanation: size = [20,20,30].
We can set the initial size to be 20 and resize to 30 at time 2.
The total wasted space is (20 – 10) + (20 – 20) + (30 – 30) = 10.
Example 3:
Input: nums = [10,20,15,30,20], k = 2
Output: 15
Explanation: size = [10,20,20,30,30].
We can set the initial size to 10, resize to 20 at time 1, and resize to 30 at time 3.
The total wasted space is (10 – 10) + (20 – 20) + (20 – 15) + (30 – 30) + (30 – 20) = 15.
1959. Minimum Total Space Wasted With K Resizing Operations LeetCode Solution in C++
class Solution {
public:
int minSpaceWastedKResizing(vector<int>& nums, int k) {
vector<vector<int>> mem(nums.size(), vector<int>(k + 1, -1));
return minSpaceWasted(nums, 0, k, mem);
}
private:
static constexpr int kMax = 200'000'000;
// Returns the minimum space wasted for nums[i..n) if you can resize k times.
int minSpaceWasted(const vector<int>& nums, int i, int k,
vector<vector<int>>& mem) {
if (i == nums.size())
return 0;
if (k == -1)
return kMax;
if (mem[i][k] != -1)
return mem[i][k];
int res = kMax;
int sum = 0;
int maxNum = nums[i];
for (int j = i; j < nums.size(); ++j) {
sum += nums[j];
maxNum = max(maxNum, nums[j]);
const int wasted = maxNum * (j - i + 1) - sum;
res = min(res, minSpaceWasted(nums, j + 1, k - 1, mem) + wasted);
}
return mem[i][k] = res;
}
}; /* code provided by PROGIEZ */
1959. Minimum Total Space Wasted With K Resizing Operations LeetCode Solution in Java
class Solution {
public int minSpaceWastedKResizing(int[] nums, int k) {
Integer[][] mem = new Integer[nums.length][k + 1];
return minSpaceWasted(nums, 0, k, mem);
}
private static final int kMax = 200_000_000;
// Returns the minimum space wasted for nums[i..n) if you can resize k times.
private int minSpaceWasted(int[] nums, int i, int k, Integer[][] mem) {
if (i == nums.length)
return 0;
if (k == -1)
return kMax;
if (mem[i][k] != null)
return mem[i][k];
int res = kMax;
int sum = 0;
int maxNum = nums[i];
for (int j = i; j < nums.length; ++j) {
sum += nums[j];
maxNum = Math.max(maxNum, nums[j]);
final int wasted = maxNum * (j - i + 1) - sum;
res = Math.min(res, minSpaceWasted(nums, j + 1, k - 1, mem) + wasted);
}
return mem[i][k] = res;
}
} // code provided by PROGIEZ
1959. Minimum Total Space Wasted With K Resizing Operations LeetCode Solution in Python
class Solution:
def minSpaceWastedKResizing(self, nums: list[int], k: int) -> int:
kMax = 200_000_000
@functools.lru_cache(None)
def dp(i: int, k: int) -> int:
"""
Returns the minimum space wasted for nums[i..n) if you can resize k times.
"""
if i == len(nums):
return 0
if k == -1:
return kMax
res = kMax
summ = 0
maxNum = nums[i]
for j in range(i, len(nums)):
summ += nums[j]
maxNum = max(maxNum, nums[j])
wasted = maxNum * (j - i + 1) - summ
res = min(res, dp(j + 1, k - 1) + wasted)
return res
return dp(0, k) # code by PROGIEZ
