2809. Minimum Time to Make Array Sum At Most x


Problem Description

Given two arrays nums1 and nums2 that are both 0-indexed and of the same length, the task is to find the minimum time it takes to reduce the sum of all elements in nums1 to a value less than or equal to a given integer x. Every second, each element nums1[i] is increased by its corresponding element nums2[i]. Once this increment has happened, you have the choice to reset any nums1[i] to 0 exactly once. If you cannot make the sum of nums1 less than or equal to x, return -1.

Intuition

To solve this problem, the intuition is to determine for each second what the best outcome would be if we reset one of the nums1 elements to 0 at that exact moment. The outcome to maximize is the sum of all nums1 elements plus all the increments that have been made up to that second.

To approach this solution:

  1. The nums1 and nums2 items are first zipped together and sorted by the nums2 values since they indicate how much each corresponding nums1 value grows per second. We're interested in maximizing the rate of growth per second, which is why sorting based on nums2 is sensible.

  2. A dynamic programming list f is prepared which is initialized to 0 and has a length of n + 1, where n is the length of the arrays. This list will help keep track of the best outcomes at each second for the corresponding prefix of the array.

  3. The main idea applied here is, for a current moment denoted by j, we want to determine whether it would be beneficial to perform the reset operation now or to have done it one second earlier. This is computed by three values:

    • The value if we choose not to reset at this moment (f[j]).
    • The new sum we would get if we reset f[j-1] one second earlier and added the current a + (b * j), which denotes current incremented value plus its growth over j seconds.
  4. This leads to the updating of f[j] to the maximum of these options.

  5. Finally, loop through each possible second and calculate if the total growth plus the sum of elements is less than or equal to x after resetting the best element at that second. If it is, return the current second as the minimum time. If no such second is found, return -1.

This solution tries to balance the gain from allowing the nums1 values to grow and the benefit of resetting a value to zero at the right time to minimize the sum to meet the condition with respect to x.

Solution Approach

The solution uses a combination of sorting, dynamic programming, and greedy strategy.

  1. Sorting: First off, the zip function combines the elements from nums1 and nums2 into pairs, and then sorts them by the second value (nums2[i]), which represents the growth rate or increment per second. This is done using the sorted function with the key being the second element of the pair (z[1]).

    By sorting, we prioritize the handling of the elements in nums1 which are paired with the largest increment factors first, allowing us to benefit from their rapid growth when considering when to reset them to zero.

  2. Dynamic Programming (DP): A dynamic programming array f is initialized as a list of zeros, with a size of n+1. Here, n is the length of nums1. The dynamic programming array f[j] represents the maximum sum that can be achieved by applying the reset operation j times, up until the current point of our iteration over the sorted pairs.

  3. Greedy Iteration: After sorting, a loop is started which iterates over each paired element from the sorted list. For each such element, an inner loop runs in reverse over the range from n down to 1. The reverse iteration allows us to consider the scenarios of having consumed one less reset opportunity at each stage.

    In the inner loop, a represents the current value of nums1[i], and b is the increment value of nums2[i]. The inner loop updates the max sum for j resets by comparing the current f[j] and the sum of f[j-1] (the max sum if the reset was done one second earlier) plus the value of the current index (after having been incremented for j seconds).

    The condition f[j] = max(f[j], f[j - 1] + a + b * j) ensures that for each possible number of resets j, we track the best sum possible at that moment.

  4. Calculate Required Seconds: After the dynamic programming step, two sums are calculated: the sum of elements in nums1 (s1) and the sum of chosen increments in nums2 (s2). The final check loops through j from 0 to n, checking if the condition (s1 + s2 * j - f[j]) <= x is met. This is checking if the total growth (assuming maximum growth for each second) minus the maximum sum when j resets have been used is less than or equal to x. If this is the case, it indicates that the sum of nums1 can be maintained below or equal to x in j seconds after resetting the most beneficial elements, and j is returned as the solution.

    If the loop completes without finding a satisfactory j, then the function returns -1, indicating that it's not possible to reduce the sum of nums1 below or equal to x.

The solution capitalizes on the greedy strategy of sorting by growth rate to consider the most impactful elements first and uses dynamic programming to keep track of the best reset decisions as the array elements grow.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Let nums1 = [4, 3, 8], nums2 = [2, 1, 3], and x = 13.

