LeetCode Problem 2143

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

In this problem, we are given two arrays, nums1 and nums2, both of length n. For every index i, we must choose exactly one value, either nums1[i] or nums2[i], when considering a subarray range [l, r].

The goal is to count how many distinct ways exist to choose values inside a contiguous range such that:

• The total sum of all chosen values from nums1 equals the total sum of all chosen values from nums2.
• Every index in the chosen range contributes exactly one number.
• Different choice patterns count as different balanced ranges, even if the range boundaries are the same.

A useful way to reinterpret the problem is this:

• If we choose nums1[i], we add nums1[i] to the left side.
• If we choose nums2[i], we add nums2[i] to the right side.

We want the final totals on both sides to match.

Another equivalent interpretation is to track a running difference:

• Choosing nums1[i] increases the difference by nums1[i]
• Choosing nums2[i] decreases the difference by nums2[i]

A range is balanced if the final difference becomes 0.

The constraints are important:

• n <= 100
• nums1[i], nums2[i] <= 100

Since values are relatively small, the total possible sum difference is bounded. The maximum possible absolute difference is:

$$100 \times 100 = 10000$$

This strongly suggests that a dynamic programming solution over possible differences is feasible.

Several edge cases are important:

• Single-element ranges where either value is 0
• Multiple ways to achieve balance in the same range
• Ranges where all values are zero
• Cases where no balanced range exists
• Negative running differences during computation

A naive implementation that enumerates all possible selections for all subarrays would explode exponentially, because every position has two choices.

Approaches

Brute Force Approach

The brute force solution considers every possible subarray [l, r].

For each subarray:

1. Enumerate all possible ways to choose between nums1[i] and nums2[i]
2. Compute the two sums
3. Check whether the sums are equal

If a subarray has length k, then it has 2^k possible selection patterns.

Across all subarrays, the total complexity becomes extremely large:

$$\sum_{k=1}^{n} (n-k+1)\cdot 2^k$$

This is exponential and completely infeasible for n = 100.

The brute force approach is correct because it explicitly checks every possible valid configuration, but it is too slow.

Key Insight

The critical observation is that we only care about the difference between the two sums.

Define:

• Choosing nums1[i] contributes +nums1[i]
• Choosing nums2[i] contributes -nums2[i]

Then a balanced range is simply a sequence whose total difference equals 0.

This transforms the problem into a dynamic programming problem over possible difference values.

For every ending index r, we maintain:

• dp[diff] = number of ways to build subarrays ending at r whose current difference is diff

At index i, every existing state can transition in two ways:

• Add nums1[i]
• Subtract nums2[i]

We also start new subarrays at every index.

Since the total possible difference range is bounded by [-10000, 10000], the number of DP states remains manageable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(n^2 \cdot 2^n)$	$O(1)$	Enumerates every subarray and every selection pattern
Optimal	$O(n \cdot S)$	$O(S)$	Dynamic programming over possible differences, where $S$ is the difference range

Here:

$$S = 20001$$

because differences range from -10000 to 10000.

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Define a hash map dp where:

• Key = current difference
• Value = number of ways to achieve that difference for subarrays ending at the previous index

2. Initialize the answer as 0.
3. Iterate through each index i.
4. Create a new hash map next_dp.
5. Start new subarrays at index i.

There are two possible choices:

• Choose nums1[i], producing difference +nums1[i]
• Choose nums2[i], producing difference -nums2[i]

Update next_dp accordingly. 6. Extend all previously tracked subarrays.

For every (diff, count) in dp:

• Choosing nums1[i] creates:

$$diff + nums1[i]$$

• Choosing nums2[i] creates:

$$diff - nums2[i]$$

Add the counts into next_dp. 7. Any state where the resulting difference equals 0 represents balanced ranges ending at index i.

Add next_dp[0] to the answer. 8. Replace dp with next_dp. 9. Continue until all indices are processed. 10. Return the answer modulo $10^9 + 7$.

