Code Logo

Longest Balanced Parity Subarray

Published at05 Jan 2026
Created by
Array Manipulation Easy 3 views
Like19

This problem looks for the longest continuous part of the list where the number of even values and odd values is exactly the same. That is what balanced parity means here.

The answer in this file is not a length. From the examples, the answer should be the balanced subarray written out as text, with the numbers joined by commas. If no balanced subarray exists, the answer should be an empty string. So you need to find the best stretch first, then return it in the right output format.

For example, [2,4,1,3,6,8,5,7] is balanced all the way through because it has four even numbers and four odd numbers, so the whole range is returned. But [1,3,5,7] has only odd numbers, so there is no balanced subarray and the answer is "".

The key detail is that the chosen part must stay contiguous. You are not picking numbers from different places. You are searching for the longest unbroken stretch where even and odd counts match perfectly.

Example Input & Output

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

The entire array has three evens and three odds.

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

No contiguous subarray balances even and odd counts.

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

The full range contains four even and four odd numbers.

Algorithm Flow

Recommendation Algorithm Flow for Longest Balanced Parity Subarray

Solution Approach

This problem asks for the length of the longest contiguous subarray where the number of even values equals the number of odd values. Because the balance can be checked by treating evens as +1 and odds as -1, we can solve it efficiently with a prefix-sum technique.

The key insight: if two prefix sums are equal, then the subarray between them has a net sum of 0, which means an equal count of evens and odds. So we want the longest span between two equal prefix values.

Here is the implementation:

function longest_balanced_parity_subarray(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] % 2 === 0) ? 1 : -1;
        if (first.has(sum)) {
            best = Math.max(best, i - first.get(sum));
        } else {
            first.set(sum, i);
        }
    }
    return best;
}

We maintain a running sum where an even number adds 1 and an odd number subtracts 1. The map first records the earliest index where each prefix sum first appeared. We initialize it with 0 at index -1 so that a balanced subarray starting at the very beginning is counted correctly.

For each index, if the current sum has been seen before, the stretch from its first occurrence to the current index is balanced, and we update best. Otherwise we record this index as the first occurrence of that sum.

Let us trace [1, 3, 5, 7]. Every value is odd, so the sum only ever decreases and never returns to a previous value, meaning no balanced subarray exists and the answer is 0. For [1, 2, 3, 4], the whole array has two evens and two odds, so the sum returns to 0 at the end and the answer is 4.

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

Best Answers

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