Widest Pair of Indices With Equal Range Sum

Widest Pair of Indices With Equal Range Sum - 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 the distance of the widest pair of indices. If no pair of indices meets the conditions, return 0.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,0,1,1,0], nums2 = [0,1,1,1,0]

› Output: 3

💡 Note: The widest pair is (2,4) where both arrays have sum 2 in range [2,4]. Distance = 4-2+1 = 3.

Example 2 — Equal Arrays

$ Input: nums1 = [1,1,0], nums2 = [1,1,0]

› Output: 3

💡 Note: Arrays are identical, so entire range [0,2] has equal sums. Distance = 2-0+1 = 3.

Example 3 — No Valid Range

$ Input: nums1 = [1,0], nums2 = [0,1]

› Output: 0

💡 Note: No range has equal sums: [0,0] has 1≠0, [1,1] has 0≠1, [0,1] has 1≠1.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
nums1.length == nums2.length
nums1[i], nums2[i] ∈ {0, 1}

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two binary arrays nums1 and nums2 of equal length

Find Equal Sums

Look for ranges [i,j] where sum(nums1[i:j]) = sum(nums2[i:j])

Maximum Distance

Return the largest distance j-i+1 among valid ranges

Key Takeaway

🎯 Key Insight: Transform to difference array and find longest zero-sum subarray using prefix sums

Asked in

G Google 35 f Meta 28 a Amazon 22 M Microsoft 18

The key insight is to transform this into a zero-sum subarray problem by creating a difference array where diff[i] = nums1[i] - nums2[i]. Equal range sums mean their difference is zero. Best approach uses prefix sum with hash map to find the longest zero-sum subarray efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n³)	O(1)	Check every possible pair of indices (i,j) and compare range sums
Prefix Sum with Hash Map	O(n)	O(n)	Transform to difference array, then find longest zero-sum subarray using prefix sums

Brute Force - Check All Pairs — Algorithm Steps

Iterate through all pairs (i,j) where i <= j
Calculate sum of nums1[i...j] and nums2[i...j]
If sums are equal, update maximum distance
Return the maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try All Pairs

Check every (i,j) where i ≤ j

Calculate Sums

Sum both arrays in range [i,j]

Track Maximum

Keep largest distance where sums match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int* nums2, int n) {
    int maxDistance = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum1 = 0, sum2 = 0;
            for (int k = i; k <= j; k++) {
                sum1 += nums1[k];
                sum2 += nums2[k];
            }
            if (sum1 == sum2) {
                int distance = j - i + 1;
                if (distance > maxDistance) {
                    maxDistance = distance;
                }
            }
        }
    }
    
    return maxDistance;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums1[1000], nums2[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums1[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    int idx = 0;
    while (token != NULL) {
        nums2[idx++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, nums2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops for i,j pairs (O(n²)) and sum calculation for each pair (O(n))

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for tracking indices and sums

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler