Choose Numbers From Two Arrays in Range - Video Solutions

Problem Overview: You have two arrays of equal length. At every index i, you must choose either nums1[i] or nums2[i]. The goal is to count how many different selections produce a total sum that lies inside a given range [lower, upper].

Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)

The most direct approach explores every possible choice. For each index, branch into two paths: pick nums1[i] or nums2[i]. Maintain the running sum and check if the final value falls inside [lower, upper]. This generates 2^n combinations, which becomes infeasible even for moderate n. This approach is useful only to reason about the search space and verify correctness on very small inputs.

Approach 2: Dynamic Programming on Sum States (O(n * R) time, O(R) space)

The key observation: the only information that matters at index i is the current cumulative sum. Let dp[s] represent the number of ways to reach sum s after processing some prefix of the arrays. For each position i, transition to the next state by adding either nums1[i] or nums2[i]. This becomes a classic state transition over sums. Because sums can be negative, apply an offset when storing them in an array. The number of tracked sums is bounded by the possible value range, which keeps the state space manageable.

Approach 3: DP with Prefix Sum Optimization (O(n * R) time, O(R) space)

When the valid range of sums becomes large, repeatedly updating individual states can be slow. A more efficient technique uses prefix sums to aggregate transitions over ranges. Instead of updating each target sum independently, accumulate contributions using a prefix array and convert them back to counts in one pass. This reduces constant factors and keeps the DP transitions efficient even when the allowed sum interval is wide. The technique is common in dynamic programming problems that involve range transitions.

The DP array is updated for each index while preserving only the current row, so memory stays proportional to the tracked sum range. The final answer is the total number of ways where the ending sum lies between lower and upper.

Recommended for interviews: The dynamic programming formulation with compressed state is the expected solution. Start by describing the brute force choice tree to show understanding of the search space. Then convert it into a DP over cumulative sums. Interviewers usually look for the insight that each position only depends on the previous set of reachable sums, which turns the exponential search into a polynomial-time solution using arrays and DP state transitions.