# Minimum Total Space Wasted With K Resizing Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimum-total-space-wasted-with-k-resizing-operations
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## 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 (to **any** 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 _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.

**Example 1:**

**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:**

**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:**

**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] <= 106`
* `0 <= k <= nums.length - 1`

# Approaches
## Brute-Force Recursion
This approach involves exploring all possible ways to partition the array `nums`. Since we can perform at most `k` resizes, this is equivalent to partitioning the array into at most `k+1` contiguous segments. A brute-force recursive method can be designed to try every valid partition, calculate the total wasted space for each, and return the minimum among them.
**Time:** Exponential, roughly O(n * C(n-1, k)). The function explores all ways to choose `k` split points from `n-1` possible locations, leading to a combinatorial explosion of calls. · **Space:** O(n), for the depth of the recursion stack in the worst case.
**Pros:** Conceptually simple and directly follows the problem's definition.
**Cons:** Extremely inefficient due to recomputing the same subproblems multiple times.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We can define a recursive function `solve(i, k_rem)` that computes the minimum wasted space for the subarray starting at index `i` with `k_rem` resizes available. 

In this function, we iterate through all possible split points `j` from `i` to `n-1`. Each `j` defines a segment `nums[i...j]`. For this segment, we set the array size to be the maximum element within it to minimize waste for that segment. The waste is `max(nums[i...j]) * length - sum(nums[i...j])`. After this segment, we recursively call the function for the remaining part of the array `nums[j+1:]` with `k_rem - 1` resizes.

The base cases for the recursion are when we've processed the whole array (`i == n`), in which case the waste is 0, or when we've run out of resizes (`k_rem < 0`), which is an invalid path.

This method explores the entire search space of partitions, but its overlapping subproblems cause a massive number of redundant calculations, leading to an exponential time complexity.
### Algorithm
*   Define a recursive function, let's say `solve(i, k_rem)`, which calculates the minimum wasted space for the subarray `nums[i:]` with `k_rem` resizing operations remaining.
*   **Base Cases:**
    *   If `i` reaches the end of the array (`i == n`), it means we have successfully partitioned the entire array, so the waste is 0.
    *   If `k_rem` becomes negative, it means we have used more than `k` resizes, which is an invalid state. Return a value representing infinity.
*   **Recursive Step:**
    *   To find the minimum waste for `nums[i:]`, we can try all possible endpoints `j` for the current partition, which starts at `i`. The partition would be `nums[i...j]`.
    *   For each `j` from `i` to `n-1`:
        *   Calculate the cost for this partition. The optimal size for this segment is `max(nums[i...j])`. The wasted space is `max(nums[i...j]) * (j - i + 1) - sum(nums[i...j])`.
        *   Recursively call the function for the rest of the array: `solve(j + 1, k_rem - 1)`. Note that one resize operation is consumed.
        *   The total waste for this choice of `j` is `cost + solve(j + 1, k_rem - 1)`.
    *   The function returns the minimum total waste found among all possible choices for `j`.
*   The initial call to the function would be `solve(0, k)`.

## Dynamic Programming
The problem exhibits optimal substructure and overlapping subproblems, which is a clear indicator for dynamic programming. We can solve this by building a table `dp[i][k]` that stores the minimum wasted space for the prefix of the array `nums[0...i]` using `k` resizes. By iterating through all possible endpoints of the last segment, we can build up the solution.
**Time:** O(n^2 * k). There are three nested loops: over `k` (number of resizes), `i` (end of prefix), and `j` (start of the last segment). · **Space:** O(n * k) for the DP table. This can be optimized to O(n) by only storing the DP states for the previous and current number of resizes.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough to pass the given constraints.; Can be space-optimized from O(n*k) to O(n).
**Cons:** The O(n^2 * k) complexity might be too slow if constraints were slightly larger.
### Explanation
We define `dp[i][k]` as the minimum wasted space for the subarray `nums[0...i]` with `k` resizes. Our goal is to find `dp[n-1][k]`.

The base case is for `k=0` resizes. This means the entire prefix `nums[0...i]` is treated as a single block. The array size must be `max(nums[0...i])` for this whole duration. The waste is `dp[i][0] = max(nums[0...i]) * (i+1) - sum(nums[0...i])`.

For `k > 0`, we build upon previous results. To calculate `dp[i][k]`, we assume the last resize happened at some index `j` (`1 <= j <= i`). This creates a final segment `nums[j...i]`. The total waste is the sum of the waste from the prefix `nums[0...j-1]` using `k-1` resizes (which is `dp[j-1][k-1]`) and the waste from the segment `nums[j...i]`. We try all possible split points `j` and take the minimum.

The recurrence is `dp[i][k] = min_{1 <= j <= i} (dp[j-1][k-1] + cost(j, i))`. We can implement this with three nested loops. The space complexity can be optimized from `O(n*k)` to `O(n)` since computing the `k`-th column only requires the `(k-1)`-th column.

```java
class Solution {
    public int minSpaceWastedKResizing(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        int sum = 0;
        int maxVal = 0;
        // Base case: k = 0 resizes
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            maxVal = Math.max(maxVal, nums[i]);
            dp[i] = maxVal * (i + 1) - sum;
        }

