Longest Balanced Subarray I

medium array hash table distinct count

Problem

Given an integer array nums, a subarray is balanced when its number of distinct even values equals its number of distinct odd values. Return the length of the longest balanced subarray.

Inputnums = [2, 5, 4, 3]

Output4

The whole array is balanced: distinct evens {2, 4} and distinct odds {5, 3} both have size 2, so the length is 4.

nums (comma-separated)

def longestBalanced(nums):
    n = len(nums)
    best = 0
    for i in range(n):                  # fix the left end
        even, odd = set(), set()        # distinct values seen
        for j in range(i, n):           # extend the right end
            if nums[j] % 2 == 0:
                even.add(nums[j])
            else:
                odd.add(nums[j])
            if len(even) == len(odd):   # balanced window
                best = max(best, j - i + 1)
    return best

function longestBalanced(nums) {
  const n = nums.length;
  let best = 0;
  for (let i = 0; i < n; i++) {        // fix the left end
    const even = new Set(), odd = new Set();
    for (let j = i; j < n; j++) {      // extend the right end
      if (nums[j] % 2 === 0) even.add(nums[j]);
      else odd.add(nums[j]);
      if (even.size === odd.size)       // balanced window
        best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

int longestBalanced(int[] nums) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {                 // fix the left end
        Set<Integer> even = new HashSet<>();
        Set<Integer> odd = new HashSet<>();
        for (int j = i; j < n; j++) {             // extend the right end
            if (nums[j] % 2 == 0) even.add(nums[j]);
            else odd.add(nums[j]);
            if (even.size() == odd.size())        // balanced window
                best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

int longestBalanced(vector<int>& nums) {
    int n = nums.size(), best = 0;
    for (int i = 0; i < n; i++) {                 // fix the left end
        unordered_set<int> even, odd;
        for (int j = i; j < n; j++) {             // extend the right end
            if (nums[j] % 2 == 0) even.insert(nums[j]);
            else odd.insert(nums[j]);
            if (even.size() == odd.size())        // balanced window
                best = max(best, j - i + 1);
        }
    }
    return best;
}

Explanation

A subarray is balanced when it holds exactly as many distinct even values as distinct odd values. We want the longest such window. With n ≤ 1500 a quadratic scan over all subarrays is fast enough, so we try every possible starting index.

We fix the left end i, then slide the right end j from i to the end of the array. As j advances we feed each new value into one of two sets: even if nums[j] is even, odd otherwise. Because they are sets, repeats are ignored automatically, so their sizes are exactly the distinct counts.

After adding each value we ask the only question that matters: is len(even) == len(odd)? When the two sizes are equal the window [i .. j] is balanced, and its length is j - i + 1. We keep the maximum of every balanced length we ever see in best.

Starting fresh for each i matters: a value that was a duplicate for one starting point can be the first occurrence for a later one, so the distinct counts must be rebuilt per start. Resetting the two sets at the top of the outer loop does exactly that.

For nums = [2, 5, 4, 3] the full array gives evens {2, 4} and odds {5, 3}, both size 2 — balanced with length 4, which is the answer. The empty answer 0 is the safe default when no window ever balances.

Time: O(n²) Space: O(n)