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

Topic	Description
Prefix Sum	Precompute running totals so the sum of any range can be answered instantly instead of adding it up every time.
Running Sum of 1d Array	Return a new array where each element is the sum of all elements up to that point.
Find Pivot Index	Find the index where the sum of numbers to the left equals the sum of numbers to the right.
Subarray Sum Equals K	Count how many contiguous subarrays add up to a target value.
Product of Array Except Self	Return an array where each element is the product of every other element, without using division.
Range Sum Query 2D - Immutable	Answer repeated queries for the sum of values inside a rectangle of a fixed grid.