3719. Longest Balanced Subarray I

Array
Hash Table
Brute Force

TIME

O(n²)

SPACE

O(n)

Intuition

For each starting index, expand the subarray while tracking distinct even and odd numbers. When counts are equal, we have a balanced subarray.

Solution

Enumerate all subarrays: For each starting index i, expand j from i to n-1.
Track distinct evens and odds: Use two sets to track distinct even and odd numbers in current subarray.
Check balance condition: When len(even) == len(odd), update max length.
Return maximum: The longest balanced subarray found.

Why Brute Force Works

Constraint is small: n <= 1500
O(n²) with O(n) set operations per subarray is acceptable
Total: O(n²) iterations, each with O(1) amortized set operations

Complexity

Time: O(n²), enumerate all subarrays
Space: O(n), sets can hold up to n distinct elements

Edge Cases

All even or all odd → return 0 (no balanced subarray possible)
Single element → return 0
Alternating even/odd → likely the entire array is balanced

Code

from typing import List


class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        """
        3719. Longest Balanced Subarray I
        Time: O(n²)
        Space: O(n)
        """
        n = len(nums)
        ans = 0

        for i in range(n):
            even = set()
            odd = set()

            for j in range(i, n):
                if nums[j] % 2 == 0:
                    even.add(nums[j])
                else:
                    odd.add(nums[j])

                if len(even) == len(odd):
                    ans = max(ans, j - i + 1)

        return ans

import java.util.HashSet;
import java.util.Set;

/**
 * 3719. Longest Balanced Subarray I
 * Time: O(n²)
 * Space: O(n)
 */
class Solution {
    public int longestBalancedSubarray(int[] nums) {
        int n = nums.length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            Set<Integer> even = new HashSet<>();
            Set<Integer> odd = new HashSet<>();

            for (int j = i; j < n; j++) {
                if (nums[j] % 2 == 0) {
                    even.add(nums[j]);
                } else {
                    odd.add(nums[j]);
                }

                if (even.size() == odd.size()) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }

        return ans;
    }
}