mediumTwo PointersPattern: Two Pointers
Balanced Subarray Extraction Solution
Problem Statement
Given a binary array, find the length of the longest subarray having an equal number of zeros and ones.
Examples
Example 1:
Input:[0, 1, 0, 1, 0, 0, 1, 1]
Output:8
Explanation: The entire array has an equal number of zeros and ones, hence it's the longest such subarray.
Example 2:
Input:[0, 1, 1, 0, 0, 1, 1]
Output:6
Explanation: The subarray [0, 1, 1, 0, 0, 1] has an equal number of zeros and ones, and it's the longest such subarray.
Constraints
- Array size is at most 10^5
- Array contains only 0s and 1s
- At least one 0 and one 1 is present in the array
- Array elements are integers
Time: O(n) Space: O(n)
The optimized approach involves using a hashmap to store the cumulative sum of ones and zeros, and updating the cumulative sum as you iterate through the array. This allows you to find the longest balanced subarray in O(n) time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.