Maximum Length Balanced Parity Subarray — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, return the length of the longest contiguous subarray where the number of odd integers is equal to the number of even integers. If no such subarray exists, return 0.
Examples
Input
[3, 5, 8]
Output
1
Explanation: Step-by-step: Given the input [3, 5, 8], we first initialize two pointers, left and right, to the start of the array. We then iterate through the array, maintaining a count of odd and even numbers. When the count of odd numbers equals the count of even numbers, we update the maximum length of the subarray. In this case, the subarray [5, 8] has 2 odd integers and 1 even integer, but the subarray [3, 5, 8] has 2 odd integers and 2 even integers, which is the longest contiguous subarray where the number of odd integers is equal to the number of even integers. Therefore, the maximum length of the subarray is 1.
Input
[1, 2, 3, 4, 5, 6]
Output
0
Explanation: Step-by-step: Given the input [1, 2, 3, 4, 5, 6], we first initialize two pointers, left and right, to the start of the array. We then iterate through the array, maintaining a count of odd and even numbers. However, we find that there is no subarray where the number of odd integers is equal to the number of even integers. Therefore, the maximum length of the subarray is 0.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
Optimal Approach & Strategy
Transform the array into 1s for odd numbers and -1s for even numbers, then use a hash map to store the first occurrence of each running prefix sum. By calculating the difference between the current index and the index where this sum was first seen, we can find the longest subarray that sums to zero in O(n) time.
Brute Force Approach
Iterate through every possible subarray using nested loops, count the number of odd and even integers for each, and update the maximum length if the counts are equal. This approach has a time complexity of O(n^2).
Verified Code Solutions
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_lengthfunction 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
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.