Longest Subarray With Equal Number of 0s and 1s

Given a binary array of n elements, where every element is either 0 or 1, find the length of the longest contiguous subarray that contains an equal number of 0s and 1s. If no such subarray exists, print 0.

Input: The first line contains a single integer n. The second line contains n space-separated values, each 0 or 1. Output: A single integer: the length of the longest subarray with an equal count of 0s and 1s, or 0 if none exists.

1 <= n <= 10^5. arr[i] is either 0 or 1.

This is a specific instance of 'Longest Subarray With Sum K' with K fixed at exactly 0 - always look for opportunities to reduce a new-looking problem to one you've already mastered, rather than treating it as something entirely new.

Find the length of the longest contiguous subarray of 0s and 1s that contains an equal count of each. Brute force: Check every possible contiguous subarray directly, counting 0s and 1s in each and comparing - this costs O(n²), too slow for large arrays. Optimised: The '0 to -1' remapping trick transforms 'equal count of 0s and 1s' into 'sum equals 0', which is exactly the same prefix-sum-plus-hash-map technique used for 'longest subarray with sum K' (with K fixed at 0) - recognizing this reduction turns a seemingly different-looking problem into one you already know how to solve efficiently.

1. Replace every 0 with -1 conceptually - the problem now becomes 'find the longest subarray whose sum is exactly 0'. 2. Track the running sum as you scan, using a hash map to remember the FIRST index at which each running sum value occurred. 3. Whenever the CURRENT running sum has been seen BEFORE, the subarray between those two occurrences has a sum of 0 (equal 0s and 1s) - track the longest such span.

Time: O(n) - one single pass, with O(1) average-case hash map lookups. Space: O(n), for the hash map of running sums to their first occurrence index.

When n = 1, the answer is always 0, since a single element cannot balance. If the entire array is already balanced, the answer is n itself.

Be ready to state the '0 to -1 remapping' trick explicitly and immediately - recognizing this transformation is the entire key insight, converting an unfamiliar-looking counting problem into the well-known 'longest zero-sum subarray' pattern.