Problem

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 (toany 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 theminimum total space wasted if you can resize the array at most k times.

Note: The array can have any size at the start and doesnot count towards the number of resizing operations.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4
5

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.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 10^6
  • 0 <= k <= nums.length - 1

Solution

Method 1 – Dynamic Programming with Partitioning

Intuition

We want to minimize wasted space by optimally partitioning the array into at most k+1 segments, each with a fixed size. For each segment, the best size is the maximum value in that segment. We use DP to try all possible partitions efficiently.

Approach

  1. Define dp[i][k] as the minimum wasted space for the first i elements with k resizes.
  2. For each position, try all possible previous partition points and update the DP value.
  3. For each segment, compute the wasted space as (max in segment) * length - sum of segment.
  4. The answer is dp[n][k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(k+2, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                int mx = 0, sum = 0;
                for (int l = i; l >= 1; --l) {
                    mx = max(mx, nums[l-1]);
                    sum += nums[l-1];
                    if (dp[l-1][j] != INT_MAX)
                        dp[i][j+1] = min(dp[i][j+1], dp[l-1][j] + mx * (i-l+1) - sum);
                }
            }
        }
        int ans = INT_MAX;
        for (int j = 1; j <= k+1; ++j) ans = min(ans, dp[n][j]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func MinSpaceWastedKResizing(nums []int, k int) int {
    n := len(nums)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+2)
        for j := range dp[i] {
            dp[i][j] = 1<<60
        }
    }
    dp[0][0] = 0
    for i := 1; i <= n; i++ {
        for j := 0; j <= k; j++ {
            mx, sum := 0, 0
            for l := i; l >= 1; l-- {
                if nums[l-1] > mx { mx = nums[l-1] }
                sum += nums[l-1]
                if dp[l-1][j] < 1<<60 {
                    if dp[i][j+1] > dp[l-1][j]+mx*(i-l+1)-sum {
                        dp[i][j+1] = dp[l-1][j]+mx*(i-l+1)-sum
                    }
                }
            }
        }
    }
    ans := 1<<60
    for j := 1; j <= k+1; j++ {
        if dp[n][j] < ans { ans = dp[n][j] }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minSpaceWastedKResizing(int[] nums, int k) {
        int n = nums.length;
        int[][] dp = new int[n+1][k+2];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                int mx = 0, sum = 0;
                for (int l = i; l >= 1; l--) {
                    mx = Math.max(mx, nums[l-1]);
                    sum += nums[l-1];
                    if (dp[l-1][j] != Integer.MAX_VALUE)
                        dp[i][j+1] = Math.min(dp[i][j+1], dp[l-1][j] + mx * (i-l+1) - sum);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 1; j <= k+1; j++) ans = Math.min(ans, dp[n][j]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun minSpaceWastedKResizing(nums: IntArray, k: Int): Int {
        val n = nums.size
        val dp = Array(n+1) { IntArray(k+2) { Int.MAX_VALUE } }
        dp[0][0] = 0
        for (i in 1..n) {
            for (j in 0..k) {
                var mx = 0
                var sum = 0
                for (l in i downTo 1) {
                    mx = maxOf(mx, nums[l-1])
                    sum += nums[l-1]
                    if (dp[l-1][j] != Int.MAX_VALUE)
                        dp[i][j+1] = minOf(dp[i][j+1], dp[l-1][j] + mx * (i-l+1) - sum)
                }
            }
        }
        var ans = Int.MAX_VALUE
        for (j in 1..k+1) ans = minOf(ans, dp[n][j])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List
class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[float('inf')] * (k+2) for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1, n+1):
            for j in range(k+1):
                mx, s = 0, 0
                for l in range(i, 0, -1):
                    mx = max(mx, nums[l-1])
                    s += nums[l-1]
                    if dp[l-1][j] != float('inf'):
                        dp[i][j+1] = min(dp[i][j+1], dp[l-1][j] + mx * (i-l+1) - s)
        return min(dp[n][1:])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn min_space_wasted_k_resizing(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let k = k as usize;
        let mut dp = vec![vec![i32::MAX; k+2]; n+1];
        dp[0][0] = 0;
        for i in 1..=n {
            for j in 0..=k {
                let mut mx = 0;
                let mut sum = 0;
                for l in (1..=i).rev() {
                    mx = mx.max(nums[l-1]);
                    sum += nums[l-1];
                    if dp[l-1][j] != i32::MAX {
                        dp[i][j+1] = dp[i][j+1].min(dp[l-1][j] + mx * (i-l+1) - sum);
                    }
                }
            }
        }
        let mut ans = i32::MAX;
        for j in 1..=k+1 { ans = ans.min(dp[n][j]); }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minSpaceWastedKResizing(nums: number[], k: number): number {
        const n = nums.length;
        const dp = Array.from({length: n+1}, () => Array(k+2).fill(Infinity));
        dp[0][0] = 0;
        for (let i = 1; i <= n; i++) {
            for (let j = 0; j <= k; j++) {
                let mx = 0, sum = 0;
                for (let l = i; l >= 1; l--) {
                    mx = Math.max(mx, nums[l-1]);
                    sum += nums[l-1];
                    if (dp[l-1][j] !== Infinity)
                        dp[i][j+1] = Math.min(dp[i][j+1], dp[l-1][j] + mx * (i-l+1) - sum);
                }
            }
        }
        let ans = Infinity;
        for (let j = 1; j <= k+1; j++) ans = Math.min(ans, dp[n][j]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * k) — For each DP state, we scan up to n previous positions.
  • 🧺 Space complexity: O(n * k) — For the DP table.