# Minimum Total Space Wasted With K Resizing Operations LeetCode Solution

Difficulty Level Medium

## Problem Statement

Minimum Total Space Wasted With K Resizing Operations LeetCode Solution – 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``size`t, 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 the time `t` is defined as `size`t` - 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.

nums= [10, 20]

k = 0

10

nums= [1,2,3]

k = 0

10

## Explanation for Minimum Total Space Wasted With K Resizing Operations LeetCode Solution:

i) For the 1st test case, we can set the initial size to be 20. The total wasted space is (20 – 10) + (20 – 20) = 10

ii) For the 2nd test case, we can set the initial size to be 20 and resize it to 30 at time 2. The total wasted space is (20 – 10) + (20 – 20) + (30 – 30) = 10

### Approach

Idea

1. Let `dp(i, k)` denote the minimum space wasted if we can resize `k` times of `nums[i..n-1]`.
2. The idea is that when we do use a resize option to adapt all elements in `nums[i..j]`, we need to pick the `size` equal to the maximum number in `nums[i..j]` so the total space wasted is `max(nums[i...j]) * (j-i+1) - sum(nums[i..j)`.

## Code for Minimum Total Space Wasted With K Resizing Operations LeetCode Solution

### Java Program

```class Solution {
int n, INF = (int) (200 * 1e6);
Integer[][] memo = new Integer[200][200];
public int minSpaceWastedKResizing(int[] nums, int k) {
n = nums.length;
return dp(nums, 0, k);
}
int dp(int[] nums, int i, int k) {
if (i == n) return 0;
if (k == -1) return INF;
if (memo[i][k] != null) return memo[i][k];
int ans = INF, maxNum = nums[i], totalSum = 0;
for (int j = i; j < n; ++j) {
maxNum = Math.max(maxNum, nums[j]);
totalSum += nums[j];
int wasted = maxNum * (j - i + 1) - totalSum;
ans = Math.min(ans, dp(nums, j + 1, k - 1) + wasted);
}
return memo[i][k] = ans;
}
}```

### C++ Program

```class Solution {
public:
int n, INF = 200 * 1e6;
int memo[200][200] = {};
int minSpaceWastedKResizing(vector<int> &nums, int k) {
memset(memo, -1, sizeof(memo));
n = nums.size();
return dp(nums, 0, k);
}
int dp(vector<int> &nums, int i, int k) {
if (i == n) return 0;
if (k == -1) return INF;
if (memo[i][k] != -1) return memo[i][k];
int ans = INF, maxNum = nums[i], totalSum = 0;
for (int j = i; j < n; ++j) {
maxNum = max(maxNum, nums[j]);
totalSum += nums[j];
int wasted = maxNum * (j - i + 1) - totalSum;
ans = min(ans, dp(nums, j + 1, k - 1) + wasted);
}
return memo[i][k] = ans;
}
};```

### Python Program

```class Solution:
def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
n, INF = len(nums), 200 * 1e6

@lru_cache(None)
def dp(i, k):
if i == n: return 0
if k == -1: return INF
ans = INF
maxNum = nums[i]
totalSum = 0
for j in range(i, n):
maxNum = max(maxNum, nums[j])
totalSum += nums[j]
wasted = maxNum * (j - i + 1) - totalSum
ans = min(ans, dp(j + 1, k - 1) + wasted)
return ans

return dp(0, k)```

## Complexity Analysis for Subarray Product Less Than K LeetCode Solution

### Time Complexity

O(N^2*K), where N <= 200 is the number of elements in the array nums, K < N is the maximum number of resizing options we can use. There are total N*K dp states, they are dp[0][0], dp[0][1].., dp[N][K]. Each state needs a loop O(N) to compute the result. So total time complexity is O(N^2*K).

### Space Complexity

The space complexity of the above code is O(N*K).

Translate »