# Minimum Time to Make Array Sum At Most x
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-make-array-sum-at-most-x)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-make-array-sum-at-most-x
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Jane Street](https://scaleengineer.com/companies/jane-street)
---
## 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 _the **minimum** time in which you can make the sum of all elements of_ `nums1` _to be **less than or equal** to_ `x`, _or_ `-1` _if this is not possible._

**Example 1:**

**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:**

**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 <= 103`
* `1 <= nums1[i] <= 103`
* `0 <= nums2[i] <= 103`
* `nums1.length == nums2.length`
* `0 <= x <= 106`

# Approaches
## Brute Force with Memoization
This approach directly models the problem by exploring all possible sequences of operations. For each possible time `t` from 1 to `n`, it considers every way to perform `t` operations. An operation is defined by which element to reset and at what second. There are `n * (n-1) * ... * (n-t+1)` ways to choose `t` distinct elements and assign them to seconds `1, 2, ..., t`. For each combination, we calculate the final sum at time `t` and check if it's at most `x`. The first `t` for which this condition is met is the answer. This exhaustive search is implemented using recursion with memoization.
**Time:** O(n^2 * 2^n). The state for memoization is `(s, mask)`, leading to `n * 2^n` states. Each state computation involves a loop of size `n`. This is repeated for each time `t` from 0 to `n`, but the memoization table can be reused. The dominant part is filling the table. · **Space:** O(n * 2^n) for the memoization table and recursion stack depth.
**Pros:** It is a direct, albeit naive, way to solve the problem by checking all possibilities.; Guaranteed to find the optimal solution if it runs to completion.
**Cons:** The time complexity is extremely high, making it infeasible for the given constraints.; The space complexity for memoization is also very large.
### Explanation
The core of this approach is to check for each possible time `t` (from 0 to `n`) if a solution exists. For a given `t`, the sum of `nums1` without any operations would be `sum(nums1) + t * sum(nums2)`. An operation on index `i` at second `s` provides a reduction of `nums1[i] + s * nums2[i]` from the final sum at time `t`.

To find the minimum possible sum at time `t`, we need to maximize this total reduction. This becomes a search problem: find a set of `t` distinct indices `{p_1, ..., p_t}` to be operated on at times `{1, ..., t}` respectively, such that `sum_{s=1 to t} (nums1[p_s] + s * nums2[p_s])` is maximized.

A recursive function, `findMaxReduction(second, used_mask)`, can solve this. `second` tracks the current time (e.g., from `t` down to 1), and `used_mask` is a bitmask to keep track of which indices have already been chosen for an operation. To optimize this recursion, we use a memoization table `memo[second][used_mask]` to store the results of subproblems, which significantly reduces the number of computations but still remains too slow for large `n`.

```java
// Conceptual code for the recursive part with memoization
class Solution {
    long[][] memo;
    int n;
    List<Integer> nums1, nums2;

    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        this.n = nums1.size();
        this.nums1 = nums1;
        this.nums2 = nums2;
        long sum1 = 0, sum2 = 0;
        for(int val : nums1) sum1 += val;
        for(int val : nums2) sum2 += val;

        this.memo = new long[n + 1][1 << n];
        for(long[] row : memo) Arrays.fill(row, -1);

        for (int t = 0; t <= n; t++) {
            long maxReduction = findMaxReduction(t, 0);
            if (sum1 + sum2 * t - maxReduction <= x) {
                return t;
            }
        }
        return -1;
    }

    private long findMaxReduction(int s, int mask) {
        if (s == 0) {
            return 0;
        }
        if (memo[s][mask] != -1) {
            return memo[s][mask];
        }

        long maxRed = 0; // If we perform fewer than s operations
        // This part is tricky. A better way is to find max reduction for exactly s ops.
        // Let's assume the function finds max reduction with s ops on s available items.
        // The logic below is for picking s items from n and assigning to times 1..s
        // A full brute force would be more complex.
        // The DP approach is the way to go.
        // For the sake of illustrating the complexity, let's assume a simplified (but still exponential) check.
        // A proper recursive solution would be more involved.
        // The main point is its exponential nature.
        return 0; // Placeholder, as a full implementation is complex and inefficient.
    }
}
```
### Algorithm
1. Iterate through each possible time `t` from 0 to `n`, where `n` is the length of the arrays.
2. For each `t`, determine the maximum possible reduction in the total sum by performing `t` operations.
3. This requires exploring all ways to choose `t` distinct indices and assigning them to the `t` seconds (from 1 to `t`).
4. A recursive backtracking function can be used for this exploration. The function would try assigning each available index to the current second and recurse for the next second.
   - `solve(second, used_mask)`: 
   - Base case: If `second == 0`, return 0.
   - Iterate through all indices `i` from 0 to `n-1`.
   - If index `i` has not been used (check `used_mask`), calculate the potential reduction: `(nums1[i] + second * nums2[i]) + solve(second - 1, used_mask | (1 << i))`.
   - Keep track of the maximum reduction found.
5. To avoid recomputing results for the same state, memoization (a top-down dynamic programming technique) can be applied. The state is defined by `(second, used_mask)`.
6. After finding the maximum reduction `maxReduction` for time `t`, calculate the final sum: `finalSum = (sum(nums1) + t * sum(nums2)) - maxReduction`.
7. If `finalSum <= x`, then `t` is a possible time. Since we are iterating `t` from 0 upwards, the first such `t` is the minimum time. Return `t`.
8. If the loop finishes without finding a valid `t`, it's impossible. Return -1.

## Dynamic Programming
A more efficient approach uses dynamic programming. The key observation is that to maximize the reduction from operations, we should use larger `nums2[i]` values with later operation times (which are larger numbers). This suggests sorting the elements by their `nums2` values.

After sorting, we can use DP to solve a problem analogous to the 0/1 knapsack problem. We want to select a subset of items to operate on to maximize the reduction. We build a DP table where `dp[j]` stores the maximum reduction achievable with `j` operations. By iterating through the sorted items and updating the DP table, we can efficiently compute the optimal reduction for any number of operations.

Finally, we can iterate through each possible time `t` from 0 to `n`, and using our pre-calculated DP table, check in O(1) time if the condition `sum <= x` can be met at time `t`. The first `t` that satisfies the condition is the minimum time.
**Time:** O(n^2). Sorting the pairs takes `O(n log n)`. The DP calculation involves two nested loops, resulting in `O(n^2)` complexity. The final check takes `O(n)`. The dominant factor is the DP computation. · **Space:** O(n), for the DP array `dp` and the `pairs` array used for sorting.
**Pros:** Highly efficient with a polynomial time complexity, suitable for the given constraints.; Systematically finds the optimal solution without exhaustive search.
**Cons:** The derivation of the DP state and transition is not immediately obvious.
### Explanation
This approach is centered around a dynamic programming formulation to calculate the maximum reduction for a given number of operations. Let's say we perform `k` operations. This will take `k` seconds, so we check at time `t=k`. The total sum without operations is `sum(nums1) + k * sum(nums2)`. The reduction from operating on index `p_s` at time `s` (for `s=1..k`) is `nums1[p_s] + s * nums2[p_s]`. To maximize the total reduction `sum_{s=1 to k} (nums1[p_s] + s * nums2[p_s])`, we should pair indices with larger `nums2` values with larger `s`.

This leads to the DP strategy:
1. Sort items based on `nums2[i]`.
2. Let `dp[j]` be the max reduction using `j` operations. We iterate through the sorted items `(a_i, b_i)` and update `dp[j]`.
3. The transition `dp[j] = max(dp[j], dp[j-1] + a_i + j * b_i)` is used. When considering item `i` for one of `j` operations, it's chosen along with `j-1` items from the first `i-1` (which have smaller `b` values). Since `b_i` is the largest, it's paired with time `j`. The term `dp[j-1]` represents the max reduction from the other `j-1` items at times `1..j-1`.
4. After computing `dp[t]` for all `t` from 0 to `n`, we can check each `t` as a potential answer.

```java
import java.util.*;

class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size();
        int[][] pairs = new int[n][2];
        long sum1 = 0;
        long sum2 = 0;
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums2.get(i);
            pairs[i][1] = nums1.get(i);
            sum1 += nums1.get(i);
            sum2 += nums2.get(i);
        }

        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));

        long[] dp = new long[n + 1];

        for (int i = 0; i < n; i++) {
            int b = pairs[i][0]; // nums2 value
            int a = pairs[i][1]; // nums1 value
            for (int j = n; j >= 1; j--) {
                dp[j] = Math.max(dp[j], dp[j - 1] + a + (long)j * b);
            }
        }

        for (int t = 0; t <= n; t++) {
            long totalSumAtT = sum1 + t * sum2;
            if (totalSumAtT - dp[t] <= x) {
                return t;
            }
        }

        return -1;
    }
}
```
### Algorithm
1. Combine `nums1[i]` and `nums2[i]` into pairs `(nums2[i], nums1[i])`.
2. Sort these pairs in ascending order based on the `nums2` values. This is crucial because to maximize reduction, elements with larger `nums2` values should be paired with later operation times.
3. Initialize a 1D DP array, `dp`, of size `n + 1`. `dp[j]` will store the maximum possible reduction achievable by performing exactly `j` operations at times `1, 2, ..., j`.
4. Iterate through each sorted pair `(b, a)` (where `b` is a `nums2` value and `a` is a `nums1` value).
   - For each pair, update the `dp` array. Iterate `j` from `n` down to 1.
   - The transition is: `dp[j] = max(dp[j], dp[j-1] + a + j * b)`. This considers either not using the current item for the `j`-th operation, or using it. If we use it, it must be paired with time `j` because its `b` value is the largest among the `j` items selected so far.
5. After filling the `dp` table, `dp[t]` contains the maximum reduction for `t` operations performed at time `t`.
6. Calculate the initial total sums of `nums1` and `nums2`, let's call them `sum1` and `sum2`.
7. Iterate `t` from 0 to `n`.
   - Calculate the potential total sum at time `t`: `totalSum = sum1 + t * sum2`.
   - Check if `totalSum - dp[t] <= x`. If it is, `t` is a valid time. Return `t` as it's the minimum possible.
8. If the loop completes, no solution is possible. Return -1.

# Solutions
### Java

```java
class Solution {
public
  int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
    int n = nums1.size();
    int[][] f = new int[n + 1][n + 1];
    int[][] nums = new int[n][0];
    for (int i = 0; i < n; ++i) {
      nums[i] = new int[]{nums1.get(i), nums2.get(i)};
    }
    Arrays.sort(nums, Comparator.comparingInt(a->a[1]));
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j];
        if (j > 0) {
          int a = nums[i - 1][0], b = nums[i - 1][1];
          f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + a + b * j);
        }
      }
    }
    int s1 = 0, s2 = 0;
    for (int v : nums1) {
      s1 += v;
    }
    for (int v : nums2) {
      s2 += v;
    }
    for (int j = 0; j <= n; ++j) {
      if (s1 + s2 * j - f[n][j] <= x) {
        return j;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTime(vector<int> &nums1, vector<int> &nums2, int x) {
    int n = nums1.size();
    vector<pair<int, int>> nums;
    for (int i = 0; i < n; ++i) {
      nums.emplace_back(nums2[i], nums1[i]);
    }
    sort(nums.begin(), nums.end());
    int f[n + 1][n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j];
        if (j) {
          auto [b, a] = nums[i - 1];
          f[i][j] = max(f[i][j], f[i - 1][j - 1] + a + b * j);
        }
      }
    }
    int s1 = accumulate(nums1.begin(), nums1.end(), 0);
    int s2 = accumulate(nums2.begin(), nums2.end(), 0);
    for (int j = 0; j <= n; ++j) {
      if (s1 + s2 * j - f[n][j] <= x) {
        return j;
      }
    }
    return -1;
  }
};

```

### Python

```python
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

```