Problem

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 _thedistance of the widest pair of indices. If no pair of indices meets the conditions, return _0.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7

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:

1
2
3
4

Input: nums1 = [0], nums2 = [1]
Output: 0
Explanation:
There are no pairs of indices that meet the requirements.

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • nums1[i] is either 0 or 1.
  • nums2[i] is either 0 or 1.

Solution

Method 1 – Prefix Sum and Hash Map

Intuition

If the sum of nums1[i..j] equals the sum of nums2[i..j], then the difference of prefix sums up to j and i-1 is the same for both arrays. We can use a hash map to record the first occurrence of each difference between prefix sums, and maximize the distance for each repeated difference.

Approach

  1. Compute prefix sums for nums1 and nums2.
  2. For each index, compute the difference between prefix sums up to that index.
  3. Use a hash map to store the first index where each difference occurs.
  4. For each index, if the difference has been seen before, update the answer with the distance.
  5. Return the maximum distance found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int widestPairOfIndices(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> first;
        int n = nums1.size(), ans = 0, diff = 0;
        first[0] = -1;
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n; ++i) {
            s1 += nums1[i];
            s2 += nums2[i];
            diff = s1 - s2;
            if (first.count(diff)) ans = max(ans, i - first[diff]);
            else first[diff] = i;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func widestPairOfIndices(nums1, nums2 []int) int {
    first := map[int]int{0: -1}
    ans, s1, s2 := 0, 0, 0
    for i := 0; i < len(nums1); i++ {
        s1 += nums1[i]
        s2 += nums2[i]
        diff := s1 - s2
        if idx, ok := first[diff]; ok {
            if i-idx > ans {
                ans = i - idx
            }
        } else {
            first[diff] = i
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int widestPairOfIndices(int[] nums1, int[] nums2) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int ans = 0, s1 = 0, s2 = 0;
        for (int i = 0; i < nums1.length; i++) {
            s1 += nums1[i];
            s2 += nums2[i];
            int diff = s1 - s2;
            if (first.containsKey(diff)) {
                ans = Math.max(ans, i - first.get(diff));
            } else {
                first.put(diff, i);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun widestPairOfIndices(nums1: IntArray, nums2: IntArray): Int {
        val first = mutableMapOf(0 to -1)
        var ans = 0
        var s1 = 0
        var s2 = 0
        for (i in nums1.indices) {
            s1 += nums1[i]
            s2 += nums2[i]
            val diff = s1 - s2
            if (diff in first) {
                ans = maxOf(ans, i - first[diff]!!)
            } else {
                first[diff] = i
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from typing import List
class Solution:
    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
        first = {0: -1}
        ans = s1 = s2 = 0
        for i, (a, b) in enumerate(zip(nums1, nums2)):
            s1 += a
            s2 += b
            diff = s1 - s2
            if diff in first:
                ans = max(ans, i - first[diff])
            else:
                first[diff] = i
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::collections::HashMap;
impl Solution {
    pub fn widest_pair_of_indices(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut first = HashMap::new();
        first.insert(0, -1);
        let (mut ans, mut s1, mut s2) = (0, 0, 0);
        for (i, (&a, &b)) in nums1.iter().zip(nums2.iter()).enumerate() {
            s1 += a;
            s2 += b;
            let diff = s1 - s2;
            if let Some(&idx) = first.get(&diff) {
                ans = ans.max(i as i32 - idx);
            } else {
                first.insert(diff, i as i32);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    widestPairOfIndices(nums1: number[], nums2: number[]): number {
        const first: Record<number, number> = {0: -1};
        let ans = 0, s1 = 0, s2 = 0;
        for (let i = 0; i < nums1.length; i++) {
            s1 += nums1[i];
            s2 += nums2[i];
            const diff = s1 - s2;
            if (diff in first) {
                ans = Math.max(ans, i - first[diff]);
            } else {
                first[diff] = i;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We traverse the arrays once, and hash map operations are O(1) on average.
  • 🧺 Space complexity: O(n) — For the hash map storing first occurrences of differences.