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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Choose Numbers From Two Arrays in Range

Number: 2282

Difficulty: Hard

Paid? Yes

Companies: Adobe

Problem Description

Given two integer arrays, nums1 and nums2, of equal length n, consider a contiguous range [l, r]. For every i in this range, you must choose either nums1[i] or nums2[i]. A range is defined as balanced if the sum of the numbers picked from nums1 equals the sum of the numbers picked from nums2. Two balanced ranges are different if their boundaries differ or if there is at least one index in the range where the choice of array is different. Return the count of different balanced ranges modulo 10^9+7.

Key Insights

  • For each index i in the range [l, r], choosing nums1[i] contributes nums1[i] to the left sum and choosing nums2[i] contributes nums2[i] to the right sum.
  • The condition for balance can be reinterpreted as: sum(nums1 choices) - sum(nums2 choices) = 0.
  • At every index, define two possible “difference” contributions: choosing from nums1 gives a change of +nums1[i] and choosing from nums2 gives a change of -nums2[i].
  • For any contiguous subarray, the problem reduces to counting the number of ways (binary decisions at each index) to achieve a total difference (accumulated sum) of 0.
  • A dynamic programming approach can be used over each contiguous range, computing possible difference values with their frequencies.
  • Iterate over all subranges [l, r] (O(n^2) ranges) and use a DP dictionary to update counts of difference sums for the current range.

Space and Time Complexity

Time Complexity: O(n^2 * D) where n is the length of the arrays and D is the range of possible differences (up to around 200*m for a range of length m), which is acceptable for n up to 100. Space Complexity: O(D) for the DP dictionary used for each contiguous range.

Solution

The solution iterates over every possible subarray [l, r]. For each starting index l, we use a dictionary (or map) to track the number of ways to obtain each possible "difference" value, where the difference is defined as (sum from nums1 choices minus sum from nums2 choices). For the first index (r = l) in the range, two possible differences are obtained by picking either nums1[l] (difference = nums1[l]) or nums2[l] (difference = -nums2[l]). Then, as we extend the range from l+1 onward, the DP dictionary is updated by considering the two possible contributions at the new index. If at any step the difference 0 is reached, the count of those DP states is added to our global answer. Finally, answer is returned modulo 10^9+7.

The approach makes use of dynamic programming over the contiguous subarray and a nested loop over start and end indices. The key trick is mapping the problem to a subset sum like solution on differences with a manageable state space.

Code Solutions

MOD = 10**9 + 7

def countBalancedRanges(nums1, nums2):
    n = len(nums1)
    result = 0
    # Iterate over every possible starting index l
    for l in range(n):
        # dp will map current difference to the number of ways to achieve that difference in current range.
        dp = {}
        # At index l, choose from nums1 or nums2.
        diff1 = nums1[l]     # if choose nums1, difference increases.
        diff2 = -nums2[l]    # if choose nums2, difference decreases.
        
        dp[diff1] = dp.get(diff1, 0) + 1
        dp[diff2] = dp.get(diff2, 0) + 1
        
        # If initial difference is 0, add the corresponding counts
        if diff1 == 0:
            result = (result + 1) % MOD
        if diff2 == 0:
            result = (result + 1) % MOD
            
        # Expand range from l+1 to n-1
        for r in range(l+1, n):
            new_dp = {}
            # For each difference so far, extend with two choices for the new index r.
            for diff, count in dp.items():
                # pick nums1[r], update difference
                new_diff1 = diff + nums1[r]
                new_dp[new_diff1] = (new_dp.get(new_diff1, 0) + count) % MOD
                
                # pick nums2[r], update difference
                new_diff2 = diff - nums2[r]
                new_dp[new_diff2] = (new_dp.get(new_diff2, 0) + count) % MOD
            
            dp = new_dp
            # Add ways which yield balanced range (difference 0)
            if 0 in dp:
                result = (result + dp[0]) % MOD
                
    return result

# Example usage:
print(countBalancedRanges([1,2,5], [2,6,3]))   # Expected output: 3
print(countBalancedRanges([0,1], [1,0]))         # Expected output: 4
← Back to All Questions