Python 5 lines O(n) solution

  • 0

    Think of 1 as push, 0 as pop, the whole stack goes up and down.
    Keep tracking the height of the stack, find which height reoccurs after longest interval.

    class Solution(object):
        def findMaxLength(self, nums):
            :type nums: List[int]
            :rtype: int
            # longest is a dict, key is the height of the stack, first element of value is its first index, second element is the reoccur interval
            sums, longest = 0, {0:[-1,0]}
            for idx, i in enumerate(nums):
                # increase height when meet 1, decrease when meet 0
                sums += (i or -1)
                # update the dict
                longest[sums] = [longest[sums][0] if sums in longest else idx, idx - (longest[sums][0] if sums in longest else idx) ]
            return max(map(lambda x:x[1], longest.values()))

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.