Description
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
Solutions
This optimized segment tree solution also converts the problem to prefix sums (even = +1, odd = -1), then uses a segment tree to track minimum and maximum values in ranges. For each new element, it updates a map tracking which indices have seen each value, applies a range update to zero out previous occurrences of that value in the segment tree, then updates the current range. It then searches for the leftmost position where the segment tree indicates a zero prefix sum exists, meaning a balanced subarray from that position to the current index. This cleaner implementation achieves the same O(n log n) complexity as the previous solution with simpler logic.
class SegmentTree {
constructor(n) {
this.n = n
this.minTree = new Array(4 * n).fill(0)
this.maxTree = new Array(4 * n).fill(0)
this.lazy = new Array(4 * n).fill(0)
}
push(node, start, end) {
if (this.lazy[node] !== 0) {
this.minTree[node] += this.lazy[node]
this.maxTree[node] += this.lazy[node]
if (start !== end) {
this.lazy[node * 2] += this.lazy[node]
this.lazy[node * 2 + 1] += this.lazy[node]
}
this.lazy[node] = 0
}
}
updateRange(node, start, end, l, r, val) {
this.push(node, start, end)
if (start > end || start > r || end < l) return
if (l <= start && end <= r) {
this.lazy[node] += val
this.push(node, start, end)
return
}
const mid = Math.floor((start + end) / 2)
this.updateRange(node * 2, start, mid, l, r, val)
this.updateRange(node * 2 + 1, mid + 1, end, l, r, val)
this.minTree[node] = Math.min(
this.minTree[node * 2],
this.minTree[node * 2 + 1]
)
this.maxTree[node] = Math.max(
this.maxTree[node * 2],
this.maxTree[node * 2 + 1]
)
}
findLeftmostZero(node, start, end) {
this.push(node, start, end)
if (this.minTree[node] > 0 || this.maxTree[node] < 0) return -1
if (start === end) return this.minTree[node] === 0 ? start : -1
const mid = Math.floor((start + end) / 2)
const left = this.findLeftmostZero(node * 2, start, mid)
if (left !== -1) return left
return this.findLeftmostZero(node * 2 + 1, mid + 1, end)
}
}
function longestBalanced(nums) {
const n = nums.length
const prev = new Map()
const st = new SegmentTree(n)
let res = 0
for (let r = 0; r < n; r++) {
const v = nums[r]
const val = v % 2 === 0 ? 1 : -1
if (prev.has(v)) {
st.updateRange(1, 0, n - 1, 0, prev.get(v), -val)
}
st.updateRange(1, 0, n - 1, 0, r, val)
prev.set(v, r)
const l = st.findLeftmostZero(1, 0, n - 1)
if (l !== -1 && l <= r) res = Math.max(res, r - l + 1)
}
return res
}