Minimum Total Space Wasted With K Resizing Operations

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, size_t, 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 size_t - 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
Inputnums = [10,20], k = 0
Output10
We can set the initial size to 20, so the total wasted space is (20 - 10) + (20 - 20) = 10.
Example 2
Inputnums = [10,20,30], k = 1
Output10
We can set the initial size to be 20 and resize to 30 at time 2, so the total wasted space is (20 - 10) + (20 - 20) + (30 - 30) = 10.

Constraints

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

Asked at 1 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate