Skip to main content
Talentd

Choose Numbers From Two Arrays in Range - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic Programming7 min readAsked at: Adobe
Practice this problem

Problem Statement

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

A range [l, r] (inclusive) where 0 <= l <= r < n is balanced if:

  • For every i in the range [l, r], you pick either nums1[i] or nums2[i].
  • The sum of the numbers you pick from nums1 equals to the sum of the numbers you pick from nums2 (the sum is considered to be 0 if you pick no numbers from an array).

Two balanced ranges from [l1, r1] and [l2, r2] are considered to be different if at least one of the following is true:

  • l1 != l2
  • r1 != r2
  • nums1[i] is picked in the first range, and nums2[i] is picked in the second range or vice versa for at least one i.

Return the number of different ranges that are balanced. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: nums1 = [1,2,5], nums2 = [2,6,3]
Output: 3
Explanation: The balanced ranges are:
- [0, 1] where we choose nums2[0], and nums1[1].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 2 = 2.
- [0, 2] where we choose nums1[0], nums2[1], and nums1[2].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 1 + 5 = 6.
- [0, 2] where we choose nums1[0], nums1[1], and nums2[2].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 1 + 2 = 3.
Note that the second and third balanced ranges are different.
In the second balanced range, we choose nums2[1] and in the third balanced range, we choose nums1[1].

Example 2:

Input: nums1 = [0,1], nums2 = [1,0]
Output: 4
Explanation: The balanced ranges are:
- [0, 0] where we choose nums1[0].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 0 = 0.
- [1, 1] where we choose nums2[1].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 0 = 0.
- [0, 1] where we choose nums1[0] and nums2[1].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 0 = 0.
- [0, 1] where we choose nums2[0] and nums1[1].
  The sum of the numbers chosen from nums1 equals the sum of the numbers chosen from nums2: 1 = 1.

 

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 100
  • 0 <= nums1[i], nums2[i] <= 100

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(2^n)O(n)Understanding the decision tree or validating small inputs
Dynamic Programming on Sum StatesO(n * R)O(R)General case where cumulative sums fall within a manageable range
DP with Prefix Sum OptimizationO(n * R)O(R)Large transition ranges where batching updates with prefix sums reduces overhead

Video Solution

Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,948 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Choose Numbers From Two Arrays in Range easy or hard?
Choose Numbers From Two Arrays in Range is classified as a Hard problem because the brute-force approach is exponential and the correct solution requires modeling the process as dynamic programming over sum states with careful range management.
Choose Numbers From Two Arrays in Range Python/Java solution
The solution in Python or Java typically maintains a DP array indexed by shifted sums to handle negative values. For every index i, update the next DP state by adding nums1[i] and nums2[i] to existing sums, and finally count how many sums fall within [lower, upper].
How to solve Choose Numbers From Two Arrays in Range in O(n)?
A strict O(n) solution is generally not feasible because the algorithm must track multiple possible cumulative sums at every step. The practical optimal solution is O(n * R) using dynamic programming with state compression, where R represents the bounded sum range maintained during transitions.
What is the best approach for Choose Numbers From Two Arrays in Range?
The most effective approach uses dynamic programming on cumulative sums. Track how many ways each possible sum can be formed after processing each index, then update the states by adding either nums1[i] or nums2[i]. This reduces the exponential choice tree to O(n * R) time, where R is the sum range being tracked.
Is Choose Numbers From Two Arrays in Range asked at Google/Amazon/Meta?
Problems involving dynamic programming over cumulative sums and choice at each index frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of state transitions, range handling, and DP optimization techniques.
What data structure is used in Choose Numbers From Two Arrays in Range?
The main structure is a dynamic programming array (or hash map) that stores counts of ways to reach each possible cumulative sum. Prefix sums may also be used to accelerate range updates during DP transitions.
What is the time complexity of Choose Numbers From Two Arrays in Range?
The optimized dynamic programming solution runs in O(n * R) time, where n is the array length and R is the range of possible cumulative sums considered in the DP state. Space complexity is O(R) because only the current set of reachable sums must be stored.

Ready to solve this problem?

Practice Choose Numbers From Two Arrays in Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Intersection of Two Arrays

Next

Intersection of Two Arrays II