#2809

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Time to Make Array Sum At Most x

Calculate the minimum seconds to reduce the array sum to at most x using optimal single-time reductions per index efficiently.

array dynamic programming sorting

Problem Statement

You are given two integer arrays nums1 and nums2 of the same length and an integer x. Every second, each nums1[i] is incremented by nums2[i], and you may choose to set any nums1[i] to zero exactly once per index to reduce the sum.

Return the minimum number of seconds required to make the sum of all elements in nums1 less than or equal to x. If it is impossible to achieve, return -1.

Examples

Example 1

Input: nums1 = [1,2,3], nums2 = [1,2,3], x = 4

Output: 3

For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6]. For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9]. For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0]. Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.

Example 2

Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4

Output: -1

It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.

Constraints

1 <= nums1.length <= 103
1 <= nums1[i] <= 103
0 <= nums2[i] <= 103
nums1.length == nums2.length
0 <= x <= 106

Solution Approach

Use Dynamic Programming for State Transitions

Define dp[i][t] as the minimum achievable sum after processing the first i indices with t seconds used. Update states by considering whether to reset nums1[i] to zero or let it accumulate via nums2[i]. This directly implements the state transition dynamic programming pattern.

Sort and Prioritize Reductions

Sort indices by nums2 increments to prioritize resetting elements that grow fastest. This reduces the array sum more efficiently, fitting with the state transition pattern where choices impact future sums.

Check Feasibility and Return Result

After computing DP states for all indices, find the minimum t where the sum is at most x. If no such t exists, return -1. This handles the problem's failure mode where sum constraints cannot be met.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on DP table size and how the state transitions are implemented. Sorting adds O(n log n) overhead, while DP can approach O(n * maxTime) depending on the maximum sum and resets allowed.

What Interviewers Usually Probe

Consider the optimality of resetting each index only once.
Think about how state transitions affect future sums for the DP table.
Be ready to justify why certain orders of resets minimize total time.

Common Pitfalls or Variants

Common pitfalls

Resetting an index multiple times, violating the one-time rule.
Ignoring the growth from nums2 increments in future seconds.
Failing to return -1 when no valid sequence achieves sum <= x.

Follow-up variants

Change the problem to allow multiple resets per index, requiring a more complex DP state.
Introduce negative nums2 increments, affecting which indices to reset.
Ask for maximum sum reduction instead of minimum time, adjusting optimization criteria.

FAQ

What is the main dynamic programming pattern in Minimum Time to Make Array Sum At Most x?

The problem uses state transition DP where each index decision affects future sums, and each nums1[i] can be reset to zero at most once.

Can nums1[i] be reset multiple times?

No, optimal solutions require at most one reset per index, following the state transition strategy.

What should be returned if the sum cannot be reduced to x?

Return -1, reflecting the problem's failure mode when constraints cannot be satisfied.

Does sorting help in this problem?

Yes, sorting indices by their nums2 increments helps prioritize resets that reduce the sum fastest, improving DP efficiency.

What is the expected time complexity approach?

Time depends on the DP state size and sorting, roughly O(n log n + n * maxTime), where n is the array length and maxTime is related to sum growth.

terminal

Solution

Solution 1: Sorting + Dynamic Programming

We notice that if we operate on the same number multiple times, only the last operation is meaningful, and the rest of the operations on that number will only increase the other numbers. Therefore, we operate on each number at most once, that is to say, the number of operations is within $[0,..n]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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 -1

Continue Practicing

#2830 maximize the profit as the salesman #2713 maximum strictly increasing cells in a matrix #2708 maximum strength of a group