Find Longest Subarray with Equal Zeros and Ones

Title: Find Longest Subarray with Equal Zeros and Ones

In this guide, you’ll learn how to find the length of the longest contiguous subarray in a binary array that contains an equal number of 0s and 1s. This is a classic array and hashing problem that shows up frequently in coding interviews, because the naive approach is easy to write but too slow, while the optimal approach relies on a clever prefix-sum trick.

We’ll walk through the brute-force intuition, build up to the prefix-sum-plus-hashmap approach that runs in O(n) time, trace the algorithm step by step on a sample input, and cover the common mistakes, edge cases, and interview follow-up questions you should be ready for.

Understanding the Problem

Given an array nums containing only the values 0 and 1, you need to find the length of the longest contiguous subarray that has the same number of 0s as 1s. For example, in [0, 1, 0, 0, 1, 1, 0], the subarray [0, 1, 0, 0, 1, 1] (indices 0 through 5) has three 0s and three 1s, giving a length of 6.

The brute-force approach checks every subarray, counts its zeros and ones, and keeps the longest one that balances; this costs O(n^2) time since there are O(n) subarrays and each count takes O(n). The optimal approach reframes the problem using prefix sums so it can be solved in a single pass.

Approach

1. Create a HashMap<Integer, Integer> named firstIndexOfSum that stores the first index at which each running sum value occurs.
2. Seed the map with firstIndexOfSum.put(0, -1) so a subarray that is balanced starting from index 0 is detected correctly.
3. Initialize sum = 0 and maxLen = 0, then iterate over the array with index i.
4. At each index, add 1 to sum if nums[i] is 1, or subtract 1 if it is 0.
5. If sum already exists as a key in firstIndexOfSum, the subarray between the stored index and i is balanced; update maxLen with i - previousIndex when it is larger.
6. If sum is new, store the current index as its first occurrence in the map.
7. After the loop finishes, maxLen holds the length of the longest balanced subarray.

Java Program

import java.util.HashMap;
import java.util.Map;

public class LongestSubarrayEqualZerosOnes {

    public static int findMaxLength(int[] nums) {
        Map<Integer, Integer> firstIndexOfSum = new HashMap<>();
        firstIndexOfSum.put(0, -1);
        int sum = 0;
        int maxLen = 0;

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

            if (firstIndexOfSum.containsKey(sum)) {
                int previousIndex = firstIndexOfSum.get(sum);
                maxLen = Math.max(maxLen, i - previousIndex);
            } else {
                firstIndexOfSum.put(sum, i);
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 0, 1, 1, 0};
        int result = findMaxLength(nums);
        System.out.println("Length of the longest balanced subarray: " + result);
    }
}

Explanation of the Program

The method findMaxLength implements the prefix-sum technique described above.

• firstIndexOfSum.put(0, -1) handles the case where a balanced subarray starts right at index 0, since conceptually the sum was 0 before any element was processed.
• sum += (nums[i] == 1) ? 1 : -1; converts the binary value into a signed contribution, so that a balanced run of zeros and ones cancels back to a previously seen sum.
• firstIndexOfSum.containsKey(sum) checks whether this exact running total occurred before; if it did, every element between the two occurrences must net to zero, which means equal zeros and ones.
• The map only ever stores the first index for each sum, via the else branch, so later matches against that sum always produce the longest possible window.

Step-by-Step Trace

For nums = [1, 0, 1, 1, 0, 0], the algorithm should return 6, since the whole array balances to three 1s and three 0s.

At the end of each iteration, maxLen holds the length of the longest balanced subarray found so far, and firstIndexOfSum maps every distinct running sum seen so far to the earliest index at which it occurred.

Examples

Example 1: Answer Shorter Than the Full Array

Not every array is balanced overall, so the longest balanced subarray sometimes excludes a leading stretch of elements.

