Minimum Total Space Wasted With K Resizing Operations LeetCode Solution

Difficulty Level Medium
Frequently asked in Media.netViews 1594

Problem Statement

Minimum Total Space Wasted With K Resizing Operations LeetCode Solution – 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 the 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.

Minimum Total Space Wasted With K Resizing Operations LeetCode Solution

Example

Test Case 1:

Input:

nums= [10, 20]

k = 0

Output:

10

Test Case 2:

nums= [1,2,3]

k = 0

Output:

10

Explanation for Minimum Total Space Wasted With K Resizing Operations LeetCode Solution:

i) For the 1st test case, we can set the initial size to be 20. The total wasted space is (20 – 10) + (20 – 20) = 10

ii) For the 2nd test case, we can set the initial size to be 20 and resize it to 30 at time 2. The total wasted space is (20 – 10) + (20 – 20) + (30 – 30) = 10

Approach

Idea

  1. Let dp(i, k) denote the minimum space wasted if we can resize k times of nums[i..n-1].
  2. The idea is that when we do use a resize option to adapt all elements in nums[i..j], we need to pick the size equal to the maximum number in nums[i..j] so the total space wasted is max(nums[i...j]) * (j-i+1) - sum(nums[i..j).

Code for Minimum Total Space Wasted With K Resizing Operations LeetCode Solution

Java Program

class Solution {
    int n, INF = (int) (200 * 1e6);
    Integer[][] memo = new Integer[200][200];
    public int minSpaceWastedKResizing(int[] nums, int k) {
        n = nums.length;
        return dp(nums, 0, k);
    }
    int dp(int[] nums, int i, int k) {
        if (i == n) return 0;
        if (k == -1) return INF;
        if (memo[i][k] != null) return memo[i][k];
        int ans = INF, maxNum = nums[i], totalSum = 0;
        for (int j = i; j < n; ++j) {
            maxNum = Math.max(maxNum, nums[j]);
            totalSum += nums[j];
            int wasted = maxNum * (j - i + 1) - totalSum;
            ans = Math.min(ans, dp(nums, j + 1, k - 1) + wasted);
        }
        return memo[i][k] = ans;
    }
}

C++ Program

class Solution {
public:
    int n, INF = 200 * 1e6;
    int memo[200][200] = {};
    int minSpaceWastedKResizing(vector<int> &nums, int k) {
        memset(memo, -1, sizeof(memo));
        n = nums.size();
        return dp(nums, 0, k);
    }
    int dp(vector<int> &nums, int i, int k) {
        if (i == n) return 0;
        if (k == -1) return INF;
        if (memo[i][k] != -1) return memo[i][k];
        int ans = INF, maxNum = nums[i], totalSum = 0;
        for (int j = i; j < n; ++j) {
            maxNum = max(maxNum, nums[j]);
            totalSum += nums[j];
            int wasted = maxNum * (j - i + 1) - totalSum;
            ans = min(ans, dp(nums, j + 1, k - 1) + wasted);
        }
        return memo[i][k] = ans;
    }
};

Python Program

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n, INF = len(nums), 200 * 1e6

        @lru_cache(None)
        def dp(i, k):
            if i == n: return 0
            if k == -1: return INF
            ans = INF
            maxNum = nums[i]
            totalSum = 0
            for j in range(i, n):
                maxNum = max(maxNum, nums[j])
                totalSum += nums[j]
                wasted = maxNum * (j - i + 1) - totalSum
                ans = min(ans, dp(j + 1, k - 1) + wasted)
            return ans

        return dp(0, k)

Complexity Analysis for Subarray Product Less Than K LeetCode Solution

Time Complexity

O(N^2*K), where N <= 200 is the number of elements in the array nums, K < N is the maximum number of resizing options we can use. There are total N*K dp states, they are dp[0][0], dp[0][1].., dp[N][K]. Each state needs a loop O(N) to compute the result. So total time complexity is O(N^2*K).

Space Complexity

The space complexity of the above code is O(N*K).

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

 

Translate »