1import java.util.HashMap;
2import java.util.Map;
3
4/**
5 * Idea:
6 * - Treat each distinct odd number as +1, and each distinct even number as -1.
7 * - Maintain prefix sums representing the odd/even balance.
8 * - When a number appears again, remove its previous contribution
9 *   (so only the latest occurrence of each value counts).
10 * - Use a segment tree with lazy propagation to maintain the min/max
11 *   prefix sums under range-add updates.
12 * - Binary search on the segment tree to find the earliest index whose
13 *   prefix sum equals the current prefix sum, which yields the longest
14 *   balanced subarray ending at the current position.
15 */
16class Solution {
17
18    /**
19     * Segment tree node covering a range of prefix-sum indices.
20     */
21    static class Node {
22        int left, right;        // range covered by this node: [left, right]
23        int minSum, maxSum;     // minimum / maximum prefix sum within the range
24        int lazyAdd;            // pending range-add value (lazy propagation)
25    }
26
27    /**
28     * Segment tree supporting:
29     * - range add (add a value to all prefix sums in a range)
30     * - descending search for the smallest index holding a given prefix sum
31     */
32    static class SegmentTree {
33        Node[] tree;
34
35        SegmentTree(int size) {
36            tree = new Node[size << 2];
37            for (int i = 0; i < tree.length; i++) {
38                tree[i] = new Node();
39            }
40            build(1, 0, size);
41        }
42
43        /**
44         * Build the tree over [left, right] with all prefix sums initialized to 0.
45         */
46        void build(int node, int left, int right) {
47            tree[node].left = left;
48            tree[node].right = right;
49            tree[node].minSum = 0;
50            tree[node].maxSum = 0;
51            tree[node].lazyAdd = 0;
52            if (left == right) {
53                return;
54            }
55            int mid = (left + right) >> 1;
56            build(node << 1, left, mid);
57            build(node << 1 | 1, mid + 1, right);
58        }
59
60        /**
61         * Add value to every prefix sum whose index lies in [left, right].
62         */
63        void modify(int node, int left, int right, int value) {
64            // Current node range fully covered: apply lazily and stop
65            if (tree[node].left >= left && tree[node].right <= right) {
66                apply(node, value);
67                return;
68            }
69            pushdown(node);
70            int mid = (tree[node].left + tree[node].right) >> 1;
71            if (left <= mid) {
72                modify(node << 1, left, right, value);
73            }
74            if (right > mid) {
75                modify(node << 1 | 1, left, right, value);
76            }
77            pushup(node);
78        }
79
80        /**
81         * Binary search on the tree: find the smallest index whose
82         * prefix sum equals target.
83         *
84         * Correctness note: prefix sums change by exactly 1 between
85         * adjacent indices, so if target lies within [minSum, maxSum]
86         * of a subtree, that subtree must contain an index with that
87         * exact prefix sum.
88         */
89        int query(int node, int target) {
90            // Reached a leaf: this is the answer index
91            if (tree[node].left == tree[node].right) {
92                return tree[node].left;
93            }
94            pushdown(node);
95            int leftChild = node << 1;
96            int rightChild = node << 1 | 1;
97            // Prefer the left child to obtain the smallest index
98            if (tree[leftChild].minSum <= target && target <= tree[leftChild].maxSum) {
99                return query(leftChild, target);
100            }
101            return query(rightChild, target);
102        }
103
104        /**
105         * Apply a range-add value to a node and record it lazily.
106         */
107        void apply(int node, int value) {
108            tree[node].minSum += value;
109            tree[node].maxSum += value;
110            tree[node].lazyAdd += value;
111        }
112
113        /**
114         * Recompute this node's aggregates from its children.
115         */
116        void pushup(int node) {
117            tree[node].minSum = Math.min(tree[node << 1].minSum, tree[node << 1 | 1].minSum);
118            tree[node].maxSum = Math.max(tree[node << 1].maxSum, tree[node << 1 | 1].maxSum);
119        }
120
121        /**
122         * Propagate the pending lazy value down to both children.
123         */
124        void pushdown(int node) {
125            if (tree[node].lazyAdd != 0) {
126                apply(node << 1, tree[node].lazyAdd);
127                apply(node << 1 | 1, tree[node].lazyAdd);
128                tree[node].lazyAdd = 0;
129            }
130        }
131    }
132
133    /**
134     * Returns the length of the longest subarray in which the number of
135     * distinct odd values equals the number of distinct even values.
136     */
137    public int longestBalanced(int[] nums) {
138        int n = nums.length;
139        SegmentTree segmentTree = new SegmentTree(n);
140
141        // lastIndex.get(x) = most recent 1-based position where value x appeared
142        Map<Integer, Integer> lastIndex = new HashMap<>();
143
144        int currentSum = 0; // prefix sum at the current right endpoint
145        int answer = 0;     // length of the longest balanced subarray found
146
147        // Enumerate the right endpoint (1-based index i)
148        for (int i = 1; i <= n; i++) {
149            int value = nums[i - 1];
150            // Odd contributes +1, even contributes -1
151            int delta = (value & 1) == 1 ? 1 : -1;
152
153            // If the value appeared before, cancel its previous contribution
154            // over the suffix starting at its last position
155            if (lastIndex.containsKey(value)) {
156                segmentTree.modify(1, lastIndex.get(value), n, -delta);
157                currentSum -= delta;
158            }
159
160            // Record the new occurrence and add its contribution
161            // over the suffix starting at position i
162            lastIndex.put(value, i);
163            segmentTree.modify(1, i, n, delta);
164            currentSum += delta;
165
166            // Find the earliest position whose prefix sum matches the
167            // current one; the subarray between them is balanced
168            int position = segmentTree.query(1, currentSum);
169            answer = Math.max(answer, i - position);
170        }
171
172        return answer;
173    }
174}
175

