Watch the video solution for Widest Pair of Indices With Equal Range Sum, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Programming Live with Larry has 191 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two 0-indexed binary arrays nums1 and nums2. Find the widest pair of indices (i, j) such that i <= j and nums1[i] + nums1[i+1] + ... + nums1[j] == nums2[i] + nums2[i+1] + ... + nums2[j].
The widest pair of indices is the pair with the largest distance between i and j. The distance between a pair of indices is defined as j - i + 1.
Return the distance of the widest pair of indices. If no pair of indices meets the conditions, return 0.
Example 1:
Input: nums1 = [1,1,0,1], nums2 = [0,1,1,0] Output: 3 Explanation: If i = 1 and j = 3: nums1[1] + nums1[2] + nums1[3] = 1 + 0 + 1 = 2. nums2[1] + nums2[2] + nums2[3] = 1 + 1 + 0 = 2. The distance between i and j is j - i + 1 = 3 - 1 + 1 = 3.
Example 2:
Input: nums1 = [0,1], nums2 = [1,1] Output: 1 Explanation: If i = 1 and j = 1: nums1[1] = 1. nums2[1] = 1. The distance between i and j is j - i + 1 = 1 - 1 + 1 = 1.
Example 3:
Input: nums1 = [0], nums2 = [1] Output: 0 Explanation: There are no pairs of indices that meet the requirements.
Constraints:
n == nums1.length == nums2.length1 <= n <= 105nums1[i] is either 0 or 1.nums2[i] is either 0 or 1.Problem Overview: You are given two arrays of equal length. The task is to find the widest pair of indices (i, j) such that the sum of the subarray nums1[i..j] equals the sum of nums2[i..j]. The width is j - i, and you want the maximum possible width.
Approach 1: Brute Force Range Comparison (O(n²) time, O(1) space)
Check every possible pair of indices (i, j). For each pair, compute the subarray sums in both arrays and compare them. This can be done either by recomputing the sum each time or maintaining incremental sums as j expands. If the sums match, update the maximum width. The method is straightforward but inefficient because it evaluates all O(n²) ranges. It mainly helps build intuition for how equal range sums behave.
Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)
The key observation: if sum(nums1[i..j]) == sum(nums2[i..j]), then the difference of their prefix sums at j and i-1 must be equal. Define a running value diff = prefixSum(nums1) - prefixSum(nums2). When the same diff appears at two different indices, the elements between them form a valid range with equal sums.
Iterate once through the arrays while updating diff. Use a hash table to store the first index where each diff occurs. If the same value appears again at index j, the subarray between the earlier index i and j has equal sums. Compute the width and update the maximum. Storing only the earliest occurrence guarantees the widest possible pair.
This technique converts the problem into finding the farthest repeated value of a running prefix difference. The hash lookup is O(1), so the entire algorithm runs in linear time.
The solution relies heavily on prefix sum reasoning and constant-time lookups using a hash table. The arrays are processed in a single pass, which is ideal for large inputs common in array interview problems.
Recommended for interviews: The Prefix Sum + Hash Table approach is the expected solution. It demonstrates recognition of prefix difference patterns and efficient use of hashing to reduce a quadratic search to linear time. Mentioning the brute force approach first shows understanding of the problem space, but the optimized prefix-difference technique shows algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Comparison | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum + Hash Table | O(n) | O(n) | Best general solution for large arrays and interview settings |