Minimum total space wasted with k resizing operations

Array Dynamic Programming Prefix Sum

43.9% acceptance

Feb 25, 2026

593

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_space_wasted_k_resizing(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    // dp[i][j] = min wasted space for nums[0..=i] with j resizes
    // We have k+1 segments total (initial + k resizes)
    let inf = i32::MAX / 2;
    let mut dp = vec![vec![inf; k + 2]; n];
    
    // Base case: one segment from 0 to i (0 resizes)
    let mut max_val = 0i64;
    let mut sum = 0i64;
    for i in 0..n {
      max_val = max_val.max(nums[i] as i64);
      sum += nums[i] as i64;
      dp[i][0] = (max_val * (i as i64 + 1) - sum) as i32;
    }
    
    // Fill dp
    for j in 1..=k {
      for i in j..n {
        // The last segment starts at some index m+1 and ends at i
        let mut max_val = 0i64;
        let mut seg_sum = 0i64;
        for m in (j - 1..i).rev() {
          max_val = max_val.max(nums[m + 1] as i64);
          seg_sum += nums[m + 1] as i64;
          let waste = max_val * (i - m) as i64 - seg_sum;
          if dp[m][j - 1] < inf {
            dp[i][j] = dp[i][j].min(dp[m][j - 1] + waste as i32);
          }
        }
      }
    }
    
    let mut ans = inf;
    for j in 0..=k {
      ans = ans.min(dp[n - 1][j]);
    }
    ans
  }
}