You are given an integer array nums.

A subarray is a contiguous, non-empty sequence of elements within the array. A subarray is called balanced if the number of distinct even numbers in it is equal to the number of distinct odd numbers in it.

Your task is to return the length of the longest balanced subarray.

A few key points to keep in mind:

• Only distinct values are counted. For example, if the subarray is [2, 2, 3], the count of distinct even numbers is 1 (just the value 2), and the count of distinct odd numbers is also 1 (the value 3), so this subarray is balanced with length 3.
• The subarray must be contiguous — you cannot skip elements.
• If multiple balanced subarrays exist, you only need the length of the longest one.

Example:

For nums = [2, 2, 3]:

• The subarray [2, 3] has 1 distinct even number and 1 distinct odd number — balanced, length 2.
• The subarray [2, 2, 3] also has 1 distinct even and 1 distinct odd — balanced, length 3.

So the answer is 3.

The condition for a balanced subarray depends on distinct even and odd values, not just raw counts. This makes the problem tricky for classic tricks like prefix sums, because adding one more element to a subarray may or may not change the distinct counts — it depends on whether that value has already appeared inside the current window.

This observation points us toward a more direct strategy: since the "distinct" property is tied to a specific window's contents, the most natural way to handle it is to fix the left endpoint i and then extend the right endpoint j one step at a time. As the window grows to the right, elements are only ever added, never removed — and that's the key insight. When a window only grows, maintaining the set of seen values is easy:

• Keep a hash set vis of values already in the window.
• When nums[j] is new (not in vis), it contributes one new distinct value — increment either the even counter or the odd counter based on its parity (nums[j] & 1).
• When nums[j] is a repeat, the distinct counts don't change at all.

With a counter array cnt of size 2 tracking distinct evens (cnt[0]) and distinct odds (cnt[1]), checking whether the current window [i, j] is balanced becomes a constant-time comparison cnt[0] == cnt[1]. Whenever it holds, the window length j - i + 1 is a candidate for the answer.

By restarting the set and counters for every left endpoint, we examine all O(n^2) subarrays, but each extension step costs only O(1) amortized work thanks to the hash set. This brute-force-with-bookkeeping approach is simple, correct, and avoids the difficulty of trying to shrink a window (where removing an element would require knowing whether other copies of it still remain inside).

Pattern Learn more about Segment Tree, Divide and Conquer and Prefix Sum patterns.

Pattern used: Enumeration (brute force over left endpoints) + Hash Table for de-duplication.

We enumerate every possible left endpoint i, then extend the right endpoint j from i to the end of the array, maintaining the distinct counts incrementally as the window grows.

Step-by-step walkthrough:

1. Initialize the answer ans = 0 and let n be the length of nums.

2. Outer loop — fix the left endpoint i: For each i from 0 to n - 1, reset the bookkeeping structures:

   • cnt = [0, 0] — a counter array where cnt[0] is the number of distinct even values and cnt[1] is the number of distinct odd values in the current window.
   • vis = set() — a hash set storing all values already seen in the window [i, j].

3. Inner loop — extend the right endpoint j: For each j from i to n - 1:

   • New value check: If nums[j] is not in vis, it is a brand-new distinct value, so:
     • Increment the appropriate counter using its parity: cnt[nums[j] & 1] += 1. The bitwise trick nums[j] & 1 evaluates to 0 for even numbers and 1 for odd numbers, which maps directly to the index in cnt.
     • Add nums[j] to vis.
   • Repeat value: If nums[j] is already in vis, the distinct counts are unchanged, so we do nothing.
   • Balance check: If cnt[0] == cnt[1], the window [i, j] is balanced, so update the answer: ans = max(ans, j - i + 1).

4. Return ans after all pairs (i, j) have been considered.

Code:

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            cnt = [0, 0]
            vis = set()
            for j in range(i, n):
                if nums[j] not in vis:
                    cnt[nums[j] & 1] += 1
                    vis.add(nums[j])
                if cnt[0] == cnt[1]:
                    ans = max(ans, j - i + 1)
        return ans

Why this works: Every subarray of nums corresponds to exactly one pair (i, j) with i <= j, and the double loop visits all such pairs. Because the window only ever grows to the right for a fixed i, the hash set vis lets us detect duplicates in O(1) average time, keeping the counters exact at every step.

Complexity Analysis:

• Time complexity: O(n^2) — there are O(n^2) pairs (i, j), and each inner-loop step does only constant-time set lookup, insertion, and comparison.
• Space complexity: O(n) — the hash set vis can hold up to n distinct values in the worst case; cnt uses constant space.