mediumArraysPattern: Prefix Sum
Maximum Length Balanced Parity Subarray Solution
Problem Statement
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
Example 1:
Input:nums = [3, 5, 8, 2, 7]
Output:4
Explanation: The subarray [5, 8, 2, 7] contains two odd integers (5, 7) and two even integers (8, 2). The length is 4.
Example 2:
Input:nums = [1, 2, 3, 4, 6]
Output:4
Explanation: The subarray [1, 2, 3, 4] has two odd and two even integers, resulting in length 4.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
Time: O(n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def max_length_balanced_parity_subarray(nums):
seen = {0: -1}
max_len = 0
count = 0
for i, num in enumerate(nums):
count += 1 if num % 2 != 0 else -1
if count in seen:
max_len = max(max_len, i - seen[count])
else:
seen[count] = i
return max_len