Widest Pair of Indices With Equal Range Sum - Solution & Explanation
Problem Statement
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 either0or1.nums2[i]is either0or1.
Approach Overview
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.
Solution
We observe that for any index pair (i, j), if nums1[i] + nums1[i+1] + ... + nums1[j] = nums2[i] + nums2[i+1] + ... + nums2[j], then nums1[i] - nums2[i] + nums1[i+1] - nums2[i+1] + ... + nums1[j] - nums2[j] = 0. If we subtract the corresponding elements of array nums1 and array nums2 to get a new array nums, the problem is transformed into finding the longest subarray in nums such that the sum of the subarray is 0. This can be solved using the prefix sum + hash table method.
We define a variable s to represent the current prefix sum of nums, and use a hash table d to store the first occurrence position of each prefix sum. Initially, s = 0 and d[0] = -1.
Next, we traverse each element x in the array nums, calculate the value of s, and then check whether s exists in the hash table. If s exists in the hash table, it means that there is a subarray nums[d[s]+1,..i] such that the sum of the subarray is 0, and we update the answer to max(ans, i - d[s]). Otherwise, we add the value of s to the hash table, indicating that the first occurrence position of s is i.
After the traversal, we can get the final answer.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
1983. Widest Pair of Indices With Equal Range Sum (Leetcode Medium) • Programming Live with Larry • 191 views views
Frequently Asked Questions
Is Widest Pair of Indices With Equal Range Sum easy or hard?
Widest Pair of Indices With Equal Range Sum Python/Java solution
How to solve Widest Pair of Indices With Equal Range Sum in O(n)?
What is the best approach for Widest Pair of Indices With Equal Range Sum?
Is Widest Pair of Indices With Equal Range Sum asked at Google/Amazon/Meta?
What data structure is used in Widest Pair of Indices With Equal Range Sum?
What is the time complexity of Widest Pair of Indices With Equal Range Sum?
Ready to solve this problem?
Practice Widest Pair of Indices With Equal Range Sum with our built-in code editor and test cases.
Practice on FleetCode