        // Iterate for k = 1 to K resizes
        for (int ki = 1; ki <= k; ki++) {
            int[] next_dp = new int[n];
            Arrays.fill(next_dp, Integer.MAX_VALUE);
            for (int i = 1; i < n; i++) {
                int currentSum = 0;
                int currentMax = 0;
                // j is the start of the last segment
                for (int j = i; j >= 1; j--) {
                    currentSum += nums[j];
                    currentMax = Math.max(currentMax, nums[j]);
                    int cost = currentMax * (i - j + 1) - currentSum;
                    if (dp[j - 1] != Integer.MAX_VALUE) {
                        next_dp[i] = Math.min(next_dp[i], dp[j - 1] + cost);
                    }
                }
            }
            dp = next_dp;
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Let `dp[i][k]` be the minimum total wasted space for the prefix `nums[0...i]` using exactly `k` resizing operations.
*   The size of our DP table will be `n x (k+1)`.
*   **Base Case (k=0):**
    *   If we use 0 resizes, the entire prefix `nums[0...i]` must be one segment. 
    *   `dp[i][0] = max(nums[0...i]) * (i + 1) - sum(nums[0...i])`. This can be calculated for all `i` from 0 to `n-1`.
*   **State Transition (k > 0):**
    *   To compute `dp[i][k]`, we consider all possible split points `j` for the last segment. The last segment is `nums[j...i]` (for `j > 0`).
    *   This implies that a resize happened at index `j`, and the prefix `nums[0...j-1]` was handled with `k-1` resizes.
    *   The recurrence relation is: `dp[i][k] = min_{1 <= j <= i} (dp[j-1][k-1] + cost(j, i))`, where `cost(j, i)` is the waste for the segment `nums[j...i]`.
*   **Calculation:**
    *   We can implement this bottom-up. Iterate `ki` from 1 to `k`. For each `ki`, iterate `i` from 1 to `n-1`. For each `i`, iterate `j` from `i` down to 1 to find the minimum.
    *   The `cost(j, i)` can be computed efficiently inside the `j` loop by maintaining a running sum and maximum.
*   **Final Answer:** The result is `dp[n-1][k]`.
*   **Space Optimization:** Notice that `dp[...][k]` only depends on `dp[...][k-1]`. We can optimize space to `O(n)` by using two 1D arrays, one for the previous `k` state and one for the current.

## DP with Divide and Conquer Optimization
The standard `O(n^2 * k)` DP can be further optimized. The calculation of each row of the DP table, `dp[...][k]`, from the previous row `dp[...][k-1]` can be accelerated from `O(n^2)` to `O(n log n)`. This is possible due to a property of the cost function which implies that the optimal choice of the last partition point is monotonic. This allows for a 'Divide and Conquer' optimization strategy.
**Time:** O(n * k * log n). Building the RMQ structure takes `O(n log n)`. Then, for each of the `k` resizes, the divide and conquer DP calculation takes `O(n log n)`. · **Space:** O(n * k) or O(n * log n). The DP table takes `O(n*k)` (or `O(n)` if optimized), and the Sparse Table for RMQ requires `O(n log n)` space.
**Pros:** Asymptotically faster than the standard DP approach.; Provides a significant performance improvement for larger `n`.
**Cons:** Significantly more complex to understand and implement correctly.; The proof that the optimal split point is monotonic is non-trivial.; Requires auxiliary data structures like a Sparse Table for efficient RMQ.
### Explanation
This approach, also known as Knuth-Yao DP optimization (though more commonly applied via the Divide and Conquer trick), speeds up the computation of DP states. The key insight is that for a fixed number of resizes `k`, the optimal position `j` to make the `(k-1)`-th resize for computing `dp[i][k]` is non-decreasing as `i` increases.

Let `opt[i][k]` be the smallest `j` that minimizes `dp[j-1][k-1] + cost(j, i)`. The property is `opt[i][k] <= opt[i+1][k]`. This allows us to constrain the search space for the optimal `j`.

We define a recursive function, say `compute(i_start, i_end, j_start, j_end)`, which calculates `dp[i][k]` for all `i` in `[i_start, i_end]`. The `j_start` and `j_end` parameters provide a restricted range where the optimal split point `j` must lie. We first find the optimal split `opt_j` for the midpoint `i_mid`. Due to the monotonicity, the optimal split for any `i < i_mid` must be in `[j_start, opt_j]`, and for any `i > i_mid`, it must be in `[opt_j, j_end]`. This allows us to solve the subproblems recursively with smaller search ranges.

For this to be efficient, calculating `cost(j, i)` must be fast. We can precompute prefix sums for `O(1)` range sum queries and build a Sparse Table for `O(1)` Range Maximum Queries. The Sparse Table construction takes `O(n log n)`. The `compute` function for each `k` then takes `O(n log n)`. The total time complexity becomes `O(n * k * log n)`.
### Algorithm
*   The DP recurrence is `dp[i][k] = min_{0 <= j < i} (dp[j][k-1] + cost(j, i-1))`.
*   This structure is a candidate for Divide and Conquer Optimization if the optimal split point, `opt[i] = argmin_{j} (dp[j][k-1] + cost(j, i-1))`, is monotonic with `i` (i.e., `opt[i] <= opt[i+1]`). This property holds for this problem's cost function.
*   **Algorithm:**
    *   For each number of resizes `ki` from 1 to `k`, we compute the `dp[...][ki]` array from `dp[...][ki-1]`.
    *   Instead of nested loops, we use a recursive helper function: `compute(i_start, i_end, j_start, j_end)`.
    *   This function computes `dp[i][ki]` for `i` in `[i_start, i_end]`, given that their optimal split points `j` are in `[j_start, j_end]`.
    *   **Inside `compute`:**
        1.  Find the midpoint `i_mid = (i_start + i_end) / 2`.
        2.  Find the optimal split point `opt_j` for `i_mid` by iterating `j` from `j_start` to `min(i_mid - 1, j_end)`.
        3.  Set `dp[i_mid][ki]` to the minimum value found.
        4.  Recursively call `compute` for the left part: `compute(i_start, i_mid - 1, j_start, opt_j)`.
        5.  Recursively call `compute` for the right part: `compute(i_mid + 1, i_end, opt_j, j_end)`.
*   To make `cost(j, i)` calculation efficient (`O(1)`), we can precompute prefix sums for the sum part and use a Sparse Table or Segment Tree for Range Maximum Queries (RMQ).

# Solutions
### Java

```java
class Solution {
public
  int minSpaceWastedKResizing(int[] nums, int k) {
    ++k;
    int n = nums.length;
    int[][] g = new int[n][n];
    for (int i = 0; i < n; ++i) {
      int s = 0, mx = 0;
      for (int j = i; j < n; ++j) {
        s += nums[j];
        mx = Math.max(mx, nums[j]);
        g[i][j] = mx * (j - i + 1) - s;
      }
    }
    int[][] f = new int[n + 1][k + 1];
    int inf = 0x3f3f3f3f;
    for (int i = 0; i < f.length; ++i) {
      Arrays.fill(f[i], inf);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i; ++h) {
          f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]);
        }
      }
    }
    return f[n][k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSpaceWastedKResizing(vector<int> &nums, int k) {
    ++k;
    int n = nums.size();
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      int s = 0, mx = 0;
      for (int j = i; j < n; ++j) {
        mx = max(mx, nums[j]);
        s += nums[j];
        g[i][j] = mx * (j - i + 1) - s;
      }
    }
    int inf = 0x3f3f3f3f;
    vector<vector<int>> f(n + 1, vector<int>(k + 1, inf));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i; ++h) {
          f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]);
        }
      }
    }
    return f[n][k];
  }
};

```

### Python

```python
class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int: k += 1 n = len(nums) g = [[0] * n for _ in range(n)] for i in range(n): s = mx = 0 for j in range(i, n): s += nums[j] mx = max(mx, nums[j]) g[i][j] = mx * (j - i + 1) - s f = [[inf] * (k + 1) for _ in range(n + 1)] f[0][0] = 0 for i in range(1, n + 1): for j in range(1, k + 1): for h in range(i): f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]) return f[- 1][- 1]

```