How hard is LeetCode 1983. Widest Pair of Indices With Equal Range Sum?

LeetCode 1983. Widest Pair of Indices With Equal Range Sum is rated Medium on LeetCode.

What is the time complexity of LeetCode 1983. Widest Pair of Indices With Equal Range Sum?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1983. Widest Pair of Indices With Equal Range Sum?

The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.

What topics does LeetCode 1983. Widest Pair of Indices With Equal Range Sum cover?

LeetCode 1983. Widest Pair of Indices With Equal Range Sum is tagged Array, Hash Table and Prefix Sum on LeetCode.

Is LeetCode 1983. Widest Pair of Indices With Equal Range Sum a premium problem?

Yes. LeetCode 1983. Widest Pair of Indices With Equal Range Sum is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Widest Pair of Indices With Equal Range Sum — LeetCode 1983 Python Solution

MediumLeetCode PremiumArrayHash TablePrefix Sum

Problem: #1983
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

The 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] + ...

Example

Input: nums1 = [1,1,0,1], nums2 = [0,1,1,0]
Output: 3
Explanation: If i = 1 and j = 3:

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the array nums auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1983. Widest Pair of Indices With Equal Range Sum is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1983. Widest Pair of Indices With Equal Range Sum?: LeetCode 1983. Widest Pair of Indices With Equal Range Sum is rated Medium on LeetCode.
What is the time complexity of LeetCode 1983. Widest Pair of Indices With Equal Range Sum?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1983. Widest Pair of Indices With Equal Range Sum?: The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.
What topics does LeetCode 1983. Widest Pair of Indices With Equal Range Sum cover?: LeetCode 1983. Widest Pair of Indices With Equal Range Sum is tagged Array, Hash Table and Prefix Sum on LeetCode.
Is LeetCode 1983. Widest Pair of Indices With Equal Range Sum a premium problem?: Yes. LeetCode 1983. Widest Pair of Indices With Equal Range Sum is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.