Problem Description

You are given two binary arrays nums1 and nums2, both 0-indexed (containing only 0s and 1s). Your task is to find a pair of indices (i, j) where i ≤ j such that the sum of elements from index i to index j in nums1 equals the sum of elements from index i to index j in nums2.

Specifically, you need to find indices where: nums1[i] + nums1[i+1] + ... + nums1[j] == nums2[i] + nums2[i+1] + ... + nums2[j]

Among all valid pairs of indices, you want to find the widest pair - the one with the largest distance. The distance between a pair of indices (i, j) is calculated as j - i + 1.

Your goal is to return the distance of the widest valid pair. If no such pair exists that satisfies the equal sum condition, return 0.

For example, if you find that indices (2, 5) form a valid pair where the sums are equal, the distance would be 5 - 2 + 1 = 4.

The key insight is that this problem can be transformed into finding the longest subarray where the difference between corresponding elements sums to zero. If we create a difference array where each element is nums1[i] - nums2[i], we need to find the longest subarray in this difference array that sums to 0. This transformation allows us to use prefix sum techniques with a hash table to efficiently track positions where the cumulative difference is the same, indicating a zero-sum subarray between those positions.

Intuition

The key observation starts with understanding what we're really looking for. When we want nums1[i] + nums1[i+1] + ... + nums1[j] to equal nums2[i] + nums2[i+1] + ... + nums2[j], we can rearrange this equation by moving all terms to one side:

(nums1[i] - nums2[i]) + (nums1[i+1] - nums2[i+1]) + ... + (nums1[j] - nums2[j]) = 0

This transformation is crucial - instead of comparing two separate sums, we're now looking for a subarray where the differences sum to zero.

Think of it this way: if we create a new array where each element is the difference between corresponding elements of nums1 and nums2, our problem becomes finding the longest subarray in this difference array that sums to 0.

