LeetCode 1983 - Widest Pair of Indices With Equal Range Sum

LeetCode Problem 1983

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the widest subarray (continuous segment) in two binary arrays nums1 and nums2 such that the sum of elements in that segment is equal for both arrays. Formally, we need to find indices (i, j) with i <= j such that:

sum(nums1[i..j]) == sum(nums2[i..j])

and maximize the distance j - i + 1.

The input consists of two equal-length binary arrays. The output is the length of the widest valid subarray. If no valid subarray exists, we return 0.

The constraints reveal that the array length n can be up to 10^5. Therefore, any solution with a quadratic time complexity will be too slow, and we need a solution closer to linear time.

Important edge cases include arrays with no matching sums, arrays of length 1, and arrays where the widest subarray spans the entire array.

Approaches

Brute Force

A brute-force approach iterates over all possible subarrays (i, j) and computes the sums for nums1 and nums2 for each segment. If the sums match, we update the maximum distance. While this approach is correct, it is too slow because there are roughly O(n^2) subarrays, and computing each sum naively is O(n). Even using prefix sums to compute subarray sums in O(1) would still lead to O(n^2) total time, which is not feasible for n = 10^5.

Optimal Approach

The key observation is that for a subarray (i, j) to have equal sums in both arrays:

sum(nums1[i..j]) == sum(nums2[i..j])

This is equivalent to saying:

prefix1[j] - prefix1[i-1] == prefix2[j] - prefix2[i-1]

or

(prefix1[j] - prefix2[j]) == (prefix1[i-1] - prefix2[i-1])

If we define diff[k] = prefix1[k] - prefix2[k] and let diff[-1] = 0, then we need diff[j] == diff[i-1]. This reduces the problem to finding the maximum distance between two equal values in the difference array, which can be done efficiently using a hash map to store the first occurrence of each difference.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Compute all subarray sums using prefix sums
Optimal	O(n)	O(n)	Use prefix difference and hashmap to track first occurrences

Algorithm Walkthrough

1. Initialize a hash map first_occurrence to store the first index where each difference diff occurs. Initialize it with {0: -1} to handle subarrays starting at index 0.

2. Initialize a variable max_width to 0 to store the maximum distance found.

3. Initialize diff = 0 to track the running difference prefix1 - prefix2.

4. Iterate through each index i from 0 to n-1.

5. Update the running difference: diff += nums1[i] - nums2[i].

6. If diff has been seen before in first_occurrence, calculate the distance from the first occurrence to i and update max_width if it is larger.

7. If diff has not been seen, store the current index in first_occurrence.

8. After iterating, return max_width.

Why it works: By tracking the first occurrence of each difference, any future occurrence of the same difference implies a subarray with equal sums between the arrays. Storing only the first occurrence ensures we maximize the distance.

Python Solution

from typing import List

class Solution:
    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
        first_occurrence = {0: -1}
        diff = 0
        max_width = 0
        
        for i in range(len(nums1)):
            diff += nums1[i] - nums2[i]
            if diff in first_occurrence:
                max_width = max(max_width, i - first_occurrence[diff])
            else:
                first_occurrence[diff] = i
        
        return max_width

Explanation: We maintain the running difference diff between prefix sums of nums1 and nums2. The hashmap first_occurrence stores the earliest index where a particular difference occurs. Whenever we encounter the same difference again, the subarray between the first occurrence and current index has equal sums in both arrays. Updating max_width ensures we capture the widest subarray.

Go Solution

func widestPairOfIndices(nums1 []int, nums2 []int) int {
    firstOccurrence := map[int]int{0: -1}
    diff := 0
    maxWidth := 0
    
    for i := 0; i < len(nums1); i++ {
        diff += nums1[i] - nums2[i]
        if firstIndex, exists := firstOccurrence[diff]; exists {
            if i - firstIndex > maxWidth {
                maxWidth = i - firstIndex
            }
        } else {
            firstOccurrence[diff] = i
        }
    }
    
    return maxWidth
}

Go-specific notes: Go requires explicit map existence checks. We initialize the map with {0: -1} to handle subarrays starting at index 0. There is no concern about integer overflow because the difference is bounded by the array length.

Worked Examples

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

i	nums1[i]	nums2[i]	diff	first_occurrence	max_width
0	1	0	1	{0:-1,1:0}	0
1	1	1	1	{0:-1,1:0}	1
2	0	1	0	{0:-1,1:0}	3
3	1	0	1	{0:-1,1:0}	3

Return 3.

Example 2: nums1 = [0,1], nums2 = [1,1]

i	nums1[i]	nums2[i]	diff	first_occurrence	max_width
0	0	1	-1	{0:-1,-1:0}	0
1	1	1	0	{0:-1,-1:0}	2

Return 2 (distance = i - (-1) = 1 - (-1) = 2).

Example 3: nums1 = [0], nums2 = [1]

i	nums1[i]	nums2[i]	diff	first_occurrence	max_width
0	0	1	-1	{0:-1,-1:0}	0

Return 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over arrays, each operation is O(1)
Space	O(n)	Hash map may store up to n different differences

The complexity is linear because we only scan the arrays once, and each difference is stored only once in the hash map.

Test Cases

# Provided examples
assert Solution().widestPairOfIndices([1,1,0,1], [0,1,1,0]) == 3  # Example 1
assert Solution().widestPairOfIndices([0,1], [1,1]) == 2          # Example 2
assert Solution().widestPairOfIndices([0], [1]) == 0              # Example 3

# Edge and additional cases
assert Solution().widestPairOfIndices([1,1,1], [1,1,1]) == 3       # Entire array matches
assert Solution().widestPairOfIndices([0,0,0], [1,1,1]) == 0       # No matches
assert Solution().widestPairOfIndices([1,0,1,0], [0,1,0,1]) == 2   # Multiple segments, pick widest
assert Solution().widestPairOfIndices([1], [1]) == 1               # Single element match
assert Solution().widestPairOfIndices([0], [0]) == 1               # Single element match zero

Test	Why
Example 1	General case, subarray not starting at index 0
Example 2	Small array, sub