int[] nums = {1, 1, 1, 0, 0, 1, 0};
int result = LongestSubarrayEqualZerosOnes.findMaxLength(nums);
System.out.println(result);
// Output: 6 (the balanced window is nums[1..6])

Example 2: Trailing Unbalanced Element

An extra element at the end of the array can also be excluded from the answer if including it would break the balance.

int[] nums = {0, 0, 0, 1, 1, 1, 1};
int result = LongestSubarrayEqualZerosOnes.findMaxLength(nums);
System.out.println(result);
// Output: 6 (the balanced window is nums[0..5]; the final 1 is excluded)

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this prefix-sum approach.

• Forgetting to seed the map with (0, -1) – without this entry, a balanced subarray that starts at index 0 is missed, so the reported maxLen is shorter than the true answer. Always call firstIndexOfSum.put(0, -1) before the loop begins.
• Summing raw 0/1 values instead of signed contributions – using the literal value of nums[i] as the increment loses the information needed to detect balance, so the same sum almost never repeats. Map 0 to -1 and 1 to +1 before adding to the running sum.
• Overwriting the first-seen index for a sum – calling put on every iteration instead of only inside the else branch replaces the earliest occurrence with a later one, shrinking the window that gets measured. Only insert into the map when the sum is genuinely new.
• Reaching for Kadane’s algorithm – this problem asks for a subarray with sum equal to zero, not the subarray with the maximum sum, so a maximum-subarray-sum solution returns the wrong answer entirely. Use the prefix-sum-to-index hashmap technique instead.

Edge Cases to Test

Walk through these input shapes before you consider the solution complete.

• Empty array
• Single-element array
• All zeros
• All ones
• Array already balanced across its full length
• Leading or trailing elements that must be excluded from the answer
• Multiple subarrays tied for the longest balanced length
• Null array reference

Additional Considerations

The algorithm runs in O(n) time, since it makes a single pass over the array and each hashmap lookup and insert is O(1) on average.

Space usage is O(n) in the worst case, because the hashmap can end up storing one entry for every distinct running sum, and there are at most n + 1 possible running sums for an array of length n.

A sliding window will not work directly on this problem, because adding one element at a time can both increase and decrease the zero-versus-one balance; there is no single direction in which shrinking or growing the window always restores balance. That is exactly why the prefix-sum hashmap technique is needed instead of a two-pointer scan.

Interview Follow-up Questions

Once you can explain the base solution, expect an interviewer to probe these variations.

• What if the array contains two distinct values other than 0 and 1? – map one value to +1 and the other to -1; the prefix-sum technique works unchanged on any array with exactly two distinct symbols.
• What if you need the longest subarray with equal counts of two specific values out of several possible values? – track only the running difference between counts of the two target values, treating every other value as a no-op that leaves the sum unchanged.
• What if the input is a stream and you need the answer so far after every new element? – keep the same hashmap and running sum across calls instead of rebuilding them, so each new element updates maxLen in O(1) amortized time.
• What if the array is too large to fit in memory? – the map’s size is bounded by the number of distinct running sums, which is at most the array length, so a true streaming solution would need to bound this with an approximate or windowed sketch and accept some loss of exactness.
• What if you are only allowed O(1) extra space? – explain that this is not achievable in general for this exact problem, because recalling the earliest index per prefix sum fundamentally requires extra memory; the trade-off is falling back to an O(n^2) brute-force scan if O(1) space is a hard constraint.

Conclusion

The longest-balanced-subarray problem is a great example of how reframing a counting question as a prefix-sum question turns an O(n^2) brute force into a single O(n) pass. The key insight, mapping 0 to -1 and watching for a repeated running sum, shows up again and again in subarray problems that ask about sums, averages, or balance.

Try adapting the code above to count how many balanced subarrays exist in total, rather than just the longest one, as good practice for extending the same hashmap idea. You can find more array-based algorithms and interview-style Java programs in the Arrays category on this site.