Why it works

The DP invariant is:

• dp[d] stores the number of distinct ways to construct contiguous subarrays ending at the current position whose sum difference equals d.

Every subarray ending at index i either:

• Starts at i
• Or extends a subarray ending at i - 1

The transitions exhaustively cover both possibilities.

A subarray is balanced exactly when its difference becomes 0, so counting states with difference 0 correctly counts all balanced ranges.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        
        dp = defaultdict(int)
        answer = 0
        
        for a, b in zip(nums1, nums2):
            next_dp = defaultdict(int)
            
            # Start new subarrays
            next_dp[a] = (next_dp[a] + 1) % MOD
            next_dp[-b] = (next_dp[-b] + 1) % MOD
            
            # Extend previous subarrays
            for diff, count in dp.items():
                next_dp[diff + a] = (
                    next_dp[diff + a] + count
                ) % MOD
                
                next_dp[diff - b] = (
                    next_dp[diff - b] + count
                ) % MOD
            
            answer = (answer + next_dp[0]) % MOD
            
            dp = next_dp
        
        return answer

The implementation uses a hash map where keys represent sum differences and values represent the number of ways to obtain those differences.

For every index, we construct a fresh DP map called next_dp. This map stores all subarrays ending at the current position.

The first updates correspond to starting new subarrays at the current index. Choosing nums1[i] contributes a positive difference, while choosing nums2[i] contributes a negative difference.

Next, we extend every previously tracked subarray by appending the current index. Each previous state branches into two new states.

After processing all transitions, next_dp[0] contains the number of balanced subarrays ending at the current index. We add this to the global answer.

Finally, we move forward by assigning dp = next_dp.

Go Solution

package main

func countSubranges(nums1 []int, nums2 []int) int {
	const MOD int = 1_000_000_007

	dp := map[int]int{}
	answer := 0

	for i := 0; i < len(nums1); i++ {
		a := nums1[i]
		b := nums2[i]

		nextDP := map[int]int{}

		// Start new subarrays
		nextDP[a] = (nextDP[a] + 1) % MOD
		nextDP[-b] = (nextDP[-b] + 1) % MOD

		// Extend previous subarrays
		for diff, count := range dp {
			newDiff1 := diff + a
			newDiff2 := diff - b

			nextDP[newDiff1] = (nextDP[newDiff1] + count) % MOD
			nextDP[newDiff2] = (nextDP[newDiff2] + count) % MOD
		}

		answer = (answer + nextDP[0]) % MOD

		dp = nextDP
	}

	return answer
}

The Go implementation follows the exact same DP structure as the Python solution.

Since Go does not have Python's defaultdict, regular maps are used. Missing keys default to 0, which naturally supports accumulation logic.

All additions are performed modulo 1_000_000_007 to avoid overflow and satisfy the problem requirement.

Worked Examples

Example 1

nums1 = [1,2,5]
nums2 = [2,6,3]

Index 0

Possible new subarrays:

Choice	Difference
choose nums1[0] = 1	1
choose nums2[0] = 2	-2

DP state:

Difference	Count
1	1
-2	1

Balanced count added:

Difference 0 Count
0

Answer = 0

Index 1

Start new subarrays:

Difference	Count
2	1
-6	1

Extend previous states:

From difference 1:

Choice	New Difference
+2	3
-6	-5

From difference -2:

Choice	New Difference
+2	0
-6	-8

Updated DP:

Difference	Count
2	1
-6	1
3	1
-5	1
0	1
-8	1

Balanced count added:

Difference 0 Count
1

Answer = 1

Index 2

Start new subarrays:

Difference	Count
5	1
-3	1

Extend previous states:

From 2:

Choice	New Difference
+5	7
-3	-1

From -6:

Choice	New Difference
-1
-9

From 3:

Choice	New Difference
8
0

From -5:

