Contiguous Array

LeetCode 525 | Difficulty: Medium

Medium

Problem Description

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

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Example 3:

Input: nums = [0,1,1,1,1,1,0,0,0]
Output: 6
Explanation: [1,1,1,0,0,0] is the longest contiguous subarray with equal number of 0 and 1.

Constraints:

- `1 <= nums.length <= 10^5`

- `nums[i]` is either `0` or `1`.

Topics: Array, Hash Table, Prefix Sum

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 362 ms)

Metric	Value
Runtime	362 ms
Memory	44.8 MB
Date	2022-01-22

Solution

public class Solution {
    public int FindMaxLength(int[] nums) {
        int n = nums.Length;
    Dictionary<int, int> map = new Dictionary<int, int>();
    int count = 0;
    int max = 0;
    map.Add(0, -1);
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == 0) { count--;} else {count++;}
        if(map.ContainsKey(count))
        {
            max = Math.Max(max, i-map[count]);
        }
        else
        {
            map.Add(count, i);
        }
    }
    
    return max;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.