HardNo. 2809
Minimum Time to Make Array Sum At Most x — LeetCode 2809 Python Solution
- Pattern
- Sorting
- Topics
- Array, Dynamic Programming, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, value of nums1[i] is incremented by nums2[i].
Example
- Input
- nums1 = [1,2,3], nums2 = [1,2,3], x = 4
- Output
- 3
- Explanation
- For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6].
Python solution
class Solution:
def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
n = len(nums1)
f = [[0] * (n + 1) for _ in range(n + 1)]
for i, (a, b) in enumerate(sorted(zip(nums1, nums2), key=lambda z: z[1]), 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j]
if j > 0:
f[i][j] = max(f[i][j], f[i - 1][j - 1] + a + b * j)
s1 = sum(nums1)
s2 = sum(nums2)
for j in range(n + 1):
if s1 + s2 * j - f[n][j] <= x:
return j
return -1Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)where n is the length of the array
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2809. Minimum Time to Make Array Sum At Most x is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0368 | Largest Divisible Subset | Medium |
| 0435 | Non-overlapping Intervals | Medium |
| 0472 | Concatenated Words | Hard |
| 0646 | Maximum Length of Pair Chain | Medium |
| 0975 | Odd Even Jump | Hard |
| 1262 | Greatest Sum Divisible by Three | Medium |
Frequently asked questions
- How hard is LeetCode 2809. Minimum Time to Make Array Sum At Most x?
LeetCode 2809. Minimum Time to Make Array Sum At Most x is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2809. Minimum Time to Make Array Sum At Most x?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 2809. Minimum Time to Make Array Sum At Most x?
The Python solution on this page uses O(n2), where n is the length of the array auxiliary space.
- What topics does LeetCode 2809. Minimum Time to Make Array Sum At Most x cover?
LeetCode 2809. Minimum Time to Make Array Sum At Most x is tagged Array, Dynamic Programming and Sorting on LeetCode.