1/*
2 * Segment tree node.
3 * It maintains:
4 *  - left, right : the index range [left, right] covered by this node
5 *  - minVal      : minimum prefix sum within this range
6 *  - maxVal      : maximum prefix sum within this range
7 *  - lazy        : pending lazy-propagation value (range add)
8 */
9class Node {
10public:
11    int left = 0, right = 0;
12    int minVal = 0, maxVal = 0;
13    int lazy = 0;
14};
15
16/*
17 * Segment tree supporting:
18 *  1. Range add (add a value to all prefix sums in a range)
19 *  2. Query for the smallest index whose prefix sum equals a target value
20 */
21class SegmentTree {
22public:
23    explicit SegmentTree(int n) {
24        tree.resize(n << 2);
25        // Build the tree over the index range [0, n]
26        build(1, 0, n);
27    }
28
29    /*
30     * Add value to all prefix sums in range [left, right].
31     */
32    void modify(int u, int left, int right, int value) {
33        if (tree[u].left >= left && tree[u].right <= right) {
34            apply(u, value);
35            return;
36        }
37        pushdown(u);
38        int mid = (tree[u].left + tree[u].right) >> 1;
39        if (left <= mid) {
40            modify(u << 1, left, right, value);
41        }
42        if (right > mid) {
43            modify(u << 1 | 1, left, right, value);
44        }
45        pushup(u);
46    }
47
48    /*
49     * Binary search on the segment tree.
50     * Find the smallest index pos such that prefixSum[pos] == target.
51     *
52     * Key observation:
53     * If target lies within [minVal, maxVal] of a segment, then since
54     * adjacent prefix sums differ by exactly 1, a position with prefix
55     * sum equal to target must exist inside that segment.
56     */
57    int query(int u, int target) {
58        if (tree[u].left == tree[u].right) {
59            return tree[u].left;
60        }
61        pushdown(u);
62        int leftChild = u << 1, rightChild = u << 1 | 1;
63        // Prefer the left child to obtain the smallest index
64        if (tree[leftChild].minVal <= target && target <= tree[leftChild].maxVal) {
65            return query(leftChild, target);
66        }
67        return query(rightChild, target);
68    }
69
70private:
71    vector<Node> tree;
72
73    /*
74     * Build an empty segment tree over [left, right].
75     * All initial prefix sums are zero.
76     */
77    void build(int u, int left, int right) {
78        tree[u].left = left;
79        tree[u].right = right;
80        tree[u].minVal = tree[u].maxVal = 0;
81        tree[u].lazy = 0;
82        if (left == right) {
83            return;
84        }
85        int mid = (left + right) >> 1;
86        build(u << 1, left, mid);
87        build(u << 1 | 1, mid + 1, right);
88    }
89
90    /*
91     * Apply a range-add of value to node u.
92     */
93    void apply(int u, int value) {
94        tree[u].minVal += value;
95        tree[u].maxVal += value;
96        tree[u].lazy += value;
97    }
98
99    /*
100     * Recompute parent information from its two children.
101     */
102    void pushup(int u) {
103        tree[u].minVal = min(tree[u << 1].minVal, tree[u << 1 | 1].minVal);
104        tree[u].maxVal = max(tree[u << 1].maxVal, tree[u << 1 | 1].maxVal);
105    }
106
107    /*
108     * Propagate the lazy tag down to both children.
109     */
110    void pushdown(int u) {
111        if (tree[u].lazy != 0) {
112            apply(u << 1, tree[u].lazy);
113            apply(u << 1 | 1, tree[u].lazy);
114            tree[u].lazy = 0;
115        }
116    }
117};
118
119class Solution {
120public:
121    int longestBalanced(vector<int>& nums) {
122        int n = nums.size();
123        SegmentTree segmentTree(n);
124
125        /*
126         * lastPos[x] = the most recent index (1-based) where value x appeared
127         */
128        unordered_map<int, int> lastPos;
129
130        int prefixSum = 0; // current prefix sum at the right endpoint
131        int ans = 0;       // length of the longest balanced subarray
132
133        /*
134         * Enumerate the right endpoint i (1-based) of the subarray.
135         */
136        for (int i = 1; i <= n; ++i) {
137            int x = nums[i - 1];
138
139            /*
140             * Contribution of value x:
141             *  +1 if x is odd
142             *  -1 if x is even
143             */
144            int delta = (x & 1) ? 1 : -1;
145
146            /*
147             * If x appeared before, remove its previous contribution
148             * from all prefix sums starting at its last position.
149             */
150            if (lastPos.count(x)) {
151                segmentTree.modify(1, lastPos[x], n, -delta);
152                prefixSum -= delta;
153            }
154
155            /*
156             * Record the new position of x and add its contribution
157             * to all prefix sums from index i onward.
158             */
159            lastPos[x] = i;
160            segmentTree.modify(1, i, n, delta);
161            prefixSum += delta;
162
163            /*
164             * Find the smallest position pos such that
165             * prefixSum[pos] == prefixSum, meaning the subarray
166             * (pos, i] is balanced.
167             */
168            int pos = segmentTree.query(1, prefixSum);
169
170            /*
171             * Update the answer with the length of this balanced subarray.
172             */
173            ans = max(ans, i - pos);
174        }
175
176        return ans;
177    }
178};
179

1/**
2 * Segment tree node definition.
3 * Each node maintains the range [left, right], the minimum and maximum
4 * values within that range, and a lazy tag for pending range updates.
5 */
6interface SegmentTreeNode {
7    left: number;   // Left boundary of the range covered by this node
8    right: number;  // Right boundary of the range covered by this node
9    minVal: number; // Minimum value in this range
10    maxVal: number; // Maximum value in this range
11    lazy: number;   // Lazy propagation tag (pending addition)
12}
13
14// Global segment tree storage
15let tree: SegmentTreeNode[];
16
17/**
18 * Build the segment tree over the range [left, right].
19 * @param node  Current node index in the tree array
20 * @param left  Left boundary of the range
21 * @param right Right boundary of the range
22 */
23function build(node: number, left: number, right: number): void {
24    tree[node].left = left;
25    tree[node].right = right;
26    if (left === right) return;
27    const mid = (left + right) >> 1;
28    build(node << 1, left, mid);
29    build((node << 1) | 1, mid + 1, right);
30}
31
32/**
33 * Apply an addition of `val` to the given node:
34 * update its min/max values and accumulate the lazy tag.
35 * @param node Current node index
36 * @param val  Value to add
37 */
38function apply(node: number, val: number): void {
39    tree[node].minVal += val;
40    tree[node].maxVal += val;
41    tree[node].lazy += val;
42}
43
44/**
45 * Push the lazy tag of the current node down to its two children.
46 * @param node Current node index
47 */
48function pushdown(node: number): void {
49    if (tree[node].lazy !== 0) {
50        apply(node << 1, tree[node].lazy);
51        apply((node << 1) | 1, tree[node].lazy);
52        tree[node].lazy = 0;
53    }
54}
55
56/**
57 * Recompute the min/max of the current node from its two children.
58 * @param node Current node index
59 */
60function pushup(node: number): void {
61    tree[node].minVal = Math.min(tree[node << 1].minVal, tree[(node << 1) | 1].minVal);
62    tree[node].maxVal = Math.max(tree[node << 1].maxVal, tree[(node << 1) | 1].maxVal);
63}
64
65/**
66 * Range update: add `val` to every position in [left, right].
67 * @param node  Current node index
68 * @param left  Left boundary of the update range
69 * @param right Right boundary of the update range
70 * @param val   Value to add
71 */
72function modify(node: number, left: number, right: number, val: number): void {
73    // Current node range is fully covered by the update range
74    if (tree[node].left >= left && tree[node].right <= right) {
75        apply(node, val);
76        return;
77    }
78    pushdown(node);
79    const mid = (tree[node].left + tree[node].right) >> 1;
80    if (left <= mid) modify(node << 1, left, right, val);
81    if (right > mid) modify((node << 1) | 1, left, right, val);
82    pushup(node);
83}
84
85/**
86 * Find the leftmost position whose stored value equals `target`.
87 * The search prefers the left subtree whenever the target value
88 * lies within its [min, max] range.
89 * @param node   Current node index
90 * @param target Target value to locate
91 * @returns The leftmost position holding the target value
92 */
93function query(node: number, target: number): number {
94    // Reached a leaf: return its position
95    if (tree[node].left === tree[node].right) return tree[node].left;
96    pushdown(node);
97    // Go left if the target value can exist in the left subtree
98    if (tree[node << 1].minVal <= target && target <= tree[node << 1].maxVal) {
99        return query(node << 1, target);
100    }
101    return query((node << 1) | 1, target);
102}
103
104/**
105 * Compute the length of the longest balanced subarray, i.e. the longest
106 * subarray in which the number of distinct odd values equals the number
107 * of distinct even values.
108 *
109 * Idea:
110 * - Treat each distinct odd value as +1 and each distinct even value as -1.
111 * - For every prefix ending at index i, the segment tree position j stores
112 *   the "balance" of the subarray (j, i] considering only the latest
113 *   occurrence of each value.
114 * - When a value reappears, its previous contribution is cancelled on the
115 *   prefix range [lastIndex, n] so that only the newest occurrence counts.
116 * - A balanced subarray ending at i corresponds to a position j with
117 *   balance equal to the current total, so we query the leftmost such j.
118 *
119 * @param nums Input array of numbers
120 * @returns Length of the longest balanced subarray
121 */
122function longestBalanced(nums: number[]): number {
123    const n = nums.length;
124
125    // Initialize the segment tree nodes over positions [0, n]
126    tree = Array.from({ length: (n + 1) * 4 }, () => ({
127        left: 0,
128        right: 0,
129        minVal: 0,
130        maxVal: 0,
131        lazy: 0,
132    }));
133    build(1, 0, n);
134
135    // Map from value to the index (1-based) of its latest occurrence
136    const lastIndex = new Map<number, number>();
137    let currentSum = 0; // Current total balance over the whole prefix
138    let result = 0;     // Length of the longest balanced subarray found
139
140    nums.forEach((num, idx) => {
141        const i = idx + 1; // Convert to 1-based index
142        // Odd values contribute +1, even values contribute -1
143        const delta = num & 1 ? 1 : -1;
144
145        // If the value appeared before, cancel its previous contribution
146        if (lastIndex.has(num)) {
147            modify(1, lastIndex.get(num)!, n, -delta);
148            currentSum -= delta;
149        }
150
151        // Record the latest occurrence and add the new contribution
152        lastIndex.set(num, i);
153        modify(1, i, n, delta);
154        currentSum += delta;
155
156        // Find the leftmost position whose balance equals the current total;
157        // the subarray (position, i] is then balanced
158        const position = query(1, currentSum);
159        result = Math.max(result, i - position);
160    });
161
162    return result;
163}
164