Problem Statement

You are given a binary array nums (only contains 0s and 1s).
Your task is to find the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example

Input:

nums = [0,1,0]

Output:

2

Explanation:

The subarray [0,1] has equal 0s and 1s → length 2.

Another subarray [1,0] also satisfies → length 2.

Approach: Using HashMap and Prefix Sum

Core Idea:

• Treat 0 as -1, and keep a cumulative sum (count) while traversing the array.
• If the same count appears again at a later index, the elements between those two indexes have equal number of 0s and 1s.
• Use a HashMap to store the first index where each count occurred.

Why it works:

• If two positions have the same count, then the subarray between them has a net difference of zero between 0s and 1s (i.e., equal number of each).

Java Code

import java.util.HashMap;

class Solution {
    public int findMaxLength(int[] nums) {
        // Map to store (count value) -> first index it occurred
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // Initialize count 0 at index -1

        int maxLength = 0;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            // Convert 0 to -1
            count += (nums[i] == 0) ? -1 : 1;

            if (map.containsKey(count)) {
                // Subarray from map.get(count)+1 to i has equal 0s and 1s
                maxLength = Math.max(maxLength, i - map.get(count));
            } else {
                // First time this count has occurred
                map.put(count, i);
            }
        }

        return maxLength;
    }
}

Explanation Step-by-Step

• Convert 0 to -1 to make it easier to balance the array.
• Keep a running count while traversing:
  • count += -1 for 0
  • count += 1 for 1
• Store the first time each count appears in a HashMap.
• If the same count is seen again, that means a balanced subarray has occurred between those indices.
• Keep track of the maximum length found.

Dry Run

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

Index	Value	Count	Map	maxLength
0	0	-1	{0:-1, -1:0}	0
1	1	0	found 0 again → i – (-1) = 2	2
2	0	-1	found -1 again → i – 0 = 2	2
3	1	0	found 0 again → i – (-1) = 4	4
4	1	1	{0:-1, -1:0, 1:4}	4

Time and Space Complexity

• Time Complexity: O(n) — One pass through the array.
• Space Complexity: O(n) — To store counts in the HashMap.