Watch 10 video solutions for Longest Balanced Subarray I, a medium level problem involving Array, Hash Table, Divide and Conquer. This walkthrough by codestorywithMIK has 11,304 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
A subarray is called balanced if the number of distinct even numbers in the subarray is equal to the number of distinct odd numbers.
Return the length of the longest balanced subarray.
Example 1:
Input: nums = [2,5,4,3]
Output: 4
Explanation:
[2, 5, 4, 3].[2, 4] and 2 distinct odd numbers [5, 3]. Thus, the answer is 4.Example 2:
Input: nums = [3,2,2,5,4]
Output: 5
Explanation:
[3, 2, 2, 5, 4].[2, 4] and 2 distinct odd numbers [3, 5]. Thus, the answer is 5.Example 3:
Input: nums = [1,2,3,2]
Output: 3
Explanation:
[2, 3, 2].[2] and 1 distinct odd number [3]. Thus, the answer is 3.
Constraints:
1 <= nums.length <= 15001 <= nums[i] <= 105Problem Overview: You are given an array and need the length of the longest contiguous subarray that is balanced. A balanced subarray means the counts of the two target values (commonly 0 and 1) are equal. The task is to scan the array and return the maximum length of such a subarray.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
The direct way is to check every possible subarray. Use two nested loops: fix a starting index and extend the subarray one element at a time while counting the occurrences of both values. Each time the counts match, update the maximum length. This approach works because it evaluates all candidate ranges, but the nested iteration makes it quadratic. With arrays of size up to tens of thousands, O(n²) quickly becomes too slow.
Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)
The optimal solution uses a prefix sum transformation combined with a hash table. Convert the array so that one value contributes +1 and the other contributes -1. When a subarray contains equal counts, the total sum across that range becomes zero. Maintain a running prefix sum while iterating through the array. Store the first index where each prefix sum appears in a hash map.
If the same prefix sum appears again at index j after first appearing at i, the elements between them form a balanced subarray because the net contribution is zero. The length is j - i. Track the maximum length as you scan. Initializing the map with sum = 0 at index -1 allows balanced subarrays starting from index 0. This technique turns the problem into detecting equal prefix sums, which is why the lookup operation in the hash map is critical for achieving O(n) time.
This method is common in array problems involving equal counts or zero-sum ranges and builds directly on array traversal combined with prefix accumulation.
Recommended for interviews: Interviewers expect the prefix sum + hash map solution. Showing the brute force approach demonstrates you understand the definition of a balanced subarray, but the optimized O(n) solution proves you can recognize prefix-sum patterns and use constant-time hash lookups to eliminate nested loops.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or when input size is very small |
| Prefix Sum + Hash Table | O(n) | O(n) | General case and expected interview solution for large arrays |