1959. Minimum Total Space Wasted With K Resizing Operations

Problem Description

The problem involves designing a dynamic array that can accommodate a varying number of elements at different times. A dynamic array is an array that can change its size during the execution of a program. We have an array called nums where nums[i] represents the number of elements in the array at time i. Additionally, the array can be resized up to k times.

A resize operation can change the array's size to any number, and the size after each resize or at each time needs to be at least as large as the number of elements specified at that time (i.e., nums[t]). The efficiency of our dynamic array design is measured by the amount of "space wasted," which is the unused capacity at each point in time. The goal is to minimize the total space wasted after all the insertions, given the constraint that the array can be resized at most k times.

Intuition

The intuition behind the solution is to use dynamic programming to explore different ways of resizing the dynamic array while keeping track of the space wasted. Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable when the problem can be divided into overlapping sub-problems with the optimal structure.

Firstly, the concept of precomputing the space wasted for all possible subarray lengths is employed. This calculation is stored in a 2D array (matrix g), where g[i][j] gives the space wasted for a subarray starting at index i and ending at index j. This is done by iterating over each subarray, tracking the maximum element (mx) within that subarray, and calculating the cumulative sum (s) of elements. The space wasted is then the maximum element times the length of the subarray minus the sum of elements in the subarray.

After calculating the space wasted for all subarrays, dynamic programming is used to find the minimum total space wasted with exactly j resizes (j <= k+1). To do this, another 2D array (matrix f) is used, where f[i][j] represents the minimum space wasted for the first i elements with j resizes.

The transition function for dynamic programming is the core part that gradually builds up the solution. It iterates over all possible combinations of array sizes and resizes and computes the minimum possible space wasted. In the end, f[n][k+1] holds the answer to the problem – the minimum total space wasted after optimizing the resizing operations, given the constraints provided by the nums array and the k value.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The implemented solution follows a dynamic programming approach that consists of the following steps:

Pre-compute wasted space for subarrays: We start by creating a 2D array (matrix g) of size n x n (n being the length of the nums array). g[i][j] represents the space wasted for a continuous subarray starting at index i and ending at index j. To fill in the matrix, we iterate through all possible starting and ending indices. For each subarray defined by (i,j), we calculate the accumulated sum s of all elements and keep track of the maximum element mx. Using these values, we calculate the wasted space as mx * (j - i + 1) - s.
Dynamic programming (DP) to minimize total wasted space: Next, we create a 2D DP array (matrix f) with n + 1 rows (for n elements) and k + 1 columns (for k resize operations allowed). Each cell f[i][j] represents the minimum total space wasted with i elements and j resizes. The matrix is initialized with inf, representing a large number since we want to minimize the space wasted. The first row of the matrix is initialized to 0 because no space is wasted before any elements are added.
Building the solution from sub-problems: The solution iterates over each possible number of elements (i, from 1 to n) and each possible number of resizes (j, from 1 to k + 1). For each pair (i, j), it explores the possibility of making a resize at every previous position h (from 0 to i - 1). It then uses the pre-computed g[h][i - 1] to find the total wasted space if we did the last resize at position h. We determine the minimum space wasted as:
```
1f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
```
Finding the result: After filling the f matrix using the above relation, the minimum space wasted with n elements and k resizes is found at f[n][k + 1], which is then returned as the result.

In summary, the solution employs dynamic programming with pre-computation and iteration over sub-problems to find the minimum space wasted given a set of constraints. By breaking down the problem in this way, it effectively handles the complexity of determining when and how to resize the dynamic array optimally.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Example Walkthrough

Let's apply the solution approach to a small example to illustrate it better.

Suppose we have the following array nums: [3, 1, 5, 4], which indicates the number of elements in the array at each time i. We are also given that we can resize the dynamic array up to k = 2 times.

Step 1: Pre-compute wasted space for subarrays

We begin by creating a matrix g with the dimensions 4x4 (n x n, where n is the length of the nums array). The matrix g will help us know the wasted space for any subarray (i, j).

We calculate the wasted space for all subarrays. For example, g[0][2] corresponds to the subarray [3, 1, 5]. The maximum element mx is 5, and the total number of elements s sum to 9. The space wasted will be 5 * 3 - 9 = 6.

This step is repeated to fill out the entire matrix g.

Step 2: Dynamic programming to minimize total wasted space

Now, we create a matrix f with dimensions 5x3 (n+1 x k+1) to store the minimum total space wasted for i elements with j resizes. Initially, f is filled with a large value (e.g., inf), except f[0][*], which is filled with 0 since no space is wasted before any elements are added.

Step 3: Building the solution from sub-problems

We populate the f matrix based on the previously calculated values in g. For each i and j, we look back at each possible 'last resize' point h:

