Widest pair of indices with equal range sum

Array Hash Table Prefix Sum

54.0% acceptance

Mar 31, 2026

104

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn widest_pair_of_indices(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let n = nums1.len();
    let mut map: HashMap<i32, usize> = HashMap::new();
    map.insert(0, 0);
    let mut diff = 0i32;
    let mut max_width = 0;
    for i in 0..n {
      diff += nums1[i] - nums2[i];
      if let Some(&first) = map.get(&diff) {
        max_width = max_width.max(i + 1 - first);
      } else {
        map.insert(diff, i + 1);
      }
    }
    max_width as i32
  }
}