Choice	New Difference
0
-8

From 0:

Choice	New Difference
5
-3

From -8:

Choice	New Difference
-3
-11

Difference 0 appears twice.

Answer becomes:

$$1 + 2 = 3$$

Final answer = 3.

Example 2

nums1 = [0,1]
nums2 = [1,0]

Index 0

Start new subarrays:

Choice	Difference
choose nums1[0]	0
choose nums2[0]	-1

DP:

Difference	Count
0	1
-1	1

Balanced count:

Difference 0 Count
1

Answer = 1

Index 1

Start new subarrays:

Difference	Count
1	1
0	1

Extend previous states.

From difference 0:

Choice	New Difference
+1	1
-0	0

From difference -1:

Choice	New Difference
0
-1

Final DP includes:

Difference	Count
0	3

Add 3 balanced ranges.

Final answer:

$$1 + 3 = 4$$

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n \cdot S)$	For each index, we iterate through all reachable differences
Space	$O(S)$	DP stores counts for all possible differences

Here:

$$S = 20001$$

because the maximum absolute difference is bounded by:

$$100 \times 100 = 10000$$

In practice, the number of reachable states is often much smaller.

Test Cases

from typing import List

s = Solution()

assert s.countSubranges([1,2,5], [2,6,3]) == 3  # Provided example 1

assert s.countSubranges([0,1], [1,0]) == 4  # Provided example 2

assert s.countSubranges([0], [0]) == 2  # Single element, both choices balanced

assert s.countSubranges([1], [2]) == 0  # No balanced range possible

assert s.countSubranges([5], [5]) == 0  # Choosing exactly one side prevents equality

assert s.countSubranges([0,0], [0,0]) == 8  # Every selection is balanced

assert s.countSubranges([1,1], [1,1]) == 2  # Two balanced selections over full range

assert s.countSubranges([2,2,2], [2,2,2]) == 12  # Multiple balanced combinations

assert s.countSubranges([100]*100, [100]*100) > 0  # Large boundary values

assert s.countSubranges([1,2,3], [4,5,6]) == 0  # No valid balances

assert s.countSubranges([0,0,1], [0,1,0]) >= 0  # Mixed zero handling

Test Summary

Test	Why
[1,2,5], [2,6,3]	Validates provided example
[0,1], [1,0]	Validates multiple balanced configurations
[0], [0]	Tests single-element zero case
[1], [2]	Tests impossible balance
[5], [5]	Ensures equal values alone are not balanced
[0,0], [0,0]	Tests exponential number of balanced selections
[1,1], [1,1]	Tests symmetric arrays
[2,2,2], [2,2,2]	Tests many repeated balanced combinations
[100]*100	Stress test for maximum constraints
[1,2,3], [4,5,6]	Tests no valid solutions
[0,0,1], [0,1,0]	Tests mixed zero and nonzero transitions

Edge Cases

Arrays Containing Zeros

Zeros are particularly important because choosing a zero from one side may immediately create a balanced range.

For example:

nums1 = [0]
nums2 = [0]

Both choices independently produce difference 0, so there are two valid balanced ranges.

The implementation correctly handles this because both transitions are inserted separately into the DP map.

Equal Values at the Same Index

A common mistake is assuming that if nums1[i] == nums2[i], then choosing either one automatically creates balance.

That is incorrect because only one side receives the value.

For example:

nums1 = [5]
nums2 = [5]

Possible differences are:

• +5
• -5

Neither equals zero.

The DP formulation naturally handles this by explicitly tracking signed differences.

Multiple Ways Producing the Same Difference

Different selection paths may lead to the same difference value.

For example:

nums1 = [0,1]
nums2 = [1,0]

Several distinct configurations end with difference 0.

A buggy implementation might overwrite counts instead of accumulating them.

The solution avoids this by summing counts inside the DP map:

next_dp[new_diff] += count

This guarantees all distinct configurations are counted correctly.