Consider f[4][2]: we explore h = 0, h = 1, h = 2, and h = 3.

Using the previous state f[h][j - 1] and adding the wasted space of the subarray from h to i-1 (obtained from g[h][i - 1]), we update f[i][j] to the minimum of these values.

As an example, let's look at the case when j = 2 (meaning one resize has already been done) and i = 4:

Without any previous resizes, f[4][2] would initially be inf.
Consider the resize at h = 2, we take f[2][1] (the best case of no resizes up to 2 elements) and add the waste from resizing at that point for the rest of the elements: g[2][3].
We do this for all h and keep the minimum value in f[4][2].

Step 4: Finding the result

After completing the f matrix, we find the minimum space wasted with n = 4 elements and k = 2 resizes at f[4][3] since we indexed our resizes starting from 1 up to k+1.

By iterating over the sub-problems and combining their results, we are able to establish the entire space wasted and then select the minimum. The result in f[4][3] gives us the minimum total space wasted for our nums array with k = 2 resizes. This demonstrates the application of dynamic programming to efficiently solve the problem.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def min_space_wasted_k_resizing(self, nums: List[int], k: int) -> int:
6        # Allow k resizings (plus one to account for zero indexing)
7        k += 1
8        n = len(nums)
9        # Initialize a grid to store the wasted space between every pair of indices
10        wasted_space_grid = [[0] * n for _ in range(n)]
11
12        # Pre-calculate the wasted space for all possible segments
13        for start_index in range(n):
14            total_segment_sum = 0  # Sum of elements in the current segment
15            max_element = 0        # Max element in the current segment
16          
17            for end_index in range(start_index, n):
18                total_segment_sum += nums[end_index]
19                max_element = max(max_element, nums[end_index])
20                # Calculate the wasted space for the current segment
21                segment_length = end_index - start_index + 1
22                wasted_space = max_element * segment_length - total_segment_sum
23                wasted_space_grid[start_index][end_index] = wasted_space
24      
25        # Initialize a DP table for the minimum wasted space
26        min_waste_dp = [[inf] * (k + 1) for _ in range(n + 1)]
27        min_waste_dp[0][0] = 0
28      
29        # DP to find the minimum wasted space with up to k resizings
30        for i in range(1, n + 1):
31            for resizing_count in range(1, k + 1):
32                for prev_partition_end in range(i):
33                    # Update the DP table entry with the minimum wasted space
34                    waste_with_prev_partition = min_waste_dp[prev_partition_end][resizing_count - 1]
35                    current_waste = waste_with_prev_partition + wasted_space_grid[prev_partition_end][i - 1]
36                    min_waste_dp[i][resizing_count] = min(min_waste_dp[i][resizing_count], current_waste)
37      
38        # Return the minimum wasted space after n elements and k resizings
39        return min_waste_dp[-1][-1]
40
41# Example usage:
42# solution = Solution()
43# print(solution.min_space_wasted_k_resizing(nums=[10, 20], k=0))
44

1class Solution {
2    public int minSpaceWastedKResizing(int[] nums, int k) {
3        k++; // Increment k because we can make "k+1" partitions
4        int n = nums.length; // Length of the nums array
5        int[][] wastedSpaceGrid = new int[n][n]; // 2D array to record wasted space for segments
6
7        // Pre-compute wasted space for each segment [i, j]
8        for (int i = 0; i < n; ++i) {
9            int sum = 0, maxNum = 0;
10            for (int j = i; j < n; ++j) {
11                sum += nums[j];
12                maxNum = Math.max(maxNum, nums[j]);
13                wastedSpaceGrid[i][j] = maxNum * (j - i + 1) - sum;
14            }
15        }
16
17        // f[i][j] represents the minimum wasted space using j resizings up to the i-th element
18        int[][] dp = new int[n + 1][k + 1];
19        int infinity = Integer.MAX_VALUE; // Using a large number to represent infinity
20      
21        // Initialize the dp array with infinity
22        for (int i = 0; i < dp.length; ++i) {
23            Arrays.fill(dp[i], infinity);
24        }
25        dp[0][0] = 0; // Base case: 0 wasted space with 0 elements and 0 resizings
26
27        // Fill up the DP table
28        for (int i = 1; i <= n; ++i) {
29            for (int j = 1; j <= k; ++j) {
30                for (int h = 0; h < i; ++h) {
31                    // Calculate minimum wasted space for dp[i][j]
32                    dp[i][j] = Math.min(dp[i][j], dp[h][j - 1] + wastedSpaceGrid[h][i - 1]);
33                }
34            }
35        }
36      
37        // Return minimum wasted space with n elements and k resizings
38        return dp[n][k];
39    }
40}
41

