Skip to content

1983. Widest Pair of Indices With Equal Range Sum πŸ”’

Description

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.length
  • 1 <= n <= 105
  • nums1[i] is either 0 or 1.
  • nums2[i] is either 0 or 1.

Solutions

Solution 1: Prefix Sum + Hash Table

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
        d = {0: -1}
        ans = s = 0
        for i, (a, b) in enumerate(zip(nums1, nums2)):
            s += a - b
            if s in d:
                ans = max(ans, i - d[s])
            else:
                d[s] = i
        return ans

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func widestPairOfIndices(nums1 []int, nums2 []int) (ans int) {
    d := map[int]int{0: -1}
    s := 0
    for i := range nums1 {
        s += nums1[i] - nums2[i]
        if j, ok := d[s]; ok {
            ans = max(ans, i-j)
        } else {
            d[s] = i
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function widestPairOfIndices(nums1: number[], nums2: number[]): number {
    const d: Map<number, number> = new Map();
    d.set(0, -1);
    const n: number = nums1.length;
    let s: number = 0;
    let ans: number = 0;
    for (let i = 0; i < n; ++i) {
        s += nums1[i] - nums2[i];
        if (d.has(s)) {
            ans = Math.max(ans, i - (d.get(s) as number));
        } else {
            d.set(s, i);
        }
    }
    return ans;
}

Comments