Following the solution approach:

  1. The two lists are zipped and sorted by growth values (nums2). The resulting list is [(3, 1), (4, 2), (8, 3)].

  2. An array f is initialized with zeros, of length 4 since n = 3. f = [0, 0, 0, 0].

  3. Iterating over each element with initialized sums s1 = 15 (sum of nums1) and s2 = 6 (sum of nums2):

    First iteration (element (3, 1)):

    • Inner loop for j = 1 to n, update f[j]:
      • j = 1: f[1] is updated to max(f[1], f[0] + 3 + 1 * 1) -> f[1] = 4.
      • j = 2: f[2] is updated to max(f[2], f[1] + 3 + 1 * 2) -> f[2] = 7.
      • j = 3: f[3] is updated to max(f[3], f[2] + 3 + 1 * 3) -> f[3] = 10.

    Second iteration (element (4, 2)):

    • Inner loop:
      • j = 1: f[1] is updated to max(f[1], f[0] + 4 + 2 * 1) -> f[1] remains 4.
      • j = 2: f[2] is updated to max(f[2], f[1] + 4 + 2 * 2) -> f[2] remains 7.
      • j = 3: f[3] is updated to max(f[3], f[2] + 4 + 2 * 3) -> f[3] becomes 13.

    Third iteration (element (8, 3)):

    • Inner loop:
      • j = 1: f[1] is updated to max(f[1], f[0] + 8 + 3 * 1) -> f[1] becomes 11.
      • j = 2: f[2] is updated to max(f[2], f[1] + 8 + 3 * 2) -> f[2] becomes 19.
      • j = 3: f[3] is updated to max(f[3], f[2] + 8 + 3 * 3) -> f[3] becomes 28.

    Now we have f = [0, 11, 19, 28].

  4. Finally, loop to find the minimum seconds required:

    Checking for j from 0 to n:

    • j = 0: (s1 + s2 * 0 - f[0]) -> (15 + 6 * 0 - 0) = 15 which is greater than x.
    • j = 1: (s1 + s2 * 1 - f[1]) -> (15 + 6 * 1 - 11) = 10 which is less than x. So the minimum time needed is 1 second.

In this case, we find that j = 1 is the point where, after resetting the most significant element to zero, the sum of nums1 will be less than or equal to x. Hence, the answer is 1 second.

Python Solution

1from typing import List
2
3class Solution:
4    def minimumTime(self, nums1: List[int], nums2: List[int], limit: int) -> int:
5        # Determine the number of pairs in nums1 and nums2
6        num_pairs = len(nums1)
7      
8        # Initialize an array to store the maximum value possible with a given number of pairs used
9        max_values = [0] * (num_pairs + 1)
10      
11        # Sort the pairs based on the second element of each pair
12        sorted_pairs = sorted(zip(nums1, nums2), key=lambda pair: pair[1])
13      
14        # Calculate the maximum value for using each possible number of pairs
15        for elem1, elem2 in sorted_pairs:
16            for j in range(num_pairs, 0, -1):
17                max_values[j] = max(max_values[j], max_values[j - 1] + elem1 + elem2 * j)
18      
19        # Calculate the sum of elements in nums1 and nums2
20        sum_nums1 = sum(nums1)
21        sum_nums2 = sum(nums2)
22      
23        # Determine the minimum number of  operations needed
24        # to bring the sum of warped nums1 and nums2 below 'limit'
25        for j in range(num_pairs + 1):
26            if sum_nums1 + sum_nums2 * j - max_values[j] <= limit:
27                return j
28      
29        # If no solution is found, return -1
30        return -1
31
32# Example usage:
33# solution = Solution()
34# result = solution.minimumTime(nums1=[1,2,3], nums2=[3,2,1], limit=50)
35# print(result) # Output will depend on the input values
36

Java Solution

1import java.util.*;
2
3class Solution {
4    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
5        int n = nums1.size(); // The size of the given lists
6        int[] dp = new int[n + 1]; // Dynamic programming array to store maximum scores
7      
8        // Create an array to store the pairs from nums1 and nums2
9        int[][] pairs = new int[n][2];
10        for (int i = 0; i < n; ++i) {
11            pairs[i] = new int[]{nums1.get(i), nums2.get(i)};
12        }
13
14        // Sort the pairs by the second element in ascending order
15        Arrays.sort(pairs, Comparator.comparingInt(pair -> pair[1]));
16
17        // Calculate the maximum score for each subsequence of pairs
18        for (int[] pair : pairs) {
19            int first = pair[0], second = pair[1];
20            for (int j = n; j > 0; --j) {
21                dp[j] = Math.max(dp[j], dp[j - 1] + first + second * j);
22            }
23        }
24      
25        int sumNums1 = 0, sumNums2 = 0; // Sum of elements from nums1 and nums2
26        for (int v : nums1) {
27            sumNums1 += v;
28        }
29        for (int v : nums2) {
30            sumNums2 += v;
31        }
32      
33        // Check for the minimal number of pairs needed to be chosen
34        // to satisfy the condition sumNums1 + sumNums2 * j - dp[j] <= x
35        for (int j = 0; j <= n; ++j) {
36            if (sumNums1 + sumNums2 * j - dp[j] <= x) {
37                return j; // Return the minimal number of pairs
38            }
39        }
40        // If no such number of pairs is found, return -1
41        return -1;
42    }
43}
44

