Leetcode 1983 Widest Pair of Indices With Equal Range Sum

Problem statement

https://leetcode.com/problems/widest-pair-of-indices-with-equal-range-sum/

Solution

What is actually asked is to find the biggest window of array A with sum equal to 0, where A = A1 - A2 elementwise. For this we can use cumulative sums idea: for each cumulative sum keep all indexes we have it and then calculate the biggest distance.

Complexity

Time complexity is O(n), space complexity is also O(n).

Code

class Solution:
    def widestPairOfIndices(self, A1, A2):
        A = (x - y for x, y in zip(A1, A2))
        acc = [0] + list(accumulate(A))
        d = defaultdict(list)
        
        for i, val in enumerate(acc):
            d[val].append(i)
            
        return max(max(t) - min(t) for t in d.values())