Minimum Total Space Wasted With K Resizing Operations

Medium
1485.

Minimum Total Space Wasted With K Resizing Operations

Minimum Total Space Wasted With K Resizing Operations is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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 <= 200
  • 1 <= nums[i] <= 10^6
  • 0 <= k <= nums.length - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minSpaceWastedKResizing = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 200
  • 1 <= nums[i] <= 10^6
  • 0 <= k <= nums.length - 1

Hints for Minimum Total Space Wasted With K Resizing Operations

  1. Hint 1

    With r resizes the timeline splits into at most r + 1 consecutive segments, each with one fixed size.

  2. Hint 2

    Within a segment the best size is the segment's maximum, so its waste is max · length − sum.

  3. Hint 3

    Let dp[i][j] be the least waste for the first i times split into j segments; 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

  1. dp[0][0] = 0, every other entry ∞.
  2. For each prefix length i, scan the last block's start p from i - 1 down to 0, maintaining the block's maximum and sum, so waste(p, i-1) is O(1) per step.
  3. For every block count j = 1..k+1: dp[i][j] = min(dp[i][j], dp[p][j-1] + waste(p, i-1)).
  4. 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

  • k resizes give k + 1 blocks — 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), but max · len must 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