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.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.
Java
C++
Go
TypeScript
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,212 views views
Watch 9 more video solutions →Practice Widest Pair of Indices With Equal Range Sum with our built-in code editor and test cases.
Practice on FleetCode