Longest Balanced Subarray II solution and explanation
Google
9 more videos on this problem
Longest Balanced Subarray II | Leetcode 3721 | Min-Max Query | Segment Tree Concept | Video 15 | MIKcodestorywithMIK · 33:17 · 16K views
3721. Longest Balanced Subarray II | Leetcode Daily - PythonLeetcode Daily · 9:03 · 3K views
Q4. Longest Balanced Subarray ii || Lazy Segment Tree || Leetcode Weekly Contest 472 || Watch in 2X🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 14:03 · 3K views
leetcode 3721 | Longest Balanced Subarray II | Hard | Segment tree |Prefix Count | Begineer FriendlyCode With Vick · 30:32 · 2K views
Longest Balanced Subarray II Leetcode 3721 | Detailed Solution | Java-HindiKernel Queen 👑 · 22:56 · 2K views
3721. Longest Balanced Subarray II (Leetcode Hard)Programming Live with Larry · 1:22:48 · 1K views
Daily Leetcode #2143: Feb 11, 2026 - 3721. Longest Balanced Subarray IIProgramming Live with Larry · 1:38:48 · 1K views
Longest Balanced Subarray II | LeetCode 3721 - Pythonimpoldev · 40:10 · 1K views
Longest Balanced Subarray II | LeetCode 3721 | Segment Tree | Java Code | Developer CoderDeveloper Coder · 1:18:09 · 861 views
Leetcode 3721 | Longest Balanced Subarray IILeetcode Lab · 8:35 · 99 views
The problem
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:
- The longest balanced subarray is
[2, 5, 4, 3]. - It has 2 distinct even numbers
[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:
- The longest balanced subarray is
[3, 2, 2, 5, 4]. - It has 2 distinct even numbers
[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:
- The longest balanced subarray is
[2, 3, 2]. - It has 1 distinct even number
[2]and 1 distinct odd number[3]. Thus, the answer is 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Approach overview
Problem 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.
Solution
We can transform the problem into a prefix sum problem. Define a prefix sum variable now, representing the difference between odd and even numbers in the current subarray:
$
now = distinct odd numbers - distinct even numbers
For odd elements, record as +1, and for even elements, record as -1. Use a hash table last to record the last occurrence position of each number. If a number appears repeatedly, we need to revoke its previous contribution.
To efficiently calculate the subarray length each time a right endpoint element is added, we use a segment tree to maintain the minimum and maximum values of the interval prefix sum, while supporting interval addition operations and binary search queries on the segment tree. When iterating to right endpoint i, first update the contribution of the current element, then use the segment tree to query the earliest position pos where the current prefix sum now appears. The current subarray length is i - pos, and we update the answer:
ans = max(ans, i - pos)
The time complexity is O(n log n), where n is the length of the array. Each segment tree modification and query operation takes O(log n), and enumerating the right endpoint n times gives a total time complexity of O(n log n). The space complexity is O(n), where segment tree nodes and the hash table each occupy O(n)$ space.
class Solution:
def longestBalanced(self, nums: List[int]) -> int:
n = len(nums)
class Node:
__slots__ = ("l", "r", "mn", "mx", "lazy")
def __init__(self):
self.l = self.r = 0
self.mn = self.mx = 0
self.lazy = 0
tr = [Node() for _ in range((n + 1) * 4)]
def build(u: int, l: int, r: int):
tr[u].l, tr[u].r = l, r
tr[u].mn = tr[u].mx = tr[u].lazy = 0
if l == r:
return
mid = (l + r) >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
def apply(u: int, v: int):
tr[u].mn += v
tr[u].mx += v
tr[u].lazy += v
def pushdown(u: int):
if tr[u].lazy:
apply(u << 1, tr[u].lazy)
apply(u << 1 | 1, tr[u].lazy)
tr[u].lazy = 0
def pushup(u: int):
tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn)
tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx)
def modify(u: int, l: int, r: int, v: int):
if tr[u].l >= l and tr[u].r <= r:
apply(u, v)
return
pushdown(u)
mid = (tr[u].l + tr[u].r) >> 1
if l <= mid:
modify(u << 1, l, r, v)
if r > mid:
modify(u << 1 | 1, l, r, v)
pushup(u)
def query(u: int, target: int) -> int:
if tr[u].l == tr[u].r:
return tr[u].l
pushdown(u)
if tr[u << 1].mn <= target <= tr[u << 1].mx:
return query(u << 1, target)
return query(u << 1 | 1, target)
build(1, 0, n)
last = {}
now = ans = 0
for i, x in enumerate(nums, start=1):
det = 1 if (x & 1) else -1
if x in last:
modify(1, last[x], n, -det)
now -= det
last[x] = i
modify(1, i, n, det)
now += det
pos = query(1, now)
ans = max(ans, i - pos)
return ans/**
*
* Idea:
* - Treat each distinct odd number as +1, and each distinct even number as -1
* - Maintain prefix sums representing the balance
* - When a number appears again, remove its previous contribution
* - Use a segment tree to maintain min/max prefix sums with range add
* - Binary search on the segment tree to find the earliest equal prefix sum
*/
class Solution {
/**
* Segment tree node
*/
static class Node {
int l, r; // segment range
int mn, mx; // minimum / maximum prefix sum
int lazy; // lazy propagation (range add)
}
/**
* Segment tree supporting:
* - range add
* - find the smallest index with a given prefix sum
*/
static class SegmentTree {
Node[] tr;
SegmentTree(int n) {
tr = new Node[n << 2];
for (int i = 0; i < tr.length; i++) {
tr[i] = new Node();
}
build(1, 0, n);
}
// Build an empty tree with all prefix sums = 0
void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
tr[u].mn = tr[u].mx = 0;
tr[u].lazy = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
// Add value v to all prefix sums in [l, r]
void modify(int u, int l, int r, int v) {
if (tr[u].l >= l && tr[u].r <= r) {
apply(u, v);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
// Binary search on the segment tree
// Find the smallest index where prefix sum == target
int query(int u, int target) {
if (tr[u].l == tr[u].r) {
return tr[u].l;
}
pushdown(u);
int left = u << 1;
int right = u << 1 | 1;
if (tr[left].mn <= target && target <= tr[left].mx) {
return query(left, target);
}
return query(right, target);
}
// Apply range add
void apply(int u, int v) {
tr[u].mn += v;
tr[u].mx += v;
tr[u].lazy += v;
}
// Update from children
void pushup(int u) {
tr[u].mn = Math.min(tr[u << 1].mn, tr[u << 1 | 1].mn);
tr[u].mx = Math.max(tr[u << 1].mx, tr[u << 1 | 1].mx);
}
// Push lazy tag down
void pushdown(int u) {
if (tr[u].lazy != 0) {
apply(u << 1, tr[u].lazy);
apply(u << 1 | 1, tr[u].lazy);
tr[u].lazy = 0;
}
}
}
public int longestBalanced(int[] nums) {
int n = nums.length;
SegmentTree st = new SegmentTree(n);
// last[x] = last position where value x appeared
Map<Integer, Integer> last = new HashMap<>();
int now = 0; // current prefix sum
int ans = 0; // answer
// Enumerate the right endpoint
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
int det = (x & 1) == 1 ? 1 : -1;
// Remove previous contribution if x appeared before
if (last.containsKey(x)) {
st.modify(1, last.get(x), n, -det);
now -= det;
}
// Add current contribution
last.put(x, i);
st.modify(1, i, n, det);
now += det;
// Find earliest position with the same prefix sum
int pos = st.query(1, now);
ans = Math.max(ans, i - pos);
}
return ans;
}
}/*
* Segment tree node.
* It maintains:
* - [l, r] : the covered index range
* - mn : minimum prefix sum in this range
* - mx : maximum prefix sum in this range
* - lazy : lazy propagation value (range add)
*/
class Node {
public:
int l = 0, r = 0;
int mn = 0, mx = 0;
int lazy = 0;
};
/*
* Segment Tree that supports:
* 1. Range add
* 2. Query the smallest index whose prefix sum equals a given value
*/
class SegmentTree {
public:
SegmentTree(int n) {
tr.resize(n << 2);
for (int i = 0; i < (int) tr.size(); ++i) {
tr[i] = new Node();
}
// Build the tree on range [0, n]
build(1, 0, n);
}
/*
* Add value v to all prefix sums in range [l, r]
*/
void modify(int u, int l, int r, int v) {
if (tr[u]->l >= l && tr[u]->r <= r) {
apply(u, v);
return;
}
pushdown(u);
int mid = (tr[u]->l + tr[u]->r) >> 1;
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
/*
* Binary search on the segment tree.
* Find the smallest index pos such that prefix_sum[pos] == target.
*
* The key observation:
* If target is within [mn, mx] of a segment, then such a position
* must exist inside this segment.
*/
int query(int u, int target) {
if (tr[u]->l == tr[u]->r) {
return tr[u]->l;
}
pushdown(u);
int lc = u << 1, rc = u << 1 | 1;
if (tr[lc]->mn <= target && target <= tr[lc]->mx) {
return query(lc, target);
}
return query(rc, target);
}
private:
vector<Node*> tr;
/*
* Build an empty segment tree.
* Initial prefix sums are all zero.
*/
void build(int u, int l, int r) {
tr[u]->l = l;
tr[u]->r = r;
tr[u]->mn = tr[u]->mx = 0;
tr[u]->lazy = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
/*
* Apply a range add to node u.
*/
void apply(int u, int v) {
tr[u]->mn += v;
tr[u]->mx += v;
tr[u]->lazy += v;
}
/*
* Push information from children to parent.
*/
void pushup(int u) {
tr[u]->mn = min(tr[u << 1]->mn, tr[u << 1 | 1]->mn);
tr[u]->mx = max(tr[u << 1]->mx, tr[u << 1 | 1]->mx);
}
/*
* Push lazy tag down to children.
*/
void pushdown(int u) {
if (tr[u]->lazy != 0) {
apply(u << 1, tr[u]->lazy);
apply(u << 1 | 1, tr[u]->lazy);
tr[u]->lazy = 0;
}
}
};
class Solution {
public:
int longestBalanced(vector<int>& nums) {
int n = nums.size();
SegmentTree st(n);
/*
* last[x] = the most recent position where value x appeared
*/
unordered_map<int, int> last;
int now = 0; // current prefix sum
int ans = 0; // answer
/*
* Enumerate the right endpoint of the subarray
*/
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
/*
* Contribution of x:
* +1 if x is odd
* -1 if x is even
*/
int det = (x & 1) ? 1 : -1;
/*
* If x appeared before, remove its previous contribution
*/
if (last.count(x)) {
st.modify(1, last[x], n, -det);
now -= det;
}
/*
* Add current contribution of x
*/
last[x] = i;
st.modify(1, i, n, det);
now += det;
/*
* Find the smallest position pos such that
* prefix_sum[pos] == now
*/
int pos = st.query(1, now);
/*
* Update the maximum balanced subarray length
*/
ans = max(ans, i - pos);
}
return ans;
}
};function longestBalanced(nums: number[]): number {
const n = nums.length;
interface Node {
l: number;
r: number;
mn: number;
mx: number;
lazy: number;
}
const tr: Node[] = Array.from({ length: (n + 1) * 4 }, () => ({
l: 0,
r: 0,
mn: 0,
mx: 0,
lazy: 0,
}));
function build(u: number, l: number, r: number) {
tr[u].l = l;
tr[u].r = r;
if (l === r) return;
const mid = (l + r) >> 1;
build(u << 1, l, mid);
build((u << 1) | 1, mid + 1, r);
}
function apply(u: number, v: number) {
tr[u].mn += v;
tr[u].mx += v;
tr[u].lazy += v;
}
function pushdown(u: number) {
if (tr[u].lazy !== 0) {
apply(u << 1, tr[u].lazy);
apply((u << 1) | 1, tr[u].lazy);
tr[u].lazy = 0;
}
}
function pushup(u: number) {
tr[u].mn = Math.min(tr[u << 1].mn, tr[(u << 1) | 1].mn);
tr[u].mx = Math.max(tr[u << 1].mx, tr[(u << 1) | 1].mx);
}
function modify(u: number, l: number, r: number, v: number) {
if (tr[u].l >= l && tr[u].r <= r) {
apply(u, v);
return;
}
pushdown(u);
const mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify((u << 1) | 1, l, r, v);
pushup(u);
}
function query(u: number, target: number): number {
if (tr[u].l === tr[u].r) return tr[u].l;
pushdown(u);
if (tr[u << 1].mn <= target && target <= tr[u << 1].mx) {
return query(u << 1, target);
}
return query((u << 1) | 1, target);
}
build(1, 0, n);
const last = new Map<number, number>();
let now = 0,
ans = 0;
nums.forEach((x, idx) => {
const i = idx + 1;
const det = x & 1 ? 1 : -1;
if (last.has(x)) {
modify(1, last.get(x)!, n, -det);
now -= det;
}
last.set(x, i);
modify(1, i, n, det);
now += det;
const pos = query(1, now);
ans = Math.max(ans, i - pos);
});
return ans;
}// Segment tree node
type Node struct {
l, r int // segment range
mn, mx int // minimum / maximum prefix sum
lazy int // lazy propagation (range add)
}
// Segment tree
type SegmentTree struct {
tr []Node
}
// Build a segment tree for range [0, n]
func NewSegmentTree(n int) *SegmentTree {
st := &SegmentTree{
tr: make([]Node, n<<2),
}
st.build(1, 0, n)
return st
}
// Initialize all prefix sums to 0
func (st *SegmentTree) build(u, l, r int) {
st.tr[u] = Node{l: l, r: r, mn: 0, mx: 0, lazy: 0}
if l == r {
return
}
mid := (l + r) >> 1
st.build(u<<1, l, mid)
st.build(u<<1|1, mid+1, r)
}
// Add v to all prefix sums in [l, r]
func (st *SegmentTree) modify(u, l, r, v int) {
if st.tr[u].l >= l && st.tr[u].r <= r {
st.apply(u, v)
return
}
st.pushdown(u)
mid := (st.tr[u].l + st.tr[u].r) >> 1
if l <= mid {
st.modify(u<<1, l, r, v)
}
if r > mid {
st.modify(u<<1|1, l, r, v)
}
st.pushup(u)
}
// Binary search on the segment tree
// Find the smallest index where prefix sum == target
func (st *SegmentTree) query(u, target int) int {
if st.tr[u].l == st.tr[u].r {
return st.tr[u].l
}
st.pushdown(u)
left, right := u<<1, u<<1|1
if st.tr[left].mn <= target && target <= st.tr[left].mx {
return st.query(left, target)
}
return st.query(right, target)
}
// Apply range addition
func (st *SegmentTree) apply(u, v int) {
st.tr[u].mn += v
st.tr[u].mx += v
st.tr[u].lazy += v
}
// Update from children
func (st *SegmentTree) pushup(u int) {
st.tr[u].mn = min(st.tr[u<<1].mn, st.tr[u<<1|1].mn)
st.tr[u].mx = max(st.tr[u<<1].mx, st.tr[u<<1|1].mx)
}
// Push lazy value down
func (st *SegmentTree) pushdown(u int) {
if st.tr[u].lazy != 0 {
v := st.tr[u].lazy
st.apply(u<<1, v)
st.apply(u<<1|1, v)
st.tr[u].lazy = 0
}
}
// Main function
func longestBalanced(nums []int) int {
n := len(nums)
st := NewSegmentTree(n)
// last[x] = last position where value x appeared
last := make(map[int]int)
now := 0 // current prefix sum
ans := 0 // answer
// Enumerate right endpoint
for i := 1; i <= n; i++ {
x := nums[i-1]
det := -1
if x&1 == 1 {
det = 1
}
// Remove previous contribution if x appeared before
if pos, ok := last[x]; ok {
st.modify(1, pos, n, -det)
now -= det
}
// Add current contribution
last[x] = i
st.modify(1, i, n, det)
now += det
// Find earliest position with same prefix sum
pos := st.query(1, now)
ans = max(ans, i-pos)
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Longest Balanced Subarray II easy or hard?
Longest Balanced Subarray II is typically classified as a hard problem because the balance condition must be converted into a prefix-state equality problem. Recognizing that repeated prefix states imply a balanced segment is the key insight, and implementing the optimized structure efficiently requires strong understanding of arrays and hashing.
Longest Balanced Subarray II Python/Java solution
Most implementations compute a running prefix balance while iterating through the array and store the earliest index for each balance value in a hash map. The same logic translates directly across Python, Java, C++, Go, and TypeScript because it relies on standard dictionary or map operations.
How to solve Longest Balanced Subarray II in O(n)?
Transform the balance requirement into a prefix state. Iterate through the array while maintaining a running prefix value. Store the first index of each prefix state in a hash map. Whenever the same state appears again, compute the length between indices and update the maximum balanced subarray length.
What is the best approach for Longest Balanced Subarray II?
The most practical approach uses prefix sums combined with a hash table to track previously seen balance states. Each prefix state represents the difference between element categories. When the same state appears again, the subarray between the two indices is balanced. For more advanced variants, a segment tree can help process prefix ranges efficiently.
Is Longest Balanced Subarray II asked at Google/Amazon/Meta?
Variants of longest balanced or equal-count subarray problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of prefix sums, hash maps, and array scanning techniques rather than brute force enumeration.
What data structure is used in Longest Balanced Subarray II?
The main structures are prefix sums, hash tables for storing first occurrences of balance states, and sometimes a segment tree for efficient range queries. Together they allow fast detection of matching prefix configurations that form balanced subarrays.
What is the time complexity of Longest Balanced Subarray II?
The optimized implementation runs in O(n log n) time when using a segment tree with prefix sums and a hash table. The segment tree supports logarithmic range queries while scanning the array. Simpler prefix-hash implementations can reach O(n) time if the balance condition can be represented by a single prefix state comparison.