C++ Solution

1#include <vector>      // Needed for using std::vector
2#include <algorithm>   // Needed for std::sort and std::accumulate
3#include <cstring>     // Needed for std::memset
4
5class Solution {
6public:
7    int minimumTime(std::vector<int>& taskTimesA, std::vector<int>& taskTimesB, int maxTime) {
8        int tasksCount = taskTimesA.size(); // Number of tasks
9        // Pair each task's time from B with the corresponding time from A
10        std::vector<std::pair<int, int>> taskPairs;
11        for (int i = 0; i < tasksCount; ++i) {
12            taskPairs.emplace_back(taskTimesB[i], taskTimesA[i]);
13        }
14      
15        // Sort the pair array based on times from B task times (ascending)
16        std::sort(taskPairs.begin(), taskPairs.end());
17      
18        // Initialize the dynamic programming array; 
19        // f[i] will hold the maximum time saved after completing i tasks
20        std::vector<int> dp(tasksCount + 1, 0);
21      
22        // Calculate the maximum time saved for each number of tasks
23        for (auto& [timeB, timeA] : taskPairs) {
24            for (int j = tasksCount; j > 0; --j) {
25                dp[j] = std::max(dp[j], dp[j - 1] + timeA + timeB * j);
26            }
27        }
28      
29        // Calculate the sum of the times for both A and B tasks
30        int totalTimeA = accumulate(taskTimesA.begin(), taskTimesA.end(), 0);
31        int totalTimeB = accumulate(taskTimesB.begin(), taskTimesB.end(), 0);
32      
33        // Find the minimum number of tasks needed such that the time limit is not exceeded
34        for (int j = 0; j <= tasksCount; ++j) {
35            if (totalTimeA + totalTimeB * j - dp[j] <= maxTime) {
36                return j; // Minimum number of tasks
37            }
38        }
39      
40        // If no solution is found return -1
41        return -1;
42    }
43};
44

Typescript Solution

1function minimumTime(nums1: number[], nums2: number[], x: number): number {
2    const numPairs = nums1.length;
3    const maxValues: number[] = new Array(numPairs + 1).fill(0);
4    const sortedPairs: number[][] = [];
5
6    // Combine corresponding elements of nums1 and nums2 into pairs
7    for (let i = 0; i < numPairs; i++) {
8        sortedPairs.push([nums1[i], nums2[i]]);
9    }
10
11    // Sort pairs based on the second element of each pair (nums2 value)
12    sortedPairs.sort((pairA, pairB) => pairA[1] - pairB[1]);
13
14    // Populate the maxValues array with maximum scores computed
15    for (const [value1, value2] of sortedPairs) {
16        for (let j = numPairs; j > 0; j--) {
17            maxValues[j] = Math.max(
18                maxValues[j],
19                maxValues[j - 1] + value1 + value2 * j
20            );
21        }
22    }
23
24    // Calculate total sum of both arrays
25    const totalSumNums1 = nums1.reduce((total, num) => total + num, 0);
26    const totalSumNums2 = nums2.reduce((total, num) => total + num, 0);
27
28    // Determine the minimum index 'j' where the condition is satisfied
29    for (let j = 0; j <= numPairs; j++) {
30        const conditionValue = totalSumNums1 + totalSumNums2 * j - maxValues[j];
31        if (conditionValue <= x) {
32            return j;
33        }
34    }
35
36    // Return -1 if no such index was found
37    return -1;
38}
39

Time and Space Complexity

Time Complexity

Let's analyze the time complexity of the given code:

  • There is a loop which sorts the zip of nums1 and nums2 by the second element of the tuple. The sort function in Python uses Timsort, which has a time complexity of O(n log n) where n is the number of elements being sorted.

  • After sorting, there is a nested loop:

    • The outer loop iterates over the sorted list, which is O(n).

    • The inner loop iterates backwards from n to 1, which is also O(n) in the worst case.

    • Inside the inner loop, the code updates the list f with calculated values, which is an O(1) operation.

Combining all the above steps, the overall time complexity of the nested loops is O(n^2).

  • The final step of the function iterates through the range n + 1, which is O(n).

Thus, the total time complexity is dominated by the sorting and the nested loops, giving us O(n log n) + O(n^2), which simplifies to O(n^2) because n^2 grows faster than n log n.

Space Complexity

For space complexity:

  • A new list f of size n + 1 is created, which gives us O(n).

  • Sorting the zipped lists creates an additional space which also leads to O(n), despite the fact that Python's sort is typically in-place, because the zip object is being converted to a list and sorted separately.

  • Other variables used are of constant space and do not scale with n.

Consequently, the total space complexity is O(n), because we only account for the largest term when calculating space complexity.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