Data Structures & Algorithms (Prefix Sum): Contiguous Array*

January 22, 2026

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.

Playground: Leetcode 526

Naive Approach - Nested Loops

Iterate over each possible subarray, maintain the running counts of 0s and 1s, and update the maximum length whenever the subarray contains equal number of 0s and 1s.

Algorithm

1. Initialize a variable: "maxLength" to track the length of the longest subarray with 
   equal number of 0 and 1.

2. Iterate over each index in "nums", treating it as the starting index of the current subarray.
    3. Initialize:
        a. A variable: "currentSubarrayZeroCount" to track the number of 0s in the current subarray.
        b. A variable: "currentSubarrayOneCount" to track the number of 1s in the current subarray.

    4. For each starting index, expand the current subarray one element at a time.
        5. If current element is 0, increment "currentSubarrayZeroCount".
        6. If current element is 1, increment "currentSubarrayOneCount".
        7. If "currentSubarrayZeroCount" is equal to "currentSubarrayOneCount", update "maxLength"
           if necessary.
    
8. Return "maxLength".

Implementation

Sample inputs
1public int findMaxLength(int[] nums) {
2
3 // 1. Initialize a variable to track the length of the longest subarray with equal number of 0 and 1.
4 int maxLength = 0;
5
6 // 2. Iterate over each index in "nums", treating it as the starting index of the current subarray.
7 for (int i = 0; i < nums.length; i++) {
8
9 /* 3. Initialize:
10 * a. A variable to track the number of 0s in the current subarray.
11 * b. A variable to track the number of 1s in the current subarray.
12 */
13 int currentSubarrayZeroCount = 0;
14 int currentSubarrayOneCount = 0;
15
16 // 4. For each starting index, expand the current subarray one element at a time.
17 for (int j = i; j < nums.length; j++) {
18
19 // 5. If current element is 0, increment the current subarray 0 Count.
20 if (nums[j] == 0) {
21 currentSubarrayZeroCount++;
22 }
23 // 6. If current element is 1, increment the current subarray 1 count.
24 if (nums[j] == 1) {
25 currentSubarrayOneCount++;
26 }
27 // 7. If count of 0s equal to the count of 1s in the current subarray, update the max length if necessary.
28 if (currentSubarrayZeroCount == currentSubarrayOneCount) {
29 maxLength = Math.max(maxLength, j - i + 1);
30 }
31
32 }
33
34 }
35
36 // 8. Return "maxLength".
37 return maxLength;
38
39}
nums
j
j
0
1
i
i
0
1
Current subarray—
nums[i..j]
i = —
j = —
zeros = —
ones = —
maxLength
—
No balanced subarray yet
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/22

Time Complexity

Each iteration involves basic validation and arithmetic operations, each taking constant time, O(1). Therefore, the time complexity primarily depends on the total number of iterations.

The outer loop runs n times. For each ith iteration, the inner loop runs (n - i) times. The total number of iterations is:

(n - 0) + (n - 1) + (n - 2) + ... + (n - (n - 1))
= n + (n - 1) + (n - 2) + ... + 2 + 1
= n * (n + 1) / 2

Since this is a quadratic expression, the overall time complexity is O(n²).

Space Complexity

We only maintain a few variables to track the count of 0s and 1s in the current subarray. Since no additional data structures are used, the overall space complexity is O(1).

Key Observations

Instead of separately counting 0s and 1s for every possible subarray, we can convert all 0s to -1.

  1. A subarray with equal number of 0s and 1s will have a sum of 0. Therefore, the problem becomes: "Find the longest contiguous subarray whose sum is 0".

key-observation-1

  1. If a subarray (i + 1 ... j) has a sum of 0, then prefixSum[j] - prefixSum[i] = 0, which means prefixSum[i] = prefixSum[j]. Therefore, while iterating, whenever a prefix sum is encountered again, the elements between its first occurrence and the current index have a sum of 0.

