Contiguous Array

Problem Link

525. Contiguous Array – LeetCode

Problem Statement

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

Examples

Example 1:

Input: nums = [0, 1]
Output: 2
Explanation: [0, 1] has 1 zero and 1 one → length 2.

Example 2:

Input: nums = [0, 1, 0]
Output: 2
Explanation: [0, 1] or [1, 0] → both have equal 0s and 1s.

Example 3:

Input: nums = [0,1,1,1,1,1,0,0,0]
Output: 6
Explanation: [1,1,1,0,0,0] has equal 0s and 1s (3 of each).

Constraints

• 1 <= nums.length <= 10⁵

• nums[i] is either 0 or 1

Intuition

To solve the problem in linear time, we transform the array:

• Treat 0 as -1, and 1 as +1

• The task becomes: Find the longest subarray with sum = 0

Why?

• Because an equal number of +1 and -1 implies equal number of 1 and 0

We use a HashMap to track the first occurrence of each cumulative sum (prefix sum). If we see the same prefix sum again, the subarray between the two indices has a net sum of 0.

Approach

1. Initialize sum = 0, maxLen = 0, and an empty Map<sum, index>

2. Iterate through the array:

   • Add +1 for every 1, -1 for every 0 to sum

   • If sum == 0, the subarray from start to current index is valid → update maxLen

   • If sum is already in the map:

     • A previous subarray led to this sum → current subarray from map.get(sum) + 1 to i has net sum = 0 → update maxLen

   • Else, store the current index for this sum in map

3. Return maxLen

Java Code

class Solution {
    public int findMaxLength(int[] nums) {
        int sum = 0;
        int maxLen = 0;
        Map<Integer, Integer> map = new HashMap<>();

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

            if (sum == 0) {
                maxLen = i + 1;
            } else if (map.containsKey(sum)) {
                maxLen = Math.max(maxLen, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }

        return maxLen;
    }
}

Time and Space Complexity

Dry Run

Input:

nums = [0, 1, 0]

Transformed:

[-1, +1, -1]

Key Observations

• Prefix sum is used to efficiently track the balance between 0s and 1s

• The map stores first occurrences only to maximize subarray length

• Resetting sum to zero means equal 0s and 1s from index 0 to i

Conclusion

This is a classic application of prefix sum with hashmap to convert a two-value balancing problem into a sum-equals-zero subarray problem.

You should consider this approach whenever you're asked to:

• Count equal numbers of two values

• Track balance or neutrality in an array