Balanced Subarray Extraction — Problem Statement & Solution Guide
Problem Description
You are tasked with analyzing a digital signal stream represented as a binary array. The goal is to determine the maximum length of a contiguous subarray where the number of 0s is exactly equal to the number of 1s. This metric is critical for identifying balanced intervals in data transmission logs, where equal distribution of signal states indicates a stable segment.
Given an array nums consisting of integers 0 and 1, return the length of the longest contiguous subarray that contains an equal count of 0s and 1s. If no such subarray exists, return 0.
The solution must efficiently process the stream to find the optimal window without resorting to brute-force enumeration of all possible subarrays.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Subarray Extraction"
WHY DOES IT MATTER?
The prefix‑sum + hash‑map pattern transforms a global property (equal counts) into a local lookup, turning an O(n²) brute force into a single pass. It is essential because many interview problems hide a cumulative invariant that can be exploited with a map.
OPTIMIZATION CHALLENGE
Recognizing that the equality of 0s and 1s depends only on their difference allows us to replace nested loops with a hash map lookup, reducing time from quadratic to linear and space from constant to linear.
REAL-WORLD CONNECTION
In distributed systems, balancing load across servers often requires monitoring the difference between incoming and processed requests. By tracking a running difference and noting when it returns to a previous value, operators can identify periods of perfect load balance—exactly the same logic as finding a balanced subarray.
Always ask: "What cumulative metric changes when I add an element, and can I store its first occurrence?" This question immediately suggests a prefix‑sum + map solution and saves time during interviews.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem of finding the longest contiguous subarray with an equal number of 0s and 1s can be reframed as a prefix-sum problem. By treating 0 as -1 and 1 as +1, the cumulative sum at any index represents the net balance of 1s over 0s up to that point. If two indices share the same cumulative sum, the subarray between them must contain an equal number of 0s and 1s, because the net difference cancels out.
A naive approach would examine every possible subarray, recomputing the counts of 0s and 1s for each, leading to an O(n²) time complexity and O(1) space. This quickly becomes infeasible for large arrays (e.g., n > 10⁵). The optimal paradigm leverages a hash map that records the earliest index at which each cumulative sum occurs. As we iterate through the array once, we update the cumulative sum and look up whether this sum has been seen before. If it has, the distance between the current index and the stored index is a candidate for the maximum length. This reduces the problem to a single linear scan with O(n) time and O(n) auxiliary space.
The key insight is that the equality of 0s and 1s depends solely on the difference between their counts, not on their absolute values. By converting the problem into a difference tracking exercise, we avoid nested loops and achieve optimal performance. This technique is a classic example of the “prefix sum + hash map” pattern, which appears in many array and string problems where subarray or substring properties depend on cumulative metrics.
Interview Questions on This Problem
Q1How would you adapt this algorithm if the array contained arbitrary integers instead of just 0s and 1s, and you needed the longest subarray with a sum of zero?
Treat each integer as itself and compute a running total. Store the first occurrence of each cumulative sum in a hash map. Whenever the same sum reappears, the subarray between the two indices sums to zero. This is essentially the same pattern, but the mapping is from sum to index rather than from difference of 0s and 1s.
Q2Suppose you are asked to find the longest subarray where the number of 1s is at least twice the number of 0s. What data structure would you use and why?
You can transform the condition into a prefix sum inequality: 2*ones - zeros >= 0. By maintaining a prefix sum of (2*currentOneCount - currentZeroCount) and using a monotonic stack or balanced BST to query the earliest index where the prefix sum is less than or equal to the current value, you can achieve O(n log n) time. A hash map alone is insufficient because you need to compare ranges of sums, not exact matches.
Q3In a streaming scenario where you cannot store the entire array, how would you still compute the longest balanced subarray?
You would maintain the same hash map of cumulative sums to earliest indices, but you would also keep a sliding window of indices that are still relevant. Since the longest subarray can only end at the current position, you can discard indices that are too far back to form a longer subarray than already found. This allows you to process the stream in O(1) additional space per element, though you still need O(n) space for the map unless you bound the window size.
Examples
Input
nums = [0, 1, 0, 0, 1, 1, 0]
Output
6
Explanation: The subarray [1, 0, 0, 1, 1, 0] (indices 1 to 6) contains three 0s and three 1s. Its length is 6. No longer balanced subarray exists in the input.
Input
nums = [1, 1, 1, 0, 0, 0]
Output
6
Explanation: The entire array [1, 1, 1, 0, 0, 0] contains three 1s and three 0s. The length is 6, which is the maximum possible for this input.
Input
nums = [0, 0, 0, 0]
Output
0
Explanation: The array contains only 0s. There are no 1s to balance the count. Therefore, no valid subarray exists, and the result is 0.
Input
nums = [1, 0, 1, 0, 1, 0, 1, 0]
Output
8
Explanation: The entire array has four 1s and four 0s. The length is 8, which is the maximum balanced segment.
Constraints
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1
Optimal Approach & Strategy
Use a prefix sum where 0 becomes -1 and 1 stays +1. Store the earliest index of each sum in a hash map. While scanning, update the sum and if it has been seen, compute the subarray length. This yields O(n) time and O(n) space.
Brute Force Approach
Check every possible subarray, count zeros and ones for each, and keep the maximum length. This takes O(n²) time and O(1) space.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function(nums) {
const prefixMap = new Map();
prefixMap.set(0, -1);
let balance = 0;
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
balance += (nums[i] === 1) ? 1 : -1;
if (prefixMap.has(balance)) {
maxLength = Math.max(maxLength, i - prefixMap.get(balance));
} else {
prefixMap.set(balance, i);
}
}
return maxLength;
};class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> prefixMap;
prefixMap[0] = -1;
int balance = 0;
int maxLength = 0;
for (int i = 0; i < nums.size(); ++i) {
balance += (nums[i] == 1) ? 1 : -1;
if (prefixMap.find(balance) != prefixMap.end()) {
maxLength = max(maxLength, i - prefixMap[balance]);
} else {
prefixMap[balance] = i;
}
}
return maxLength;
}
};class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, -1);
int balance = 0;
int maxLength = 0;
for (int i = 0; i < nums.length; i++) {
balance += (nums[i] == 1) ? 1 : -1;
if (prefixMap.containsKey(balance)) {
maxLength = Math.max(maxLength, i - prefixMap.get(balance));
} else {
prefixMap.put(balance, i);
}
}
return maxLength;
}
}class Solution:
def findMaxLength(self, nums: List[int]) -> int:
prefix_map = {0: -1}
balance = 0
max_length = 0
for i, num in enumerate(nums):
balance += 1 if num == 1 else -1
if balance in prefix_map:
max_length = max(max_length, i - prefix_map[balance])
else:
prefix_map[balance] = i
return max_length/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function(nums) {
const prefixMap = new Map();
prefixMap.set(0, -1);
let balance = 0;
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
balance += (nums[i] === 1) ? 1 : -1;
if (prefixMap.has(balance)) {
maxLength = Math.max(maxLength, i - prefixMap.get(balance));
} else {
prefixMap.set(balance, i);
}
}
return maxLength;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.