Skip to content

2809. Minimum Time to Make Array Sum At Most x 👍

Approach 1: 2D DP

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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
26
27
28
29
30
31
32
33
class Solution {
 public:
  int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
    const int n = nums1.size();
    const int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
    const int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
    // dp[j] := max reduced value if we do j ops on the nums so far
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    vector<pair<int, int>> sortedNums;

    for (int i = 0; i < n; ++i)
      sortedNums.emplace_back(nums2[i], nums1[i]);

    sort(sortedNums.begin(), sortedNums.end());

    for (int i = 1; i <= n; ++i) {
      const auto [num2, num1] = sortedNums[i - 1];
      for (int j = 1; j <= i; ++j)
        dp[i][j] = max(
            // max reduced value if we do j ops on the first i - 1 nums
            dp[i - 1][j],
            // max reduced value if we do j - 1 ops on the first i - 1 nums +
            // making i-th num of nums1 to 0 at j-th operation
            dp[i - 1][j - 1] + num2 * j + num1);
    }

    for (int op = 0; op <= n; ++op)
      if (sum1 + sum2 * op - dp[n][op] <= x)
        return op;

    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
26
27
28
29
30
31
32
33
class Solution {
  public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
    final int n = nums1.size();
    final int sum1 = nums1.stream().mapToInt(Integer::intValue).sum();
    final int sum2 = nums2.stream().mapToInt(Integer::intValue).sum();
    // dp[i][j] := max reduced value if we do j ops on the first i nums
    int[][] dp = new int[n + 1][n + 1];
    List<Pair<Integer, Integer>> sortedNums = new ArrayList<>();

    for (int i = 0; i < n; ++i)
      sortedNums.add(new Pair<>(nums2.get(i), nums1.get(i)));

    sortedNums.sort(Comparator.comparingInt(a -> a.getKey()));

    for (int i = 1; i <= n; ++i) {
      final int num2 = sortedNums.get(i - 1).getKey();
      final int num1 = sortedNums.get(i - 1).getValue();
      for (int j = 1; j <= i; ++j)
        dp[i][j] = Math.max(
            // max reduced value if we do j ops on the first i - 1 nums
            dp[i - 1][j],
            // max reduced value if we do j - 1 ops on the first i - 1 nums +
            // making i-th num of nums1 to 0 at j-th operation
            dp[i - 1][j - 1] + num2 * j + num1);
    }

    for (int op = 0; op <= n; ++op)
      if (sum1 + sum2 * op - dp[n][op] <= x)
        return op;

    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
class Solution:
  def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
    n = len(nums1)
    # dp[i][j] := max reduced value if we do j ops on the first i nums
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    sum1 = sum(nums1)
    sum2 = sum(nums2)

    for i, (num2, num1) in enumerate(sorted(zip(nums2, nums1)), 1):
      for j in range(1, i + 1):
        dp[i][j] = max(
            # max reduced value if we do j ops on the first i - 1 nums
            dp[i - 1][j],
            # max reduced value if we do j - 1 ops on the first i - 1 nums +
            # making i-th num of nums1 to 0 at j-th operation
            dp[i - 1][j - 1] + num2 * j + num1
        )

    for op in range(n + 1):
      if sum1 + sum2 * op - dp[n][op] <= x:
        return op

    return -1

Approach 2: 1D DP

  • Time: $O(n^2)$
  • Space: $O(n)$
 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
26
27
28
29
30
31
32
33
class Solution {
 public:
  int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
    const int n = nums1.size();
    const int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
    const int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
    // dp[i][j] := max reduced value if we do j ops on the first i nums
    vector<int> dp(n + 1);
    vector<pair<int, int>> sortedNums;

    for (int i = 0; i < n; ++i)
      sortedNums.emplace_back(nums2[i], nums1[i]);

    sort(sortedNums.begin(), sortedNums.end());

    for (int i = 1; i <= n; ++i) {
      const auto [num2, num1] = sortedNums[i - 1];
      for (int j = i; j > 0; --j)
        dp[j] = max(
            // max reduced value if we do j ops on the first i - 1 nums
            dp[j],
            // max reduced value if we do j - 1 ops on the first i - 1 nums +
            // making i-th num of nums1 to 0 at j-th operation
            dp[j - 1] + num2 * j + num1);
    }

    for (int op = 0; op <= n; ++op)
      if (sum1 + sum2 * op - dp[op] <= x)
        return op;

    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
26
27
28
29
30
31
32
33
class Solution {
  public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
    final int n = nums1.size();
    final int sum1 = nums1.stream().mapToInt(Integer::intValue).sum();
    final int sum2 = nums2.stream().mapToInt(Integer::intValue).sum();
    // dp[j] := max reduced value if we do j ops on the nums so far
    int[] dp = new int[n + 1];
    List<Pair<Integer, Integer>> sortedNums = new ArrayList<>();

    for (int i = 0; i < n; ++i)
      sortedNums.add(new Pair<>(nums2.get(i), nums1.get(i)));

    sortedNums.sort(Comparator.comparingInt(a -> a.getKey()));

    for (int i = 1; i <= n; ++i) {
      final int num2 = sortedNums.get(i - 1).getKey();
      final int num1 = sortedNums.get(i - 1).getValue();
      for (int j = i; j > 0; --j)
        dp[j] = Math.max(
            // max reduced value if we do j ops on the first i - 1 nums
            dp[j],
            // max reduced value if we do j - 1 ops on the first i - 1 nums +
            // making i-th num of nums1 to 0 at j-th operation
            dp[j - 1] + num2 * j + num1);
    }

    for (int op = 0; op <= n; ++op)
      if (sum1 + sum2 * op - dp[op] <= x)
        return op;

    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
class Solution:
  def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
    n = len(nums1)
    # dp[j] := max reduced value if we do j ops on the nums so far
    dp = [0] * (n + 1)
    sum1 = sum(nums1)
    sum2 = sum(nums2)

    for i, (num2, num1) in enumerate(sorted(zip(nums2, nums1)), 1):
      for j in range(i, 0, -1):
        dp[j] = max(
            # max reduced value if we do j ops on the first i - 1 nums
            dp[j],
            # max reduced value if we do j - 1 ops on the first i - 1 nums +
            # making i-th num of nums1 to 0 at j-th operation
            dp[j - 1] + num2 * j + num1
        )

    for op in range(n + 1):
      if sum1 + sum2 * op - dp[op] <= x:
        return op

    return -1