Contiguous Array Solutions & Complexity

1. Define the problem

Contiguous Array

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1 . Treat each 0 as -1 and each 1 as +1, then track a running sum. A subarray is balanced exactly when the running sum returns to a value it has hit before — the distance between those two points is its length.

Constraints

1 ≤ nums.length ≤ 10⁵
nums_i is either 0 or 1

Example

Inputnums = [0, 1]

Output2

Explanation The whole array [0, 1] has one 0 and one 1, so its length, 2, is the answer.

2. Visualize the solution

Track the first index each running sum was seen

Statusinit

nums[0]=0 → sum=-1. Not seen before, record firstIndex[-1]=0.

What happens in this step

firstIndex = {0: -1}   sum = 0

i=0: nums[0]=0 → sum += -1 → sum = -1
  firstIndex has no key -1 → record firstIndex[-1] = 0
  firstIndex = {0: -1, -1: 0}

Step 1 of 2

Steps to visualize

Start a hashmap with {0: -1} — a running sum of 0 was "seen" before the array begins.
Walk the array, adding +1 for a 1 and -1 for a 0 onto a running sum.
If this running sum has been seen before, the gap since its first occurrence is a balanced subarray — track the longest one.
If it has not been seen before, record this index as its first occurrence.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track the first index each running sum was seen

Statusinit

nums[0]=0 → sum=-1. Not seen before, record firstIndex[-1]=0.

What happens in this step

firstIndex = {0: -1}   sum = 0

i=0: nums[0]=0 → sum += -1 → sum = -1
  firstIndex has no key -1 → record firstIndex[-1] = 0
  firstIndex = {0: -1, -1: 0}

Step 1 of 2

4. Solution

Solution

solution.tsTypeScript

function findMaxLength(nums) {
  const firstIndex = new Map([[0, -1]]);
  let sum = 0;
  let maxLen = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 1 ? 1 : -1;

    if (firstIndex.has(sum)) {
      maxLen = Math.max(maxLen, i - firstIndex.get(sum));
    } else {
      firstIndex.set(sum, i);
    }
  }

  return maxLen;
}

Time: O(n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [0, 1]`	`2`	example from the docstring
`nums = [0, 1, 0]`	`2`	balance found in a two-element window, not the whole array
`nums = [0, 0, 0]`	`0`	no subarray is ever balanced
`nums = [1, 1, 0, 0]`	`4`	the entire array is the longest balanced subarray
`nums = [0]`	`0`	smallest valid input, a single element can never balance
`nums = [1, 0, 1, 0, 1, 0]`	`6`	alternating values where the full array is balanced

Contiguous Array