Maximum Length Balanced Parity Subarray — Problem Statement & Solution Guide

ArraysMediumPrefix Sum

TimeO(N)

SpaceO(N)

Quick Answer & Algorithm Key Takeaway

Cumulative sum for range queries

TopicArrays

PatternPrefix Sum

TimeO(N)

SpaceO(N)

Problem Description

Given an array of integers, determine the maximum length of a contiguous segment in which the count of odd numbers equals the count of even numbers. If no such segment exists, the answer should be 0. The input consists of a single array, and the output is a single integer representing the desired length.

DSA Pattern Breakdown

"Maximum Length Balanced Parity Subarray"

medium

WHY DOES IT MATTER?

The prefix‑sum + hashmap pattern converts a global counting constraint into a local equality check, enabling constant‑time look‑ups for previously seen states. This pattern appears in many interview problems involving equal counts, target sums, or balanced partitions, making it a versatile tool in a developer's arsenal.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that equal odds and evens imply a net sum of zero after mapping, allowing us to replace an O(N^2) enumeration with a single pass that records the earliest index for each cumulative sum. This reduces both time and space from quadratic to linear.

REAL-WORLD CONNECTION

Consider a load balancer that tracks the difference between requests routed to two server pools. The moment the difference returns to a previously observed value, the interval between those two timestamps represents a period of perfectly balanced traffic—a direct analogue to the zero‑sum subarray detection.

During an interview, compute the transformed array on the fly while maintaining the running sum; don't create a separate array. Immediately check the hashmap for the current sum—this avoids extra passes and demonstrates in‑place thinking.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(N)

Core Theory — Why This Approach?

The problem reduces to finding the longest contiguous subarray where the number of odd elements equals the number of even elements. By mapping each odd number to +1 and each even number to -1 (or the opposite), the condition translates to locating the longest subarray whose transformed sum is zero. This transformation enables the use of prefix‑sum techniques: for each index we compute the cumulative sum of the mapped values; if the same cumulative sum reappears at a later index, the segment between those two indices has a net sum of zero, meaning equal odds and evens.

A naive double‑loop that checks every possible subarray would require O(N^2) time, which quickly becomes infeasible for N up to 10^5 or higher—common limits in coding interviews and production systems. The optimal paradigm leverages a hash map to store the earliest index at which each prefix sum occurs. As we scan the array once, we can instantly compute the length of a zero‑sum segment by subtracting the stored index from the current position, updating the maximum length when appropriate. This yields a linear‑time solution while using linear extra space for the map.

The approach exemplifies the broader class of "prefix sum + hashmap" patterns used to solve many subarray‑sum problems (e.g., longest subarray with sum K, subarrays with equal numbers of 0s and 1s). Recognizing that the parity balance can be expressed as a zero‑sum condition is the key insight that transforms an otherwise quadratic problem into an O(N) algorithm suitable for large inputs.

Interview Questions on This Problem

Q1How would you modify the solution if the requirement changed to finding the longest subarray where the count of numbers divisible by 3 equals the count of numbers not divisible by 3?

Map numbers divisible by 3 to +1 and others to -1, then apply the same prefix‑sum + hashmap technique. The core idea remains identical; only the mapping rule changes.

Q2Can you solve the problem in O(1) extra space while still running in linear time?

Only if the input range is limited (e.g., values are bounded) so that we can use an array instead of a hashmap for prefix‑sum indices. Otherwise, O(1) extra space is impossible because we need to remember first occurrences of potentially O(N) distinct prefix sums.

Q3Explain how you would extend the algorithm to handle multiple queries asking for the longest balanced parity subarray within different sub‑ranges of the original array.

Pre‑process the array to compute prefix sums and store them in a segment tree or binary indexed tree that can answer range‑minimum/maximum queries on prefix‑sum positions. Each query can then be answered in O(log N) by locating the farthest matching prefix sum within the query bounds.

Examples

Example 1

Input

[1,2,3,4,5,6]

Output

Explanation: The entire array contains three odd elements (1,3,5) and three even elements (2,4,6). Since the counts are equal, the longest balanced subarray spans the whole array, giving a length of 6.

Example 2

Input

[2,4,6,1,3]

Output

Explanation: All subarrays are examined: any subarray containing only even numbers has 0 odds, any subarray containing only odd numbers has 0 evens, and any mixed subarray has an unequal number of odds and evens. Therefore, no balanced subarray exists, and the result is 0.

Example 3

Input

[1,1,2,2,3,4,5,6]

Output

Explanation: Scanning the array, the subarray from index 2 to 5 (values 2,2,3,4) contains two evens (2,2,4) and two odds (3). This is the longest segment with equal parity counts, so the answer is 4.

Example 4

Input

[7,8,9,10,11,12,13]

Output

Explanation: The subarray [9,10,11,12] (indices 2–5) has two odds (9,11) and two evens (10,12). No longer subarray satisfies the balance condition, so the maximum length is 4.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
The array may contain positive, negative, or zero values

Optimal Approach & Strategy

Map odds to +1, evens to -1, compute prefix sums, and use a hash map to record the earliest index of each sum; the distance between repeated sums gives the length of a balanced segment, yielding O(N) time.

Brute Force Approach

Check every possible subarray, count odds and evens inside it, and keep the longest where the counts match. This requires two nested loops and O(N^2) time.

Code Solutions

Language:

JavaScript Solution

Time: O(N)

function maxLengthBalancedParitySubarray(nums) {
    let map = new Map();
    map.set(0, -1);
    let maxLength = 0, count = 0;
    for (let i = 0; i < nums.length; i++) {
        count += (nums[i] % 2 !== 0 ? 1 : -1);
        if (map.has(count)) {
            maxLength = Math.max(maxLength, i - map.get(count));
        } else {
            map.set(count, i);
        }
    }
    return maxLength === 0 ? 0 : 1;
}

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int maxLengthBalancedParitySubarray(std::vector<int>& nums) {
        std::unordered_map<int, int> seen;
        seen[0] = -1;
        int maxLength = 0, count = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            count += (nums[i] % 2 != 0 ? 1 : -1);
            if (seen.find(count) != seen.end()) {
                maxLength = std::max(maxLength, i - seen[count]);
            } else {
                seen[count] = i;
            }
        }
        return maxLength;
    }
};

class Solution {
    public int max_length_balanced_parity_subarray(int[] nums) {
        int max_length = 0;
        int left = 0;
        int odd_count = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 != 0) {
                odd_count++;
            }
            while (left <= right && odd_count > (right - left + 1 - odd_count)) {
                if (nums[left] % 2 != 0) {
                    odd_count--;
                }
                left++;
            }
            max_length = Math.max(max_length, right - left + 1);
        }
        return max_length;
    }
}

def max_length_balanced_parity_subarray(nums):
    max_length = 0
    left = 0
    odd_count = 0
    for right in range(len(nums)):
        if nums[right] % 2 != 0:
            odd_count += 1
        while left <= right and odd_count > (right - left + 1 - odd_count):
            if nums[left] % 2 != 0:
                odd_count -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

function maxLengthBalancedParitySubarray(nums) {
    let map = new Map();
    map.set(0, -1);
    let maxLength = 0, count = 0;
    for (let i = 0; i < nums.length; i++) {
        count += (nums[i] % 2 !== 0 ? 1 : -1);
        if (map.has(count)) {
            maxLength = Math.max(maxLength, i - map.get(count));
        } else {
            map.set(count, i);
        }
    }
    return maxLength === 0 ? 0 : 1;
}

Asked in Top Tech Interviews

PhonePe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.