Minimum Total Space Wasted With K Resizing Operations

You have an array nums where nums[i] represents the number of elements you need to store at time step i. You can resize your container at most k times. Between resizes the container size stays fixed at whatever you set it to, and it must be large enough to hold the maximum value in that segment. Any extra capacity is wasted. Find the minimum total wasted space across all time steps.

This is LeetCode 1959: Minimum Total Space Wasted With K Resizing Operations, and it is a clean example of interval DP combined with partitioning. If you have solved Coin Change or Edit Distance, you already know how to fill a DP table. This problem asks you to partition an array into at most k + 1 contiguous segments and minimize the total waste across all of them.

Why this problem matters

This problem sits at the intersection of two important DP ideas:

• Partitioning into contiguous segments: you are dividing a sequence into groups where each group has a cost, and you want to minimize total cost.
• Interval cost computation: the cost of each segment depends on the max and sum of a subarray, which you can precompute efficiently.

These ideas show up in many other problems. Splitting a string into palindromes, splitting an array into subarrays with bounded sums, allocating tasks across workers. Once you see the partition DP template here, you will recognize it everywhere.

The key insight

Think of k resizes as k + 1 segments. You are choosing where to place k dividers in the array. Each segment gets a container sized to the maximum value in that segment, and the waste for a segment from index l to r is:

cost(l, r) = max(nums[l..r]) * (r - l + 1) - sum(nums[l..r])

The total container capacity minus the total actual usage. Your goal is to place dividers to minimize the sum of these costs.

Building the solution

Define dp[j][i] as the minimum wasted space for nums[0..i] using at most j + 1 segments (meaning j resizes).

Base case (j = 0): With no resizes, you have one segment covering the entire prefix nums[0..i]. The container size is max(nums[0..i]) and the waste is max * (i + 1) - sum(nums[0..i]).

Transition (j > 0): Try every possible split point m where the last segment starts at m + 1:

dp[j][i] = min over all m in [0, i-1] of (dp[j-1][m] + cost(m+1, i))

You are saying: "use j - 1 resizes on nums[0..m], then let the last segment be nums[m+1..i]." You try every possible m and pick the one that gives the least total waste.

Precomputation: You can precompute prefix sums so that sum(nums[l..r]) is O(1). For the segment max, you can compute it on the fly as you iterate m backwards from i - 1 down to 0, maintaining a running max.

The solution

def min_space_wasted_k_resizing(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    def cost(l, r, seg_max):
        return seg_max * (r - l + 1) - (prefix[r + 1] - prefix[l])

    INF = float('inf')
    dp = [[INF] * n for _ in range(k + 1)]

    running_max = 0
    for i in range(n):
        running_max = max(running_max, nums[i])
        dp[0][i] = cost(0, i, running_max)

    for j in range(1, k + 1):
        for i in range(n):
            seg_max = nums[i]
            for m in range(i - 1, -1, -1):
                dp[j][i] = min(dp[j][i], dp[j - 1][m] + cost(m + 1, i, seg_max))
                seg_max = max(seg_max, nums[m])
            if j > 0:
                dp[j][i] = min(dp[j][i], dp[j - 1][i])

    return dp[k][n - 1]

Step-by-step walkthrough

Let's trace through nums = [10, 20, 15, 30, 20] with k = 1.

The final answer is dp[1][4] = 25. The optimal split is [10, 20, 15] | [30, 20]. The first segment has a container of size 20 (waste = 60 - 45 = 15) and the second segment has a container of size 30 (waste = 60 - 50 = 10). Total waste = 25.

Notice how the DP table builds from left to right and from fewer resizes to more resizes. Each cell considers all possible places to put the last divider, which is the classic partition DP pattern.

Complexity analysis

Where n is the length of nums and k is the number of allowed resizes.

The inner loop iterates backward through all possible split points for each (j, i) pair, giving O(n) work per cell. There are O(k * n) cells, so the total is O(k * n^2). This fits within the LeetCode constraints where n is at most 200 and k is at most n - 1.

Edge cases

• k = 0: No resizes allowed. The container must hold max(nums) for the entire array. Total waste is max(nums) * n - sum(nums).
• k >= n - 1: You can resize before every time step, so the container always matches the current value exactly. Total waste is 0.
• All elements equal: Every partition has zero waste, so the answer is always 0 regardless of k.
• Single element: Waste is always 0 since the container is exactly nums[0].
• Decreasing array: The max is always the first element when no resizing is done. Resizing at the right points removes the large prefix from dominating later segments.

The building blocks

This problem uses partition DP, which is a variation of interval DP. The core template is:

• State: dp[j][i] = optimal cost for the first i + 1 elements using at most j + 1 partitions.
• Transition: Try all split points m and take dp[j-1][m] + cost(m+1, i).
• Base case: dp[0][i] = cost of one segment covering the entire prefix.

You will see this exact structure in:

• Split Array Largest Sum (LeetCode 410): partition into k subarrays to minimize the maximum subarray sum. Same DP skeleton, different cost function.
• Palindrome Partitioning II (LeetCode 132): partition a string into palindromes with minimum cuts. The cost function checks for palindromes instead of computing waste.
• Burst Balloons (LeetCode 312): an interval DP where you choose which element to process last in each segment.

The partition DP template is one of the most reusable patterns in competitive programming and interviews.

From understanding to recall

You can follow the walkthrough above and see how each cell gets filled. But can you reproduce the recurrence from scratch? The gap between "I understand it" and "I can write it in an interview" is real.

The key things to internalize: the state is (number of resizes used, rightmost index). The transition tries every split point. The cost function uses the segment max and segment sum. Once those three pieces click, you can reconstruct the entire solution without looking at notes. Spaced repetition makes that happen faster than rereading the explanation ten times in a row.

Related posts

• Coin Change - Bottom-up DP with a similar table-filling approach, just a different cost structure
• Edit Distance - 2D DP where each cell depends on previously computed values, same mental model as partition DP
• Best Time to Buy and Sell Stock III - Another problem where you partition decisions into a fixed number of transactions