LeetCode 3719: Longest Balanced Subarray I — Solution Guide

Problem recap

You’re given an integer array nums. A subarray is balanced if:

the number of distinct even values in the subarray
equals
the number of distinct odd values in the subarray.

Your task is to return the maximum length of any balanced subarray.

A key detail: distinct matters. For example, in [3, 2, 2, 5, 4], the distinct even numbers are {2, 4} (count = 2), not 3.

Constraints (important for choosing the approach):

1 <= nums.length <= 1500
1 <= nums[i] <= 10^5

Core idea

Because n <= 1500, we can afford an O(n²) approach:

Fix a left boundary i
Extend the right boundary j from i to n-1
Maintain:
- a set seen of values already present in the current subarray
- counts of distinct evens and odds

When we add a new value to seen, we update the appropriate distinct count.
If at any point distinct_even == distinct_odd, the subarray [i..j] is balanced, and we can update the answer.

This is exactly the “Hash Table + Enumeration” approach intended for this problem.

Why this works

For each starting index i, we examine every subarray that starts at i (i.e., [i..i], [i..i+1], …). While expanding:

seen ensures we count each value only once (so duplicates don’t inflate the distinct counts).
distinct_even and distinct_odd always represent the current subarray’s distinct parity counts.

Since we check all pairs (i, j), the maximum length found is the true answer.

Step-by-step algorithm

Initialize ans = 0
For each i in [0..n-1]:
- seen = set()
- cnt_even = 0, cnt_odd = 0
For each j in [i..n-1]:
- If nums[j] not in seen:
  - Add it to seen
  - Increment cnt_even if even else increment cnt_odd
- If cnt_even == cnt_odd, update ans = max(ans, j - i + 1)
Return ans

Python solution

from typing import List

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

        for i in range(n):
            seen = set()
            cnt_even = 0
            cnt_odd = 0

            for j in range(i, n):
                x = nums[j]
                if x not in seen:
                    seen.add(x)
                    if x % 2 == 0:
                        cnt_even += 1
                    else:
                        cnt_odd += 1

                if cnt_even == cnt_odd:
                    ans = max(ans, j - i + 1)

        return ans

This matches the expected longestBalanced(...) method signature commonly used for this problem.

Complexity

Time: O(n²) (two loops over i and j, with average O(1) set operations)
Space: O(n) (the seen set can grow up to the subarray size)

This is acceptable given n <= 1500.

Common pitfalls

Counting total evens/odds instead of distinct evens/odds.
You must track distinct values, so a set (or hash table) is necessary.
Forgetting to reset seen and counts for each new i.
Each left boundary starts a brand-new scan.