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.

longestBalanced.js

/**
 * Longest Balanced Subarray:
 * A subarray is balanced if the number of DISTINCT even values
 * equals the number of DISTINCT odd values.
 *
 * This solution uses:
 *  - value compression
 *  - tracking first occurrences of each value
 *  - a segment tree with lazy propagation
 *  - sliding left boundary
 *
 * It is the official O(n log n) solution.
 */

var longestBalanced = function(nums) {
    const n = nums.length;
    if (n === 0) return 0;

    // ------------------------------------------------------------
    // 1. VALUE COMPRESSION
    // ------------------------------------------------------------
    // Compress values so each distinct number gets an ID 0..m-1.
    const uniq = Array.from(new Set(nums)).sort((a, b) => a - b);
    const m = uniq.length;

    const idMap = new Map();
    for (let i = 0; i < m; i++) {
        idMap.set(uniq[i], i);
    }

    // pos[id] = all indices where that compressed value appears
    const pos = Array.from({ length: m }, () => []);

    // idOfIndex[i] = compressed ID of nums[i]
    const idOfIndex = new Int32Array(n);

    for (let i = 0; i < n; i++) {
        const id = idMap.get(nums[i]);
        pos[id].push(i);
        idOfIndex[i] = id;
    }

    // ------------------------------------------------------------
    // 2. SIGN ARRAY
    // ------------------------------------------------------------
    // signArr[id] = +1 if odd, -1 if even
    const signArr = new Int8Array(m);
    for (let i = 0; i < m; i++) {
        signArr[i] = (uniq[i] & 1) ? 1 : -1;
    }

    // ptr[id] = pointer to which occurrence of this value
    // is currently the "first occurrence" in the sliding window.
    const ptr = new Int32Array(m);

    // ------------------------------------------------------------
    // 3. SEGMENT TREE SETUP
    // ------------------------------------------------------------
    // We maintain a segment tree over indices [0..n-1].
    // Each node stores:
    //   mn = minimum balance in that segment
    //   mx = maximum balance in that segment
    //   lazy = lazy propagation value
    //
    // The tree tracks the "balance" for all possible right endpoints r.
    // A subarray [l..r] is balanced if balance(l, r) == 0.
    //
    const size = 4 * n + 5;
    const mn = new Int32Array(size);
    const mx = new Int32Array(size);
    const lazy = new Int32Array(size);

    // Apply a lazy update to a node
    const apply = (idx, v) => {
        mn[idx] += v;
        mx[idx] += v;
        lazy[idx] += v;
    };

    // Push lazy value down to children
    const push = (idx) => {
        const v = lazy[idx];
        if (v !== 0) {
            const left = idx << 1;
            const right = left | 1;
            apply(left, v);
            apply(right, v);
            lazy[idx] = 0;
        }
    };

    // Pull values up from children
    const pull = (idx) => {
        const left = idx << 1;
        const right = left | 1;
        mn[idx] = Math.min(mn[left], mn[right]);
        mx[idx] = Math.max(mx[left], mx[right]);
    };

    // Range update: add v to all positions in [ql, qr]
    const update = (idx, l, r, ql, qr, v) => {
        if (qr < l || ql > r) return;
        if (ql <= l && r <= qr) {
            apply(idx, v);
            return;
        }
        push(idx);
        const mid = (l + r) >> 1;
        update(idx << 1, l, mid, ql, qr, v);
        update((idx << 1) | 1, mid + 1, r, ql, qr, v);
        pull(idx);
    };

    // Find the largest index >= ql where the segment value == 0
    const findLastZero = (idx, l, r, ql) => {
        // If segment is outside range or cannot contain zero, skip
        if (r < ql) return -1;
        if (mn[idx] > 0 || mx[idx] < 0) return -1;

        // Leaf node: this is a zero
        if (l === r) return l;

        push(idx);
        const mid = (l + r) >> 1;

        // Try right child first (we want the largest index)
        let res = findLastZero((idx << 1) | 1, mid + 1, r, ql);
        if (res !== -1) return res;

        // Otherwise try left child
        return findLastZero(idx << 1, l, mid, ql);
    };

    // ------------------------------------------------------------
    // 4. INITIALIZE SEGMENT TREE WITH FIRST OCCURRENCES
    // ------------------------------------------------------------
    // For each distinct value, its first occurrence contributes
    // its sign to all r >= firstOccurrence.
    for (let id = 0; id < m; id++) {
        const arr = pos[id];
        if (arr.length > 0) {
            update(1, 0, n - 1, arr[0], n - 1, signArr[id]);
        }
    }

    // ------------------------------------------------------------
    // 5. SLIDE LEFT BOUNDARY l FROM 0 TO n-1
    // ------------------------------------------------------------
    let ans = 0;

    for (let l = 0; l < n; l++) {

        // Pruning: if remaining length can't beat ans, stop early
        if (n - l <= ans) break;

        // Only search if zero is possible in the segment tree
        if (!(mn[1] > 0 || mx[1] < 0)) {
            const r = findLastZero(1, 0, n - 1, l);
            if (r !== -1) {
                ans = Math.max(ans, r - l + 1);
            }
        }

        // --------------------------------------------------------
        // Remove nums[l] from the window and adjust contributions
        // --------------------------------------------------------
        const id = idOfIndex[l];
        let k = ptr[id];
        const arr = pos[id];

        // If this index is the current first occurrence
        if (k < arr.length && arr[k] === l) {
            const sign = signArr[id];

            // Remove its contribution
            update(1, 0, n - 1, arr[k], n - 1, -sign);

            // Move pointer to next occurrence
            k++;

            // Add contribution of new first occurrence (if exists)
            if (k < arr.length) {
                update(1, 0, n - 1, arr[k], n - 1, sign);
            }

            ptr[id] = k;
        }
    }

    return ans;
};