Minimum Total Space Wasted With K Resizing Operations Solution
Minimum Total Space Wasted With K Resizing Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Total Space Wasted With K Resizing Operations is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are designing a dynamic buffer. nums[t] is the number of elements it must hold at time t. At every time t the buffer's size size_t must be at least nums[t], and the space wasted at time t is size_t - nums[t]. The total waste is the sum over all times.
The initial size can be anything and is free. After that, you may resize the buffer at most k times (each resize sets a new size of your choice).
Return the minimum possible total waste.
Example 1
Input: nums = [10,20], k = 0
Output: 10
Explanation: Without resizing the size must be 20 throughout, wasting 10 at time 0.
Example 2
Input: nums = [10,20,30], k = 1
Output: 10
Explanation: Size 20 for times 0–1, then resize to 30.
Example 3
Input: nums = [10,20,15,30,20], k = 2
Output: 15
Explanation: Sizes 10 | 20, 20 | 30, 30: waste 0 + 5 + 10.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 10^60 <= k <= nums.length - 1
Hints for Minimum Total Space Wasted With K Resizing Operations
Hint 1
With
rresizes the timeline splits into at mostr + 1consecutive segments, each with one fixed size.Hint 2
Within a segment the best size is the segment's maximum, so its waste is
max · length − sum.Hint 3
Let
dp[i][j]be the least waste for the firstitimes split intojsegments; try every start of the last segment.
How to solve Minimum Total Space Wasted With K Resizing Operations
Resizing at most k times means cutting the array into at most k + 1 contiguous blocks. Each block uses its own maximum as the size, wasting max · len − sum. The task becomes a classic partition DP.
Approach
dp[0][0] = 0, every other entry ∞.- For each prefix length
i, scan the last block's startpfromi - 1down to 0, maintaining the block's maximum and sum, sowaste(p, i-1)is O(1) per step. - For every block count
j = 1..k+1:dp[i][j] = min(dp[i][j], dp[p][j-1] + waste(p, i-1)). - Return
min over j ≤ k+1 of dp[n][j].
Why it works
Any schedule with at most k resizes is a partition into at most k + 1 blocks, and for a fixed partition setting each block to its maximum is optimal (smaller is illegal, larger only wastes more). The DP enumerates every partition's last block and reuses the optimal cost of the prefix before it.
Complexity
- Time —
O(n² · k) - Space —
O(n · k)
Pitfalls
kresizes givek + 1blocks — the initial size is free.- Using fewer resizes than allowed is fine; take the minimum over all block counts up to
k + 1. - The total waste fits in 32 bits (at most
200 · 10^6), butmax · lenmust not be accumulated carelessly in a type narrower than that.
Reference solution
Python
from typing import List
def minSpaceWastedKResizing(nums: List[int], k: int) -> int:
n = len(nums)
segs = k + 1
INF = 10**18
dp = [[INF] * (segs + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
mx = 0
total = 0
for p in range(i - 1, -1, -1):
if nums[p] > mx:
mx = nums[p]
total += nums[p]
waste = mx * (i - p) - total
prev = dp[p]
cur = dp[i]
for j in range(1, segs + 1):
if prev[j - 1] + waste < cur[j]:
cur[j] = prev[j - 1] + waste
return min(dp[n][1:])Java
public static int minSpaceWastedKResizing(int[] nums, int k) {
int n = nums.length, segs = k + 1;
final int INF = Integer.MAX_VALUE;
int[][] dp = new int[n + 1][segs + 1];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int mx = 0, total = 0;
for (int p = i - 1; p >= 0; p--) {
mx = Math.max(mx, nums[p]);
total += nums[p];
int waste = mx * (i - p) - total;
for (int j = 1; j <= segs; j++) {
if (dp[p][j - 1] == INF) continue;
dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + waste);
}
}
}
int best = INF;
for (int j = 1; j <= segs; j++) best = Math.min(best, dp[n][j]);
return best;
}C++
int minSpaceWastedKResizing(vector<int>& nums, int k) {
int n = nums.size(), segs = k + 1;
const long long INF = LLONG_MAX / 4;
vector<vector<long long>> dp(n + 1, vector<long long>(segs + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
long long mx = 0, total = 0;
for (int p = i - 1; p >= 0; p--) {
mx = max(mx, (long long) nums[p]);
total += nums[p];
long long waste = mx * (i - p) - total;
for (int j = 1; j <= segs; j++) {
dp[i][j] = min(dp[i][j], dp[p][j - 1] + waste);
}
}
}
long long best = INF;
for (int j = 1; j <= segs; j++) best = min(best, dp[n][j]);
return (int) best;
}JavaScript
var minSpaceWastedKResizing = function(nums, k) {
var n = nums.length, segs = k + 1;
var dp = [];
for (var i = 0; i <= n; i++) dp.push(new Array(segs + 1).fill(Infinity));
dp[0][0] = 0;
for (i = 1; i <= n; i++) {
var mx = 0, total = 0;
for (var p = i - 1; p >= 0; p--) {
if (nums[p] > mx) mx = nums[p];
total += nums[p];
var waste = mx * (i - p) - total;
for (var j = 1; j <= segs; j++) {
if (dp[p][j - 1] + waste < dp[i][j]) dp[i][j] = dp[p][j - 1] + waste;
}
}
}
var best = Infinity;
for (j = 1; j <= segs; j++) if (dp[n][j] < best) best = dp[n][j];
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming