Contiguous Array

Medium#525subarray sum

You get an array of 0s and 1s. Find the length of the longest contiguous subarray with as many 0s as 1s. Our example: [0, 1, 1, 0, 1, 1, 1, 0, 0] — the answer is 6: [0, 1, 1, 1, 0, 0] from index 3 to 8.

525 Contiguous ArrayWalkthrough · 1×

Example: [0, 1, 1, 0, 1, 1, 1, 0, 0]. Under the numbers is the balance: +1 for every 1 and -1 for every 0 so far; it stands before the next number.

numsbalance-10+11+11-10+11+11+11-10-10
not reached yetalready seencurrentthe first time this balance was seenas many 0s as 1s

Nothing found yet: best = 0

01/36
restart · back · play · step
Speed
1function findMaxLength(nums):
2 best = 0
3 balance = 0
4 first = map {0: -1} // balance → its first index
5 for i from 0 to len(nums) - 1:
6 if nums[i] == 1: balance = balance + 1
7 else: balance = balance - 1
8 if balance in first:
9 best = max(best, i - first[balance])
10 else:
11 first[balance] = i
12 return best
state
best
0
balance
–
first
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Count a 1 as +1 and a 0 as -1. A stretch has as many 0s as 1s exactly when its sum is 0, that is, when the running balance is the same at both of its ends.
  2. The longest stretch ending at i starts right after the first index with the same balance. So first keeps only the first index of each balance and is never overwritten: at index 4 balance 1 comes back, and first[1] stays 2.
  3. first starts with {0: -1}, balance 0 before index 0, so a stretch from the very start is counted too, as [0, 1] and [0, 1, 1, 0] are here.

Complexity

Time O(n): one pass, and a map lookup or store takes O(1) on average. Memory O(n): the balance stays between -n and n, one first index for each.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.