BinarySearch 0513 Stacks

Problem statement

https://binarysearch.com/problems/Stacks/

Solution

Just keep cumulative sums for each list and then find the biggest element in intersection.

Complexity

It is O(m) for time and O(k) for space, where m is total number of elements in all lists and k is the length of the longest list.

Code

class Solution:
    def solve(self, S):
        if not S: return 0
        A = set([0] + list(accumulate(S[0])))
        for i in range(1, len(S)):
            A &= set([0] + list(accumulate(S[i])))
        return max(A)