AlgoMaster Logo

Longest Balanced Subarray II

hardFrequencyUpdated September 21, 2026

Understanding the Problem

The load-bearing word is "distinct." If the problem counted every even and odd element, a prefix-sum or sliding window would handle it directly. Distinct values behave differently. Extending a window by one element changes the distinct-even count only when that value is new to the window. Shrinking from the left changes the count only when the removed element was the last copy of its value.

That makes the window state non-monotonic. A number can appear many times, yet it contributes once to the distinct count as long as at least one copy remains in the subarray.

The problem reduces to two sub-questions: how do we track whether a value still belongs to the current subarray, and how do we compare distinct-odd and distinct-even counts efficiently across all subarrays?

Key Constraints:

  • nums.length <= 10^5. An O(n^2) scan over all subarrays is around 10^10 operations in the worst case, too slow. The final solution needs to be O(n log n) or better.
  • Values are at most 10^5, so a hash map keyed by value fits comfortably.
  • The answer is the longest valid subarray, so we want to recover the best left endpoint for each right endpoint in a single sweep rather than re-examine ranges.

Approach 1: Brute Force

Intuition

Pick every possible subarray, scan it, build one set of distinct even values and one set of distinct odd values, and compare their sizes. The longest subarray with equal sizes is the answer.

This is the baseline because it follows the definition directly. It also exposes the bottleneck: we rebuild the same distinct sets from scratch for heavily overlapping subarrays.

Algorithm

  1. Initialize answer = 0.
  2. For every l from 0 to n - 1:
  3. For every r from l to n - 1:
  4. Create empty sets for distinct even and odd values.
  5. Scan k from l to r and insert nums[k] into the appropriate set.
  6. If the two set sizes are equal, update answer.
  7. Return answer.

Example Walkthrough

1Try [0..0]: {2} even, {} odd. 1 vs 0, not balanced
0
2
1
5
2
4
3
3
1/4

Code

The inner rescan is pure waste. Fixing the left boundary and extending the right one element at a time lets us update the distinct sets incrementally instead of rebuilding them.

Approach 2: Incremental Distinct Sets

Intuition

Fix left and grow right one step at a time. The window [left..right + 1] differs from [left..right] by a single new value, so we insert that value into the correct set in O(1) average time rather than rebuilding both sets. For a fixed left, the two sets always hold the distinct values inside the current window, because each step only adds and nothing leaves.

This removes the O(n) inner rescan and drops the running time from O(n^3) to O(n^2). It is still too slow at n = 10^5, because every (left, right) pair is examined.

Algorithm

  1. Initialize answer = 0.
  2. For each left from 0 to n - 1:
  3. Create empty even and odd sets.
  4. Extend right from left to n - 1.
  5. Insert nums[right] into the correct set.
  6. If the set sizes are equal, update answer.
  7. Return answer.

Example Walkthrough

1left=0: expand right. r=0: odd={3}, even={}. 1 vs 0
0
left
3
right
1
2
2
2
3
5
4
4
1/4

Code

Distinct-set maintenance is now cheap, but we still process all O(n^2) subarrays. The next approach transforms the balance condition into a value that a single sweep over the right endpoint can match against, so the best left endpoint falls out of one query instead of an inner loop.

Approach 3: Optimal (Segment Tree + Last Occurrence)

Intuition

The path to O(n log n) is to stop counting "how many distinct values are inside [l..r]" and reason about latest occurrences instead.

Fix a right endpoint i. For any value x, whether x belongs to the subarray [l..i] depends on one fact: is the latest occurrence of x at or after l? If yes, x appears somewhere in [l..i]. If no, every copy of x sits before l, so x is absent.

Assign each distinct value a contribution: +1 if odd, -1 if even. A subarray is balanced exactly when its distinct-odd and distinct-even counts are equal, which means the total contribution of its distinct values is 0.

Let last[x] be the latest 1-based position of value x. Process positions left to right. After handling position i, define tree[p] as the total contribution of all distinct values whose latest occurrence is at or before p, and now as the total contribution of all distinct values seen so far (equivalently tree[i]). The values counted in tree[p] are precisely the ones whose only remaining copies lie in [1..p], so they are absent from the subarray (p + 1) .. i. The contribution of the distinct values that do fall inside (p + 1) .. i is therefore now - tree[p], and the subarray is balanced exactly when tree[p] == now.

For each right endpoint i, we want the earliest p with tree[p] == now, which maximizes the length i - p. When x arrives at position i, its latest occurrence moves: if it appeared before at old, remove its contribution from the suffix [old, n] and add the new contribution to [i, n]. Suffix range-add plus an earliest-position query is what a lazy segment tree handles in O(log n) per step.

Algorithm

  1. Build a lazy segment tree on positions [0, n], initialized to all zeros.
  2. Keep a hash map last for the latest 1-based occurrence of each value.
  3. Keep now = 0 and answer = 0.
  4. For each position i from 1 to n:
  5. Let x = nums[i - 1] and det = +1 if x is odd, otherwise -1.
  6. If x appeared before at last[x], apply modify(last[x], n, -det) and subtract det from now.
  7. Set last[x] = i.
  8. Apply modify(i, n, det) and add det to now.
  9. Query the earliest position p where the segment tree value equals now.
  10. Update answer = max(answer, i - p).
  11. Return answer.

Example Walkthrough

1i=1: x=1 odd, new. now=+1. Earliest p with tree[p]=1 is p=1. len=i-p=0
0
1
i
1
2
2
3
3
2
1/4

Code