Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Balance here compares the numbers of distinct even and distinct odd values, not their total occurrences. Sets capture that distinction: repeating a value does not change its side's distinct count. The smaller constraints permit enumerating all subarrays.

Approach

For every starting index, initialize empty even and odd sets. Extend the right endpoint one position at a time and insert the new value into the set matching its parity. Whenever the two set sizes are equal, update the longest balanced length with the current subarray length.

Return the largest length found, leaving zero if none qualifies. Resetting the sets for each new start ensures they describe exactly the current subarray. Since every start/end pair is tested, a balanced region is never missed, even when its frequencies are highly uneven but its distinct parity counts match.

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        for i in range(n):
            e = set()
            o = set()

            for j in range(i, n):
                if nums[j] % 2 == 0:
                    e.add(nums[j])
                else:
                    o.add(nums[j])
                if len(o) == len(e):
                    res = max(res, j - i + 1)

        return res

Complexity analysis

Let n = nums.length. Time: O(n^2). Auxiliary space: O(n) for distinct even/odd sets.