Minimum Time to Make Array Sum At Most x

Minimum Time to Make Array Sum At Most x

What is this problem about?

The Minimum Time to Make Array Sum At Most x problem gives you two arrays and an integer x. In each operation, you can select one index and set arr1[i] = 0, permanently removing that element's contribution. Each second, all elements in arr1 increase by their corresponding arr2 value. Find the minimum number of seconds to make the sum of arr1 at most x, or return -1 if impossible. This hard coding problem is a sophisticated DP involving sorted order optimization.

Why is this asked in interviews?

Jane Street asks this at a senior level because it requires the non-obvious insight that the optimal order to zero out elements — sorted by arr2[i] ascending — minimizes total accumulated gain. Combined with DP over this optimal ordering, it tests both mathematical reasoning and algorithmic depth. The array, sorting, and dynamic programming interview pattern is combined with a greedy key observation.

Algorithmic pattern used

Sorting + DP. The key insight: to minimize time, zero out elements with the smallest arr2 values last (they contribute less growth per second, so it's cheaper to handle them later). Sort pairs (arr1[i], arr2[i]) by arr2[i] ascending. Define dp[i][j] = maximum sum reduction achievable by selecting exactly j elements from the first i pairs to zero out (in i seconds). Transition: include or exclude pair i. Final answer: find minimum j where totalSum + j * totalArr2Sum - dp[n][j] ≤ x.

Example explanation

arr1 = [1, 2], arr2 = [1, 3], x = 1.

• After sorting by arr2: [(1,1), (2,3)].
• Total sum = 3. Total arr2 sum = 4.
• dp[2][1] = best single reduction = 2 (zero out element with arr1=2 after 1 second).
• At t=1: sum = 3 + 14 - 2 = 5? Not ≤ 1. Need t=2: zero both. Sum = 3 + 24 - dp[2][2] = ...
• Continue until sum ≤ x.

Common mistakes candidates make

• Not recognizing the optimal zeroing order (smallest arr2 first).
• Confusing "sum grows each second" with "sum only grows once."
• DP indexing errors when transitioning from i-1 to i.
• Off-by-one in applying the formula after j seconds.

Interview preparation tip

Problems where "elements grow over time and you can freeze them" require identifying the optimal freeze order first. Elements that grow fastest should be frozen first (zeroed out earliest). Proving this greedy ordering via exchange argument and then building DP on top is the standard two-step approach. Jane Street and similar quantitative finance firms frequently test this combination of mathematical optimization and DP — practice proving greedy choices rigorously before coding.