Now, how do we find the longest subarray with sum 0? This is where prefix sums come in. If we have a prefix sum s at index i and later encounter the same prefix sum s at index j, it means the elements between indices i+1 and j sum to zero (because the cumulative sum didn't change).

For example, if our prefix sum is 3 at index 2 and again 3 at index 7, then the subarray from index 3 to 7 must sum to 0 (since adding those elements didn't change our cumulative sum).

To efficiently track where we first saw each prefix sum value, we use a hash table. The hash table stores each unique prefix sum value as a key and its first occurrence index as the value. When we encounter a prefix sum we've seen before, we know we've found a zero-sum subarray, and we can calculate its length.

We initialize the hash table with {0: -1} because an empty prefix (before index 0) has sum 0. This handles the edge case where the zero-sum subarray starts from index 0.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation uses prefix sum combined with a hash table to efficiently find the widest pair of indices.

Step 1: Initialize Data Structures

• Create a hash table d with initial value {0: -1}. This handles the case where a valid subarray starts from index 0.
• Initialize ans = 0 to track the maximum distance found.
• Initialize s = 0 to maintain the running prefix sum of differences.

Step 2: Process Arrays Element by Element We iterate through both arrays simultaneously using enumerate(zip(nums1, nums2)):

• For each index i and corresponding elements a from nums1 and b from nums2:
  • Update the prefix sum: s += a - b
  • This accumulates the difference between corresponding elements

Step 3: Check for Valid Subarrays For each position i with prefix sum s:

• If s exists in hash table d:
  • This means we've seen this prefix sum before at index d[s]
  • The subarray from index d[s] + 1 to i has sum 0
  • Calculate the distance: i - d[s]
  • Update the answer: ans = max(ans, i - d[s])
• If s is not in hash table d:
  • Record this as the first occurrence of prefix sum s
  • Store d[s] = i

Why This Works: When we find the same prefix sum at two different indices, it means the elements between those indices sum to zero. For example:

• At index j: prefix sum = 5
• At index k: prefix sum = 5
• This means elements from j+1 to k sum to 0 (since the cumulative sum didn't change)

Time and Space Complexity:

• Time: O(n) where n is the length of the arrays - we traverse once through both arrays
• Space: O(n) in worst case for the hash table if all prefix sums are unique

The algorithm efficiently finds the widest valid pair by keeping track of only the first occurrence of each prefix sum, ensuring we always get the maximum possible distance when we encounter a repeated prefix sum.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

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

Step 1: Create the difference array For each index, calculate nums1[i] - nums2[i]:

• Index 0: 1 - 0 = 1
• Index 1: 1 - 1 = 0
• Index 2: 0 - 1 = -1
• Index 3: 1 - 0 = 1
• Index 4: 0 - 1 = -1
• Index 5: 1 - 1 = 0

Difference array: [1, 0, -1, 1, -1, 0]

Step 2: Process with prefix sum and hash table

Initialize:

• Hash table d = {0: -1} (represents empty prefix before index 0)
• ans = 0 (maximum distance found)
• s = 0 (running prefix sum)

Iteration process:

Step 3: Find the maximum distance The maximum distance found is 6, which corresponds to the entire array from index 0 to 5.

Verification: Let's verify that indices (0, 5) give equal sums:

• nums1[0] + nums1[1] + nums1[2] + nums1[3] + nums1[4] + nums1[5] = 1 + 1 + 0 + 1 + 0 + 1 = 4
• nums2[0] + nums2[1] + nums2[2] + nums2[3] + nums2[4] + nums2[5] = 0 + 1 + 1 + 0 + 1 + 1 = 4

The sums are equal (both are 4), confirming our answer. The distance is 5 - 0 + 1 = 6.

Key Insights from the Example:

1. When the prefix sum returns to a previously seen value, it indicates a zero-sum subarray in the difference array
2. By storing only the first occurrence of each prefix sum, we maximize the distance when we encounter it again
3. The special initialization {0: -1} allows us to handle subarrays that start from index 0

Solution Implementation

Time and Space Complexity

The time complexity is O(n) where n is the length of the arrays nums1 and nums2. The algorithm iterates through both arrays exactly once using the enumerate(zip(nums1, nums2)) construct, performing constant-time operations for each element: calculating the difference a - b, checking dictionary membership, updating the maximum, and potentially adding to the dictionary.

The space complexity is O(n) where n is the length of the arrays. In the worst case, when all cumulative sums s are unique, the dictionary d will store n + 1 entries (including the initial entry {0: -1} plus one entry for each iteration). Each dictionary entry uses constant space to store the sum as a key and the index as a value.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Initialize the Hash Table with {0: -1}

One of the most common mistakes is initializing an empty hash table instead of starting with {0: -1}. This initialization is crucial for handling subarrays that start from index 0.

Why it matters: If the cumulative difference becomes 0 at some index i, it means the entire subarray from index 0 to i has equal sums in both arrays. Without the initial {0: -1}, we would miss these valid subarrays.

Example scenario:

• nums1 = [1, 0, 1]
• nums2 = [0, 1, 1]
• At index 2, the cumulative difference is 0 (meaning nums1[0:3] sum equals nums2[0:3] sum)
• Without {0: -1}, we'd miss this valid subarray of length 3

Solution: Always initialize with first_occurrence = {0: -1} rather than first_occurrence = {}

2. Updating the Hash Table for Every Occurrence of a Prefix Sum

Another mistake is updating the hash table every time we see a prefix sum, not just the first time.

Why it matters: We want the maximum width, so we should keep the earliest (leftmost) occurrence of each prefix sum. Updating it with later occurrences would give us smaller widths.

Incorrect approach:

# WRONG: This updates every time, losing track of the earliest occurrence
for index, (value1, value2) in enumerate(zip(nums1, nums2)):
    sum_difference += value1 - value2
    if sum_difference in first_occurrence:
        max_width = max(max_width, index - first_occurrence[sum_difference])
    first_occurrence[sum_difference] = index  # Updates regardless!

Correct approach:

# RIGHT: Only store the first occurrence
for index, (value1, value2) in enumerate(zip(nums1, nums2)):
    sum_difference += value1 - value2
    if sum_difference in first_occurrence:
        max_width = max(max_width, index - first_occurrence[sum_difference])
    else:
        first_occurrence[sum_difference] = index  # Only on first occurrence

3. Misunderstanding the Distance Calculation

Some developers might incorrectly calculate the distance as i - d[s] instead of understanding why this is correct, leading to off-by-one errors when trying to "fix" it.

Why the formula works: When we have the same prefix sum at indices j and i, the valid subarray spans from j+1 to i (inclusive). The number of elements in this range is i - j, which equals i - d[s] when d[s] = j.

Common mistake: Adding 1 to the formula thinking it needs adjustment: i - d[s] + 1 (incorrect)

Solution: Trust the formula i - d[s] as it correctly calculates the width of the subarray from index d[s] + 1 to i.