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]. After this is done, you can do the following operation:

  • Choose an index 0 <= i < nums1.length and make nums1[i] = 0.

You are also given an integer x.

Return _theminimum time in which you can make the sum of all elements of _nums1 _to beless than or equal to _x, or-1 if this is not possible.

Examples

Example 1

1
2
3
4
5
6
7

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]. 
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

1
2
3

Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4
Output: -1
Explanation: 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 <= 10^3
  • 1 <= nums1[i] <= 10^3
  • 0 <= nums2[i] <= 10^3
  • nums1.length == nums2.length
  • 0 <= x <= 10^6

Solution

Method 1 – Dynamic Programming with Sorting

Intuition

At each second, we can reset one element to zero after incrementing all by nums2. To minimize the sum, we should reset the largest contributors (nums1[i] + t * nums2[i]) as early as possible. We can use dynamic programming to track the minimum sum for each number of resets.

Approach

  1. Let n = length of nums1.
  2. For each i, calculate the total contribution if we reset it at time t.
  3. Sort indices by nums2[i] descending, as resetting higher increment contributors earlier is better.
  4. Use DP: dp[k] = minimum sum after k resets.
  5. For each k from 0 to n, try all combinations and update dp.
  6. Return the smallest k such that dp[k] <= x, or -1 if not possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
        int n = nums1.size();
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; ++i) arr[i] = {nums2[i], nums1[i]};
        sort(arr.rbegin(), arr.rend());
        vector<long long> dp(n+1, 0);
        for (int i = 0; i < n; ++i) dp[0] += arr[i].second;
        for (int i = 0; i < n; ++i) {
            for (int k = i+1; k >= 1; --k) {
                dp[k] = max(dp[k], dp[k-1] + arr[i].first * k);
            }
        }
        for (int k = 0; k <= n; ++k) {
            if (dp[k] <= x) return k;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func minimumTime(nums1, nums2 []int, x int) int {
    n := len(nums1)
    arr := make([][2]int, n)
    for i := 0; i < n; i++ {
        arr[i] = [2]int{nums2[i], nums1[i]}
    }
    sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
    dp := make([]int, n+1)
    for i := 0; i < n; i++ {
        dp[0] += arr[i][1]
    }
    for i := 0; i < n; i++ {
        for k := i+1; k >= 1; k-- {
            if dp[k] < dp[k-1]+arr[i][0]*k {
                dp[k] = dp[k-1]+arr[i][0]*k
            }
        }
    }
    for k := 0; k <= n; k++ {
        if dp[k] <= x {
            return k
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minimumTime(int[] nums1, int[] nums2, int x) {
        int n = nums1.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) arr[i] = new int[]{nums2[i], nums1[i]};
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        long[] dp = new long[n+1];
        for (int i = 0; i < n; i++) dp[0] += arr[i][1];
        for (int i = 0; i < n; i++) {
            for (int k = i+1; k >= 1; k--) {
                dp[k] = Math.max(dp[k], dp[k-1] + (long)arr[i][0] * k);
            }
        }
        for (int k = 0; k <= n; k++) {
            if (dp[k] <= x) return k;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minimumTime(nums1: IntArray, nums2: IntArray, x: Int): Int {
        val n = nums1.size
        val arr = Array(n) { i -> Pair(nums2[i], nums1[i]) }
        arr.sortByDescending { it.first }
        val dp = LongArray(n+1)
        for (i in 0 until n) dp[0] += arr[i].second
        for (i in 0 until n) {
            for (k in i+1 downTo 1) {
                dp[k] = maxOf(dp[k], dp[k-1] + arr[i].first * k)
            }
        }
        for (k in 0..n) {
            if (dp[k] <= x) return k
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minimumTime(self, nums1: list[int], nums2: list[int], x: int) -> int:
        n: int = len(nums1)
        arr = sorted(zip(nums2, nums1), reverse=True)
        dp = [0] * (n+1)
        for i in range(n):
            dp[0] += arr[i][1]
        for i in range(n):
            for k in range(i+1, 0, -1):
                dp[k] = max(dp[k], dp[k-1] + arr[i][0] * k)
        for k in range(n+1):
            if dp[k] <= x:
                return k
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn minimum_time(nums1: Vec<i32>, nums2: Vec<i32>, x: i32) -> i32 {
        let n = nums1.len();
        let mut arr: Vec<(i32, i32)> = nums2.iter().zip(nums1.iter()).map(|(&a, &b)| (a, b)).collect();
        arr.sort_by(|a, b| b.0.cmp(&a.0));
        let mut dp = vec![0i64; n+1];
        for i in 0..n {
            dp[0] += arr[i].1 as i64;
        }
        for i in 0..n {
            for k in (1..=i+1).rev() {
                dp[k] = dp[k].max(dp[k-1] + arr[i].0 as i64 * k as i64);
            }
        }
        for k in 0..=n {
            if dp[k] <= x as i64 {
                return k as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minimumTime(nums1: number[], nums2: number[], x: number): number {
        const n = nums1.length;
        const arr = nums2.map((v, i) => [v, nums1[i]]).sort((a, b) => b[0] - a[0]);
        const dp = Array(n+1).fill(0);
        for (let i = 0; i < n; i++) dp[0] += arr[i][1];
        for (let i = 0; i < n; i++) {
            for (let k = i+1; k >= 1; k--) {
                dp[k] = Math.max(dp[k], dp[k-1] + arr[i][0] * k);
            }
        }
        for (let k = 0; k <= n; k++) {
            if (dp[k] <= x) return k;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because of the nested loops for DP.
  • 🧺 Space complexity: O(n), for the DP array.