Code Logo

Longest Balanced Subarray

Published at05 Jan 2026
Created by
Array Manipulation Easy 9 views
Like15

This problem asks for the length of the longest continuous part of the list where the number of even values and odd values is equal. That balanced stretch can begin anywhere and end anywhere, as long as the numbers stay together in one unbroken subarray.

The answer is just a number showing how long the best balanced subarray is. If the whole list has the same number of evens and odds, then the answer is the full length of the list. If there is no balanced subarray at all, the answer should be 0.

For example, [2,5,6,3,4,7] has three evens and three odds, so the whole list is balanced and the answer is 6. But [1,3,5,7] has only odd numbers, so there is no balanced subarray and the answer is 0.

The important part is that you are counting evens and odds inside continuous stretches, not inside random picks from the list. You are searching for the longest valid range, not just any valid range.

Example Input & Output

Example 1
Input
nums = [2,5,6,3,4,7]
Output
6
Explanation

The entire array has three evens and three odds, forming the longest balanced subarray.

Example 2
Input
nums = [1,3,5,7]
Output
0
Explanation

There is no subarray where even and odd counts match.

Example 3
Input
nums = [2,4,1,3,6,8,5,7]
Output
8
Explanation

The full array balances four even numbers with four odd numbers.

Algorithm Flow

Recommendation Algorithm Flow for Longest Balanced Subarray

Solution Approach

This problem asks for the length of the longest contiguous subarray with an equal number of 0s and 1s. We can transform each 0 into -1 and each 1 into +1, turning the problem into finding the longest subarray whose prefix-sum difference is zero.

The key insight is that two equal prefix sums enclose a subarray with net sum 0, meaning an equal count of zeros and ones. So we look for the longest span between two equal prefix values using a hash map.

Here is the implementation:

function find_longest_balanced_segment(arr) {
    const first = new Map();
    first.set(0, -1);
    let sum = 0, best = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += (arr[i] === 0) ? -1 : 1;
        if (first.has(sum)) {
            best = Math.max(best, i - first.get(sum));
        } else {
            first.set(sum, i);
        }
    }
    return best;
}

We keep a running sum where a 0 subtracts 1 and a 1 adds 1. The map first stores the earliest index for each prefix sum, seeded with 0 at index -1. Whenever the current sum has been seen before, the subarray between the two occurrences is balanced, and we track the longest such span.

Let us trace [0, 1, 0, 1]. The sums are -1, 0, -1, 0. The first time we hit 0 is at index 1, giving span 1 - (-1) = 2, and again at index 3 giving 3 - (-1) = 4, so the answer is 4. For [1, 1, 1], the sum keeps increasing and never repeats, so the answer is 0.

The time complexity is O(n) and the space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int find_longest_balanced_segment(int[] nums) {
        Map<Integer,Integer> first = new HashMap<>();
        first.put(0, -1);
        int prefix = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix += (nums[i] % 2 == 0) ? 1 : -1;
            if (first.containsKey(prefix)) {
                best = Math.max(best, i - first.get(prefix));
            } else {
                first.put(prefix, i);
            }
        }
        return best;
    }
}