Minimum time to make array sum at most x

Array Dynamic Programming Sorting

27.1% acceptance

Feb 25, 2026

248

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(nums1: Vec<i32>, nums2: Vec<i32>, x: i32) -> i32 {
    let n = nums1.len();
    let total1: i32 = nums1.iter().sum();
    let total2: i32 = nums2.iter().sum();
    if total1 <= x { return 0; }
    // Sort pairs by nums2 ascending; zero element with higher nums2 last (more savings at later time t)
    let mut pairs: Vec<(i32, i32)> = nums1.iter().zip(nums2.iter()).map(|(&a, &b)| (a, b)).collect();
    pairs.sort_by_key(|&(_, b)| b);
    // dp[ops] = max savings when performing exactly ops zero-operations on first j elements
    let mut dp = vec![0i64; n + 1];
    for j in 0..n {
      let (a, b) = pairs[j];
      for ops in (1..=j+1).rev() {
        let saving = a as i64 + ops as i64 * b as i64;
        if dp[ops-1] + saving > dp[ops] { dp[ops] = dp[ops-1] + saving; }
      }
    }
    for t in 0..=n {
      if total1 as i64 + t as i64 * total2 as i64 - dp[t] <= x as i64 {
        return t as i32;
      }
    }
    -1
  }
}