1class Solution {
2public:
3    int minSpaceWastedKResizing(vector<int>& nums, int k) {
4        ++k; // Incrementing k because we can perform k+1 operations
5        int n = nums.size(); // n is the size of the input array nums
6
7        // g will store the extra space wasted for each subarray
8        vector<vector<int>> wastedSpace(n, vector<int>(n));
9
10        // Calculating the amount of space wasted if we resize from i to j
11        for (int start = 0; start < n; ++start) {
12            int sum = 0, maxElement = 0;
13            for (int end = start; end < n; ++end) {
14                maxElement = max(maxElement, nums[end]);
15                sum += nums[end];
16                wastedSpace[start][end] = maxElement * (end - start + 1) - sum;
17            }
18        }
19
20        int infinity = 0x3f3f3f3f; // Using a large number to represent infinity
21        // f will store the minimum wasted space for subarrays with different numbers of resizing operations
22        vector<vector<int>> minWastedSpace(n + 1, vector<int>(k + 1, infinity));
23        minWastedSpace[0][0] = 0; // Base case: no numbers and no operations equals zero wasted space
24
25        // Calculating the minimum wasted space for each subarray with j operations
26        for (int i = 1; i <= n; ++i) {
27            for (int operations = 1; operations <= k; ++operations) {
28                for (int previousIndex = 0; previousIndex < i; ++previousIndex) {
29                    minWastedSpace[i][operations] = min(
30                        minWastedSpace[i][operations], 
31                        minWastedSpace[previousIndex][operations - 1] + wastedSpace[previousIndex][i - 1]
32                    );
33                }
34            }
35        }
36
37        // The answer is the minimum wasted space for the whole array with k operations
38        return minWastedSpace[n][k];
39    }
40};
41

1function minSpaceWastedKResizing(nums: number[], k: number): number {
2    k++; // Incrementing k because we can perform k+1 operations
3    const n: number = nums.length; // n is the size of the input array nums
4
5    // wastedSpace will store the extra space wasted for each subarray
6    let wastedSpace: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
7
8    // Calculating the amount of space wasted if we resize from i to j
9    for (let start = 0; start < n; ++start) {
10        let sum: number = 0, maxElement: number = 0;
11        for (let end = start; end < n; ++end) {
12            maxElement = Math.max(maxElement, nums[end]);
13            sum += nums[end];
14            wastedSpace[start][end] = maxElement * (end - start + 1) - sum;
15        }
16    }
17
18    const infinity: number = Infinity; // Using Infinity to represent a very large number
19    // minWastedSpace will store the minimum wasted space for subarrays with different numbers of resizing operations
20    let minWastedSpace: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(infinity));
21    minWastedSpace[0][0] = 0; // Base case: no numbers and no operations equals zero wasted space
22
23    // Calculating the minimum wasted space for each subarray with j operations
24    for (let i = 1; i <= n; ++i) {
25        for (let operations = 1; operations <= k; ++operations) {
26            for (let previousIndex = 0; previousIndex < i; ++previousIndex) {
27                minWastedSpace[i][operations] = Math.min(
28                    minWastedSpace[i][operations],
29                    minWastedSpace[previousIndex][operations - 1] + wastedSpace[previousIndex][i - 1]
30                );
31            }
32        }
33    }
34
35    // The answer is the minimum wasted space for the whole array with k operations
36    return minWastedSpace[n][k];
37}
38

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several nested loops:

There are two loops used to fill in the g matrix, which stores the space wasted if we resize the array from i to j. The outer loop runs n times, and the inner loop runs at most n times in the worst case, resulting in a time complexity of O(n^2) for this part.
There are three loops used to calculate the minimum space wasted with k resizings in matrix f:
- The outermost loop runs n + 1 times (accounting for i from 1 to n).
- The middle loop runs k + 1 times, since k is incremented at the beginning (k += 1).
- The innermost loop runs up to i times, which in the worst case would be n times.
Combining these loops, we get a time complexity of O(n^2 * (k + 1)) for this second part.

Combining both parts, the total time complexity is O(n^2 + n^2 * (k + 1)), which simplifies to O(n^2 * k).

Space Complexity

The space complexity is determined by the space needed to store the matrices g and f:

The g matrix is n by n, so it requires O(n^2) space.
The f matrix is (n + 1) by (k + 1), so it requires O(n * k) space.

The total space complexity is O(n^2 + n * k). Since in most cases k would be less than n, this simplifies to O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1959. Minimum Total Space Wasted With K Resizing Operations

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Pre-compute wasted space for subarrays

Step 2: Dynamic programming to minimize total wasted space

Step 3: Building the solution from sub-problems

Step 4: Finding the result

Solution Implementation

Time and Space Complexity