#525 Contiguous Array

Mediumsolve on LeetCode ↗

frequently reported atMeta Amazon Google

the problem

In plain words

Given a binary array, return the length of the longest contiguous subarray with an equal number of 0s and 1s.

in nums = [0,1]

out 2

in nums = [0,1,0]

out 2

in nums = [0,1,1,1,1,1,0,0,0]

out 6

1 ≤ n ≤ 10⁵
nums[i] is 0 or 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternPrefix sum + HashMap

Count a 1 as +1 and a 0 as −1. Equal counts means sum 0, which means the same running balance at both ends. Keep the first index of each balance to get the longest span.

solutions

From brute force to optimal

For each start, extend the end while tracking balance; record lengths where balance is 0.

For each start: balance = 0.
For each end: balance ±= 1; if 0, update best.

timeO(n²)

All (start, end) pairs.

spaceO(1)

A counter.

javajava.util.*

1class Solution {2    public int findMaxLength(int[] nums) {3        int best = 0;4        for (int start = 0; start < nums.length; start++) {5            int balance = 0; // +1 for a 1, -1 for a 06            for (int end = start; end < nums.length; end++) {7                balance += nums[end] == 1 ? 1 : -1;8                if (balance == 0) best = Math.max(best, end - start + 1);9            }10        }11        return best;12    }13}

Same balance at i and j ⇒ nums(j..i] is balanced. Store each balance's first index only.

firstSeen = {0: −1}.
balance += (x == 1 ? 1 : −1).
Seen before → best = max(best, i − first). Else record i.

timeO(n)

One pass, O(1)-average map operations.

spaceO(n)

Up to 2n + 1 balances, but at most n + 1 are ever stored.

javajava.util.*

1class Solution {2    public int findMaxLength(int[] nums) {3        Map<Integer, Integer> firstSeen = new HashMap<>(); // balance → earliest index4        firstSeen.put(0, -1); // balance 0 "happens" before the array starts5        int balance = 0, best = 0;6        for (int i = 0; i < nums.length; i++) {7            balance += nums[i] == 1 ? 1 : -1;8            Integer first = firstSeen.get(balance);9            if (first != null) best = Math.max(best, i - first); // same balance → equal 0s and 1s between10            else firstSeen.put(balance, i);                     // keep only the EARLIEST index11        }12        return best;13    }14}

Balance is always in −n..n, so an array of size 2n + 1 (shifted by n) is a perfect hash table.

Fill with a "never seen" marker; firstSeen[n] = −1.
Same loop as the map version, indexing balance + n.

timeO(n)

One pass; array access is O(1) with no hashing or boxing.

spaceO(n)

2n + 1 ints.

javajava.util.*

1class Solution {2    public int findMaxLength(int[] nums) {3        int n = nums.length;4        int[] firstSeen = new int[2 * n + 1]; // balance ranges over -n..n → shift by n5        Arrays.fill(firstSeen, -2);           // -2 = "never seen"6        firstSeen[n] = -1;                    // balance 0 at index -17        int balance = 0, best = 0;8        for (int i = 0; i < n; i++) {9            balance += nums[i] == 1 ? 1 : -1;10            int slot = balance + n;11            if (firstSeen[slot] != -2) best = Math.max(best, i - firstSeen[slot]);12            else firstSeen[slot] = i;13        }14        return best;15    }16}

in the room

How to say it in the interview

talk track

Reframe first: "0 → −1 turns this into the longest subarray with sum 0."
Stress first index, because overwriting it would shorten the answer.

traps

Updating the stored index on every repeat (you want the earliest).
Forgetting {0: −1}: a balanced prefix starting at index 0 is missed.

what they ask next

Follow-ups

Count the balanced subarrays instead of finding the longest?

Map balance → how many times it was seen (start with {0: 1}). At each i, add count[balance] to the answer, then increment it. O(n) time, O(n) space.

Why not a sliding window?

Growing or shrinking the window doesn't move the balance in one direction, so you can't tell which side to move. Prefix balances with a map are the tool here.

before you submit

Edge cases to test

Only 1s, or only 0s → 0.
The whole array is balanced → n.
A single element → 0.

practise next