< Back




525. Contiguous Array

A bit of a brainfuck, tbh. We need to return the maximum length of a contiguous subarray within the
given input array that has an even number of 1s and 0s. The best way to do this is to treat 0s as a
step down, causing us to subtract 1 from the current tracker, and 1s as a step up, causing us to add
1 to the current tracker.

We can start to create our subarrays by remembering where we've been. If we see curr twice, we have
it's last seen index. We can subtract our current index from that index, providing us with the length
of the subarray that has an even number of 1s and 0s.

Because of our oscillation with curr, we know that if we see the same number twice for curr, it's
because the numbers of 1s and 0s have evened out.

The solution is as follows:


  class Solution:
      def findMaxLength(self, nums: List[int]) -> int:
          count = {0: -1}
          ans = curr = 0

          for i, num in enumerate(nums):
              curr += 1 if num == 1 else -1
              if curr in count:
                  ans = max(ans, i - count[curr])
              else:
                  count[curr] = i

          return ans


_ Time Complexity:

  O(n) - We inspect every number in the input array.

_ Space Complexity:

  O(n) - We can store at most n elements in the count dictionary.