We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Make Array Sum At Most x

Number: 2952

Difficulty: Hard

Paid? No

Companies: Jane Street

Problem Description

We are given two equal‐length 0-indexed arrays – nums1 and nums2. Every second, every element in nums1 is increased by its corresponding value in nums2. Immediately after the update in that second, you are allowed to “reset” exactly one element (i.e. set that element’s value to 0). Given an integer x, we want to determine the minimum number of seconds needed so that the sum of nums1 becomes less than or equal to x. If no series of operations achieves this, return -1.

Key Insights

  • Every second every element increases by its corresponding nums2 value.
  • Resetting an index i at second s “saves” some amount: without a reset index i would be nums1[i] + T×nums2[i] (if T seconds elapse), but if reset at time s its final value becomes (T–s)×nums2[i].
  • The benefit (reduction) from resetting index i at second s is: nums1[i] + s×nums2[i].
  • Since you can only perform at most one reset per second, if T seconds pass you may reset at most min(T, n) indices.
  • Given T seconds the “baseline” sum if no resets are applied is sum(nums1) + T×sum(nums2). Then by “spending” resets on selected indices you can reduce this sum by a total “benefit” which is maximized if for each reset you choose an index i and assign it a reset time s (distinct and between 1 and T) so that the benefit nums1[i] + s×nums2[i] is as high as possible.
  • In an optimal strategy the best available s‐values (namely the largest ones) will be assigned to those indices that have the highest “leverage” (typically those with a high nums2 value and a high nums1 value).
  • A crucial observation is that if T ≥ n then you may “use” all n resets, and the best possible final sum becomes independent of T. (It equals sum(nums1) minus a constant “saved” amount.) Hence, if even using the maximum resets (with T = n seconds) does not drive the final sum to ≤ x then no solution exists.

Space and Time Complexity

Time Complexity: O(n log n) – sorting the indices once plus O(n) work per binary search iteration over T (and T is searched in the range [0, n]). Space Complexity: O(n) – extra space for storing the sort order.

Solution

We solve the problem by “guessing” a candidate number of seconds T using binary search. For a given T, the sum without any resets is S_base = sum(nums1) + T×sum(nums2). We are allowed to perform resets in T seconds – that is, at most R = min(T, n) resets.

For any reset, if you choose to reset index i at second s then its benefit is (nums1[i] + s×nums2[i]). In order to “save” as many points as possible we want to use our available resets on the indices that give the greatest benefit. Also, since s can be chosen from 1 to T (each used only once), the optimal assignment gives the largest available s (namely T) to the index that “pays” for it best (i.e. with the highest nums2), the second‑largest s (T–1) to the next, and so on. Thus, after sorting indices in descending order of nums2, the optimal total benefit if we use r resets is equal to the sum for j from 1 to r of   (nums1[chosen_j] + (T – j + 1)×nums2[chosen_j]).

If the final sum S_final = S_base – (optimal benefit) becomes ≤ x then T seconds is enough. (When T ≥ n the benefit is independent of T so if even T = n fails then no solution exists.) We then use binary search on T in the range [0, n] to find the minimum T for which S_final ≤ x.

Data structures used: • An array of indices sorted based on nums2 in descending order. • A helper function (check) that computes the final sum for a candidate T by “greedily” taking the top min(T, n) indices and assigning them the reset times T, T–1, …, (T–r+1).

The binary search allows us to efficiently find the minimum seconds required.

Code Solutions

# Python solution with line-by-line comments
def minTime(nums1, nums2, x):
    n = len(nums1)
    # Precompute baseline sum without resets: sum(nums1) + T * sum(nums2)
    total_nums1 = sum(nums1)
    total_nums2 = sum(nums2)
    
    # Create list of indices sorted by nums2 in descending order.
    # A higher nums2 gives the possibility for a larger benefit when assigned a later reset time.
    sorted_indices = sorted(range(n), key=lambda i: nums2[i], reverse=True)
    
    # Check function: for a given T seconds, can we achieve a final sum <= x?
    def check(T):
        # Number of resets we can perform in T seconds is r = min(T, n)
        r = min(T, n)
        # Baseline total if no resets occur
        base_sum = total_nums1 + T * total_nums2
        # Compute maximum total benefit from resets.
        # For j from 1 to r, assign s = (T - j + 1)
        benefit = 0
        for j in range(1, r+1):
            i = sorted_indices[j-1]  # j-th best candidate (0-indexed)
            benefit += nums1[i] + (T - j + 1) * nums2[i]
        final_sum = base_sum - benefit
        return final_sum <= x

    # Before binary search, check the case T >= n when we use all resets.
    # If even when T == n the final sum is too high then no T can work.
    if not check(n):
        return -1

    # Binary search T over [0, n]. We already have check(n)==True.
    low, high = 0, n
    result = n
    while low <= high:
        mid = (low + high) // 2
        if check(mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1
    return result

# Example usage:
print(minTime([1,2,3], [1,2,3], 4))  # Expected output: 3
print(minTime([1,2,3], [3,3,3], 4))  # Expected output: -1
← Back to All Questions