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:
-
The
nums1
andnums2
items are first zipped together and sorted by thenums2
values since they indicate how much each correspondingnums1
value grows per second. We're interested in maximizing the rate of growth per second, which is why sorting based onnums2
is sensible. -
A dynamic programming list
f
is prepared which is initialized to 0 and has a length ofn + 1
, wheren
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. -
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 currenta + (b * j)
, which denotes current incremented value plus its growth overj
seconds.
- The value if we choose not to reset at this moment (
-
This leads to the updating of
f[j]
to the maximum of these options. -
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
.
Learn more about Dynamic Programming and Sorting patterns.
Solution Approach
The solution uses a combination of sorting, dynamic programming, and greedy strategy.
-
Sorting: First off, the
zip
function combines the elements fromnums1
andnums2
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 thesorted
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. -
Dynamic Programming (DP): A dynamic programming array
f
is initialized as a list of zeros, with a size ofn+1
. Here,n
is the length ofnums1
. The dynamic programming arrayf[j]
represents the maximum sum that can be achieved by applying the reset operationj
times, up until the current point of our iteration over the sorted pairs. -
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 to1
. 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 ofnums1[i]
, andb
is the increment value ofnums2[i]
. The inner loop updates the max sum forj
resets by comparing the currentf[j]
and the sum off[j-1]
(the max sum if the reset was done one second earlier) plus the value of the current index (after having been incremented forj
seconds).The condition
f[j] = max(f[j], f[j - 1] + a + b * j)
ensures that for each possible number of resetsj
, we track the best sum possible at that moment. -
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 innums2
(s2
). The final check loops throughj
from0
ton
, 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 whenj
resets have been used is less than or equal tox
. If this is the case, it indicates that the sum ofnums1
can be maintained below or equal tox
inj
seconds after resetting the most beneficial elements, andj
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 ofnums1
below or equal tox
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
The two lists are
zip
ped and sorted by growth values (nums2
). The resulting list is[(3, 1), (4, 2), (8, 3)]
. -
An array
f
is initialized with zeros, of length 4 sincen = 3
.f = [0, 0, 0, 0]
. -
Iterating over each element with initialized sums
s1 = 15
(sum ofnums1
) ands2 = 6
(sum ofnums2
):First iteration (element (3, 1)):
- Inner loop for
j = 1
ton
, updatef[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]
remains4
.j = 2
:f[2]
is updated to max(f[2]
,f[1] + 4 + 2 * 2
) ->f[2]
remains7
.j = 3
:f[3]
is updated to max(f[3]
,f[2] + 4 + 2 * 3
) ->f[3]
becomes13
.
Third iteration (element (8, 3)):
- Inner loop:
j = 1
:f[1]
is updated to max(f[1]
,f[0] + 8 + 3 * 1
) ->f[1]
becomes11
.j = 2
:f[2]
is updated to max(f[2]
,f[1] + 8 + 3 * 2
) ->f[2]
becomes19
.j = 3
:f[3]
is updated to max(f[3]
,f[2] + 8 + 3 * 3
) ->f[3]
becomes28
.
Now we have
f = [0, 11, 19, 28]
. - Inner loop for
-
Finally, loop to find the minimum seconds required:
Checking for
j
from0
ton
:j = 0
:(s1 + s2 * 0 - f[0])
->(15 + 6 * 0 - 0)
= 15 which is greater thanx
.j = 1
:(s1 + s2 * 1 - f[1])
->(15 + 6 * 1 - 11)
= 10 which is less thanx
. 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.
Solution Implementation
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
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
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
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
ofnums1
andnums2
by the second element of the tuple. The sort function in Python uses Timsort, which has a time complexity ofO(n log n)
wheren
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
to1
, which is alsoO(n)
in the worst case. -
Inside the inner loop, the code updates the list
f
with calculated values, which is anO(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 isO(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 sizen + 1
is created, which gives usO(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 thezip
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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we