Watch 10 video solutions for Longest Balanced Subarray II, a hard level problem involving Array, Hash Table, Divide and Conquer. This walkthrough by codestorywithMIK has 13,794 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 <= 1051 <= nums[i] <= 105Problem Overview: You receive an array and must find the length of the longest subarray that satisfies a specific balance condition between its elements. The challenge is detecting equalized prefix states efficiently across the array while handling large input sizes where brute force checks are too slow.
Approach 1: Brute Force Subarray Check (O(nĀ²) time, O(1) space)
Enumerate every possible subarray using two nested loops. For each start index i, extend the end index j and recompute the balance condition by counting values inside the window. This guarantees correctness but quickly becomes impractical as n grows because every candidate segment requires recomputation. This approach is useful for understanding the structure of balanced segments but fails typical interview constraints.
Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)
Convert the balance requirement into a prefix-state equality problem. Maintain a running prefix sum or balance score that represents the difference between categories of elements. If two indices share the same prefix state, the subarray between them is balanced. Store the first occurrence of each prefix state in a hash table. As you iterate through the array, compute the current prefix state and check whether it has appeared before. The distance between the first occurrence and the current index forms a balanced subarray candidate.
Approach 3: Segment Tree + Prefix Sum + Hash Table (O(n log n) time, O(n) space)
For larger constraints or extended balance definitions, combine prefix sums with a segment tree. First compute prefix balance values for every index. A hash table tracks earliest occurrences of prefix states, while the segment tree supports efficient range queries when evaluating candidate spans during divide-and-conquer processing. The tree allows fast retrieval of valid prefix boundaries and ensures each segment is processed in logarithmic time. This hybrid structure handles cases where prefix states must be validated across multiple ranges rather than a single linear scan.
Recommended for interviews: Interviewers typically expect the prefix sum + hash map insight because it converts the problem from subarray enumeration to prefix-state matching. Demonstrating the brute force approach first shows you understand the definition of a balanced segment. The optimized solution proves you recognize the core pattern used in many longest subarray with equal counts problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Scan | O(nĀ²) | O(1) | Small arrays or verifying correctness during development |
| Prefix Sum + Hash Table | O(n) | O(n) | Best general solution for detecting equal prefix states |
| Segment Tree + Prefix Sum + Hash Table | O(n log n) | O(n) | Large inputs or variants requiring range queries on prefix states |