Minimum Total Space Wasted With K Resizing Operations

Minimum Total Space Wasted With K Resizing Operations - Problem

You are designing a dynamic array that changes size over time. Given a 0-indexed integer array nums where nums[i] represents the number of elements that will be in the array at time i, and an integer k representing the maximum number of resize operations allowed.

At each time t, the array size size[t] must be at least nums[t] to hold all elements. The space wasted at time t is size[t] - nums[t]. Your goal is to minimize the total space wasted across all time periods.

Return the minimum total space wasted if you can resize the array at most k times.

Note: The initial array size can be any value and does not count as a resize operation.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,20,30], k = 1

› Output: 10

💡 Note: Optimal strategy: Resize after first element. Segment [10] wastes 0, segment [20,30] uses size 30 and wastes 30-20=10. Total waste = 0+10 = 10.

Example 2 — No Resize Better

$ Input: nums = [20,15,8,2], k = 3

› Output: 0

💡 Note: With k=3 resize operations, we can create 4 segments: [20], [15], [8], [2]. Each segment has waste = max_val × length - sum = element × 1 - element = 0. Total waste = 0+0+0+0 = 0.

Example 3 — Multiple Resizes

$ Input: nums = [10,20], k = 1

› Output: 0

💡 Note: Two segments: [10] wastes 0, [20] wastes 0. Total waste = 0.

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁶
0 ≤ k ≤ nums.length - 1

Visualization

Tap to expand

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is to partition the timeline into segments where each segment uses a fixed array size equal to the maximum needed in that period. The optimal approach uses 2D Dynamic Programming to find the best way to place at most k resize operations. Time: O(n²×k), Space: O(n²+n×k).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n² × k)	O(n × k + n²)	Cache recursive results to avoid recomputation
2D Dynamic Programming (Bottom-Up)	O(n² × k)	O(n × k + n²)	Build solution using 2D DP table iteratively
Brute Force Recursion	O(n^k)	O(k)	Try all possible ways to place k resize operations

Memoization (Top-Down DP) — Algorithm Steps

Use recursion with memoization
Cache results by state (pos, k)
Precompute segment costs for efficiency

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Costs

Calculate waste for all possible segments

Memoize States

Cache results for each (position, operations) pair

Reuse Results

Lookup cached values instead of recomputing

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int waste[200][200];
int memo[200][200];
bool computed[200][200];

int solve(int pos, int operationsLeft, int n) {
    if (pos >= n) return 0;
    if (operationsLeft == 0) {
        return waste[pos][n-1];
    }
    
    if (computed[pos][operationsLeft]) {
        return memo[pos][operationsLeft];
    }
    
    int minWaste = INT_MAX;
    for (int end = pos; end < n; end++) {
        int currentWaste = waste[pos][end];
        int remainingWaste = end + 1 < n ? solve(end + 1, operationsLeft - 1, n) : 0;
        if (currentWaste + remainingWaste < minWaste) {
            minWaste = currentWaste + remainingWaste;
        }
    }
    
    computed[pos][operationsLeft] = true;
    memo[pos][operationsLeft] = minWaste;
    return minWaste;
}

int solution(int* nums, int numsSize, int k) {
    int n = numsSize;
    
    // Initialize computed array
    memset(computed, false, sizeof(computed));
    
    // Precompute waste for all segments
    for (int i = 0; i < n; i++) {
        int maxVal = nums[i];
        int total = nums[i];
        waste[i][i] = 0;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > maxVal) maxVal = nums[j];
            total += nums[j];
            waste[i][j] = maxVal * (j - i + 1) - total;
        }
    }
    
    return solve(0, k + 1, n);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[200];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && numsSize < 200) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

n×k states, each tries n positions, with O(1) segment cost lookup

⚠ Quadratic Growth

Space Complexity

O(n × k + n²)

Memoization table O(n×k) plus precomputed costs O(n²)

⚠ Quadratic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler