1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int maxBalancedSubarray(int[] nums) {
6        // Maps a combined "prefix state" to the earliest index at which it occurs.
7        // The state packs two prefix quantities into one long key.
8        Map<Long, Integer> firstIndexOfState = new HashMap<>();
9
10        int maxLength = 0;
11
12        // prefixXor: running XOR of all elements processed so far.
13        int prefixXor = 0;
14
15        // parityBalance: running count where each even number adds 1 and each odd
16        // number subtracts 1. It starts at nums.length as an offset so the value
17        // always stays non-negative and fits cleanly into the low 32 bits of the key.
18        int parityBalance = nums.length;
19
20        // Register the initial state (before processing any element) at index -1,
21        // so subarrays starting from index 0 can be measured correctly.
22        firstIndexOfState.put((long) parityBalance, -1);
23
24        for (int i = 0; i < nums.length; ++i) {
25            // Update the prefix XOR.
26            prefixXor ^= nums[i];
27
28            // Update the parity balance: +1 for even, -1 for odd.
29            parityBalance += nums[i] % 2 == 0 ? 1 : -1;
30
31            // Pack both quantities into a single long:
32            //   high 32 bits -> prefixXor
33            //   low  32 bits -> parityBalance
34            long stateKey = (1L * prefixXor << 32) | parityBalance;
35
36            // If this exact state was seen before, the subarray between the previous
37            // occurrence (exclusive) and the current index has a net-zero XOR
38            // contribution and an equal number of even and odd values -> balanced.
39            if (firstIndexOfState.containsKey(stateKey)) {
40                maxLength = Math.max(maxLength, i - firstIndexOfState.get(stateKey));
41            } else {
42                // Record only the first occurrence to maximize subarray length later.
43                firstIndexOfState.put(stateKey, i);
44            }
45        }
46
47        return maxLength;
48    }
49}
50

1class Solution {
2public:
3    int maxBalancedSubarray(vector<int>& nums) {
4        // Map from a packed state key to the earliest index where it occurred.
5        unordered_map<long long, int> firstIndex;
6        int answer = 0;
7
8        // prefixXor: running XOR of the elements in the prefix.
9        int prefixXor = 0;
10        // parityBalance: running count of (even count - odd count),
11        // initialized with an offset of nums.size() to keep it non-negative.
12        int parityBalance = static_cast<int>(nums.size());
13
14        // Record the base state before processing any element (index -1).
15        firstIndex[static_cast<long long>(parityBalance)] = -1;
16
17        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
18            // Update the running XOR.
19            prefixXor ^= nums[i];
20            // Even number contributes +1, odd number contributes -1.
21            parityBalance += (nums[i] % 2 == 0) ? 1 : -1;
22
23            // Pack both the XOR value and the parity balance into a single key:
24            // high 32 bits hold prefixXor, low 32 bits hold parityBalance.
25            long long key = (static_cast<long long>(prefixXor) << 32) | static_cast<unsigned int>(parityBalance);
26
27            if (firstIndex.contains(key)) {
28                // The same state seen before means the subarray in between is
29                // balanced (XOR == 0 and equal even/odd counts); update answer.
30                answer = std::max(answer, i - firstIndex[key]);
31            } else {
32                // Store the earliest index for this state.
33                firstIndex[key] = i;
34            }
35        }
36
37        return answer;
38    }
39};
40

1/**
2 * Finds the length of the longest "balanced" subarray, where a subarray is
3 * balanced when:
4 *   1. The XOR of all its elements equals 0 (equal prefix XOR at both ends).
5 *   2. It contains an equal number of even and odd values (equal parity balance).
6 *
7 * We track two prefix states simultaneously and pack them into a single bigint
8 * key. If the same combined state reappears at indices i and j (i < j), then the
9 * subarray (i, j] satisfies both conditions.
10 *
11 * @param nums - The input array of numbers.
12 * @returns The length of the longest balanced subarray.
13 */
14function maxBalancedSubarray(nums: number[]): number {
15    // Maps a packed (xorPrefix, parityBalance) state to the earliest index it occurred.
16    const stateToIndex = new Map<bigint, number>();
17
18    let maxLength = 0;
19    let xorPrefix = 0; // Running XOR of all elements seen so far.
20
21    // Running parity balance. Offset by nums.length so it never goes negative,
22    // keeping it cleanly within the low 32 bits of the packed key.
23    let parityBalance = nums.length;
24
25    // Record the initial state (before processing any element) at index -1.
26    stateToIndex.set(BigInt(parityBalance), -1);
27
28    for (let i = 0; i < nums.length; ++i) {
29        // Update the prefix XOR with the current element.
30        xorPrefix ^= nums[i];
31
32        // Even numbers add +1, odd numbers add -1 to the balance.
33        parityBalance += nums[i] % 2 === 0 ? 1 : -1;
34
35        // Pack both states into one key: XOR in the high bits, balance in the low bits.
36        const key = (BigInt(xorPrefix) << 32n) | BigInt(parityBalance);
37
38        if (stateToIndex.has(key)) {
39            // Same state seen before -> the subarray in between is balanced.
40            maxLength = Math.max(maxLength, i - stateToIndex.get(key)!);
41        } else {
42            // First occurrence of this state -> store its index.
43            stateToIndex.set(key, i);
44        }
45    }
46
47    return maxLength;
48}
49