DSA problem
Longest Balanced Subarray II
Given a binary array nums of length n and a list of queries queries[i] = [L_i, R_i], for each query return the length of the longest contiguous subarray of nums[L_i..R_i] containing an equal number of 0s and 1s.
The classic prefix-balance trick reduces "equal zeros and ones" to "two indices with the same prefix value". Define balance[i] as (count of 1s minus count of 0s) in nums[0..i-1], so balance[0] = 0 and balance[i+1] = balance[i] +/- 1. A subarray (i, j] is balanced iff balance[j] == balance[i]. Therefore the global answer over a fixed range [L, R] is the maximum of (j - i) over all pairs (i, j) with L <= i < j <= R + 1 and balance[i] == balance[j].
For a single query this is solvable in O(R - L + 1) with a hash map that remembers, for each balance value, the leftmost index seen inside the current window. To answer many queries efficiently we go offline: sort queries by R and sweep j from 0 to n. For each balance value b we maintain its most recent occurrence inside the sweep. As j grows we update a segment tree indexed by i (the position of that "earlier" occurrence) holding the value j - i. Each query [L, R] becomes a max-range query on the segment tree restricted to indices i >= L and j <= R + 1.
Because balance can range from -n to +n, shift everything by +n so the values become non-negative array indices into a "last seen position by balance" array. The total time is O((n + Q) log n) with O(n) memory.
Examples
nums = [0,1,0,0,1,1,0], queries = [[0,6],[2,5],[0,3]][6,4,2]nums = [1,1,1,0], queries = [[0,3],[0,2]][2,0]nums = [0,1], queries = [[0,1]][2]Constraints
- 1 <= nums.length <= 10^5
- nums[i] is 0 or 1
- 1 <= queries.length <= 10^5
- 0 <= L_i <= R_i < nums.length
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.