key-observation-2

Hence, the problem can be reduced to checking whether a prefix sum has been observed before and, if so, calculating the length of the subarray between the two occurrences.

Suitable Approach - Prefix Sum

Create a dummy array where every 0 is replaced with -1. Iterate over nums and maintain a map to store each prefix sum and its first occurrence.

While iterating, if we encounter a prefix sum that has been seen before, we have found an eligible subarray whose sum is 0, meaning the subarray contains an equal number of 0s and 1s.

Note
  1. Instead of creating a separate array, convert 0 to -1 directly while calculating the prefix sum, avoiding extra space.
  2. Add {0: -1} to the map to handle subarrays that start at index 0 and have a sum of 0.

Algorithm

1. Initialize:
    a. A variable: "maxLength" to track the length of the longest subarray with equal 
       number of 0s and 1s.
    b. A variable: "currentPrefixSum" to track the prefix sum observed so far.
    c. A map: "currentPrefixSumMap" to track the first occurrence of each distinct prefix sum.

2. Add "{0: -1}" to "currentPrefixSumMap" handle subarrays starting at index 0.

3. Iterate over each "index" in "nums":
    4. If the current element is 1, add 1 to "currentPrefixSum".
    5. If the current element is equal 0, add -1 to "currentPrefixSum".
    6. If "currentPrefixSum" exists in "currentPrefixSumMap", update "maxLength" if necessary.
    7. If "currentPrefixSum" does not exist in "currentPrefixSumMap", add "currentPrefixSum" 
       and "index" as key-value pair.

8. Return "maxLength".

Implementation

Sample inputs
1public int findMaxLength(int[] nums) {
2
3 /* 1. Initialize:
4 * a. A variable to track the length of the longest subarray with equal number of 0s and 1s.
5 * b. A variable to track the prefix sum observed so far.
6 * c. A map to track the first occurrence of each distinct prefix sum.
7 */
8 int maxLength = 0;
9 int currentPrefixSum = 0;
10 Map<Integer, Integer> currentPrefixSumMap = new HashMap<>();
11
12 // 2. Add "{0: -1}" to the current prefix sum map to handle subarrays starting at index 0.
13 currentPrefixSumMap.put(0, -1);
14
15 // 3. Iterate over each index in nums.
16 for (int i = 0; i < nums.length; i++) {
17 // 4. If the current element is 1, add 1 to the current prefix sum.
18 if (nums[i] == 1) currentPrefixSum++;
19 // 5. If the current element is equal 0, add -1 to the current prefix sum.
20 if (nums[i] == 0) currentPrefixSum += -1;
21 // 6. If the current prefix sum exists in the current prefix sum map, update maxLength if necessary.
22 if (currentPrefixSumMap.containsKey(currentPrefixSum)) {
23 maxLength = Math.max(maxLength, i - currentPrefixSumMap.get(currentPrefixSum));
24 } else {
25 /* 7. If the current prefix sum does not exist in the current prefix sum map, add the current prefix
26 * sum and the current index as key-value pair.
27 */
28 currentPrefixSumMap.put(currentPrefixSum, i);
29 }
30 }
31
32 // 8. Return maxLength.
33 return maxLength;
34
35}
nums
0
1
i
i
0
1
Balanced subarray—
nums[first + 1..i]
i = —
currentPrefixSum = —
first index = —
i − first = —
currentPrefixSumMap
Empty
maxLength
—
No balanced subarray yet
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/13

Time Complexity

Each iteration involves basic validation and arithmetic operations, each taking constant time, O(1). Therefore, the time complexity still primarily depends on the total number of iterations.

The loop runs n times. Hence, the overall time complexity is O(n).

Space Complexity

We maintain a map to store the first occurrence of each distinct prefix sum. In the worst case, when all elements in nums are 1, the map will store n distinct prefix sums. Hence, the overall space complexity is O(n).