We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Widest Pair of Indices With Equal Range Sum

Number: 519

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given two 0-indexed binary arrays, nums1 and nums2, find the widest pair of indices (i, j) (with i <= j) such that the sum of elements in nums1 between i and j equals the sum in nums2 over the same range. The "widest" pair is defined as the pair with the largest distance (j - i + 1). Return the distance of the widest pair, or 0 if no such pair exists.

Key Insights

  • The problem can be reduced to finding a subarray where the difference between the prefix sums of nums1 and nums2 remains constant.
  • Define a running difference: diff = (prefix sum of nums1) - (prefix sum of nums2).
  • A subarray (i, j) has equal sums if diff[j] == diff[i-1] (or diff[j] == 0 for subarrays starting at index 0).
  • Use a hash table (or dictionary) to record the earliest index each diff value is encountered.
  • Compute the maximum width (j - i) by checking every index against its earliest occurrence.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

The solution uses a prefix sum approach on both arrays combined into a running diff. We maintain a dictionary to store the first occurrence of each diff value. As we iterate over the indices, whenever we see that the same diff has been encountered before, it implies that the subarray between that previous index+1 and the current index has equal range sums. We then update the maximum distance accordingly. Note the trick of initializing the dictionary with diff 0 at index -1 to handle subarrays starting from index 0.

Code Solutions

# Python solution
def widestPairEqualRangeSum(nums1, nums2):
    # Dictionary to store the first index where a diff was seen.
    diff_index_map = {0: -1}
    max_width = 0
    diff = 0
    
    # Iterate through both arrays together.
    for i in range(len(nums1)):
        # Update running diff
        diff += nums1[i] - nums2[i]
        
        # If the diff was seen before, compute subarray length.
        if diff in diff_index_map:
            # Length is current index minus the earlier index
            max_width = max(max_width, i - diff_index_map[diff])
        else:
            # Record first occurrence of this diff.
            diff_index_map[diff] = i
    return max_width

# Example usage:
print(widestPairEqualRangeSum([1,1,0,1], [0,1,1,0])) # Output: 3
← Back to All Questions