Problem Description

Given two integer arrays nums1 and nums2 of the same length, the task is to find the widest pair of indices (i, j) (with i <= j) such that the sum of the subarray nums1[i..j] is equal to the sum of the subarray nums2[i..j]. The "width" of a pair is defined as j - i. Your goal is to return the maximum width among all such valid pairs. If no such pair exists, return 0.

• Both arrays have the same length n (where 1 <= n <= 10^5).
• Elements can be negative, zero, or positive.
• Indices i and j must satisfy 0 <= i <= j < n.
• Find the maximum possible width among all pairs with equal subarray sums.

Thought Process

At first glance, this problem seems to require checking all possible pairs (i, j) and comparing the sums of subarrays in both arrays. However, this naive approach is highly inefficient because for each pair, calculating subarray sums would take O(n^2) time, which is not feasible for large arrays.

To optimize, we need to find a way to compare subarray sums efficiently. Notice that if sum(nums1[i..j]) == sum(nums2[i..j]), then their difference over that range is zero. This leads to the idea of using prefix sums and considering the difference between the prefix sums of nums1 and nums2. If the difference at index i-1 is equal to the difference at index j, then the subarrays from i to j must have equal sums.

Thus, instead of comparing sums directly, we can work with the difference of prefix sums and search for the widest distance between indices with the same difference value.

Solution Approach

We can solve this problem efficiently using prefix sums and a hash map. Here’s how:

1. Compute Prefix Sums: For both arrays, compute the running prefix sums. At each index, calculate the difference between the prefix sums of nums1 and nums2.
2. Use a Hash Map: Maintain a hash map that maps each observed difference to the earliest index where it appears.
3. Iterate and Track Widths: As we iterate through the arrays, whenever we see a difference value that we have seen before, it means that the subarrays between those two indices have equal sums. Compute the width and keep track of the maximum.
4. Edge Case: Initialize the hash map with 0: -1 to handle the case where the difference is zero from the start.

This approach ensures we only need a single pass through the arrays, and all lookups are constant time.

Example Walkthrough

Consider the following example:

• nums1 = [1, 2, 3, 2, 1]
• nums2 = [3, 2, 1, 2, 3]

Let's compute the prefix sums and their differences step by step:

• At index -1: diff = 0 (initialize diff_to_index[0] = -1)
• Index 0: prefix1 = 1, prefix2 = 3, diff = -2 (diff_to_index[-2] = 0)
• Index 1: prefix1 = 3, prefix2 = 5, diff = -2 (diff = -2 seen before at 0, width = 1)
• Index 2: prefix1 = 6, prefix2 = 6, diff = 0 (diff = 0 seen before at -1, width = 3)
• Index 3: prefix1 = 8, prefix2 = 8, diff = 0 (width = 4)
• Index 4: prefix1 = 9, prefix2 = 11, diff = -2 (width = 4)

The maximum width is 4, corresponding to indices (0, 4) or (0, 3).

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n^2) — For each pair of indices, we compute subarray sums.
• Space Complexity: O(1) (ignoring input size)

• Time Complexity: O(n) — We make a single pass through the arrays and do constant-time work per index.
• Space Complexity: O(n) — The hash map can store up to n unique difference values.

The optimized approach is much more efficient and suitable for large inputs.

Summary

By shifting from direct subarray sum comparison to tracking prefix sum differences, we can solve this problem efficiently. The key insight is that identical differences in prefix sums indicate equal subarray sums over a range. Using a hash map to record the first occurrence of each difference allows us to find the widest pair in linear time. This approach is both elegant and practical for large-scale data.

Code Implementation

def widestPairOfIndices(nums1, nums2):
    diff_to_index = {0: -1}
    prefix1 = prefix2 = 0
    max_width = 0
    for i in range(len(nums1)):
        prefix1 += nums1[i]
        prefix2 += nums2[i]
        diff = prefix1 - prefix2
        if diff in diff_to_index:
            width = i - diff_to_index[diff]
            if width > max_width:
                max_width = width
        else:
            diff_to_index[diff] = i
    return max_width
      

#include <vector>
#include <unordered_map>
using namespace std;

int widestPairOfIndices(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> diff_to_index;
    diff_to_index[0] = -1;
    int prefix1 = 0, prefix2 = 0, max_width = 0;
    for (int i = 0; i < nums1.size(); ++i) {
        prefix1 += nums1[i];
        prefix2 += nums2[i];
        int diff = prefix1 - prefix2;
        if (diff_to_index.count(diff)) {
            int width = i - diff_to_index[diff];
            if (width > max_width) max_width = width;
        } else {
            diff_to_index[diff] = i;
        }
    }
    return max_width;
}
      

import java.util.*;

public class Solution {
    public int widestPairOfIndices(int[] nums1, int[] nums2) {
        Map<Integer, Integer> diffToIndex = new HashMap<>();
        diffToIndex.put(0, -1);
        int prefix1 = 0, prefix2 = 0, maxWidth = 0;
        for (int i = 0; i < nums1.length; i++) {
            prefix1 += nums1[i];
            prefix2 += nums2[i];
            int diff = prefix1 - prefix2;
            if (diffToIndex.containsKey(diff)) {
                int width = i - diffToIndex.get(diff);
                if (width > maxWidth) maxWidth = width;
            } else {
                diffToIndex.put(diff, i);
            }
        }
        return maxWidth;
    }
}
      

function widestPairOfIndices(nums1, nums2) {
    const diffToIndex = new Map();
    diffToIndex.set(0, -1);
    let prefix1 = 0, prefix2 = 0, maxWidth = 0;
    for (let i = 0; i < nums1.length; i++) {
        prefix1 += nums1[i];
        prefix2 += nums2[i];
        let diff = prefix1 - prefix2;
        if (diffToIndex.has(diff)) {
            let width = i - diffToIndex.get(diff);
            if (width > maxWidth) maxWidth = width;
        } else {
            diffToIndex.set(diff, i);
        }
    }
    return maxWidth;
}