🚀 Longest Balanced Subarray (Distinct Even = Distinct Odd)

Recently, I worked on an interesting array problem:

A subarray is called balanced if the number of distinct even numbers is equal to the number of distinct odd numbers. The task is to return the length of the longest such subarray.

At first glance, this looks like a simple parity count problem. Naturally, thoughts go toward prefix sums or sliding window techniques. But the real challenge lies in one word distinct.

We are not counting how many even or odd elements exist. We are counting how many unique even and unique odd values exist inside a subarray. That changes the entire strategy.

Distinct counts are not monotonic. If we shrink a window, removing one element might reduce the distinct count or it might not. That makes classic two pointer shrinking approaches unreliable here.

Given the constraint (n ≤ 1500), an O(n²) solution is fully acceptable and optimal.

💡 Approach

For every starting index:
• Expand the subarray to the right.
• Maintain a frequency map.
• Track two counters:
• evenDistinct
• oddDistinct
• Whenever both are equal, update the maximum length.

This guarantees correctness while staying within acceptable time complexity.

✅ Java Implementation
import java.util.*;

class Solution {
public int longestBalanced(int[] nums) {
int n = nums.length;
int maxLen = 0;

    for (int i = 0; i < n; i++) {
        Map<Integer, Integer> freq = new HashMap<>();
        int evenDistinct = 0;
        int oddDistinct = 0;

        for (int j = i; j < n; j++) {
            int num = nums[j];

            if (!freq.containsKey(num)) {
                freq.put(num, 1);
                if (num % 2 == 0) evenDistinct++;
                else oddDistinct++;
            } else {
                freq.put(num, freq.get(num) + 1);
            }

            if (evenDistinct == oddDistinct) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }

    return maxLen;
}

}
📊 Complexity
• Time Complexity: O(n²)
• Space Complexity: O(n)

🎯 My POV

This problem reminded me that not every array problem fits into the “optimize to O(n)” mindset. Sometimes, understanding constraints and choosing the correct strategy is more important than forcing a pattern.

The biggest lesson:
When you see words like distinct or unique, pause before applying sliding window blindly.

Strong problem-solving is not about memorising patterns it’s about recognising when patterns don’t apply.

That’s where real growth happens as a developer.