Longest Balanced Parity Subarray

Published atDate not available

Array Easy 0 views

Like0

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

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

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;
    }
}

javascript

function longest_balanced_parity_subarray(nums) {
    const sumMap = {0: -1};
    let maxLen = 0, current = 0;
    for (let i = 0; i < nums.length; i++) {
        current += (nums[i] % 2 === 0) ? 1 : -1;
        if (current in sumMap) maxLen = Math.max(maxLen, i - sumMap[current]);
        else sumMap[current] = i;
    }
    return maxLen;
}

php

function longest_balanced_parity_subarray($nums) {
    $sumMap = [0 => -1];
    $maxLen = 0; $current = 0;
    foreach ($nums as $i => $x) {
        $current += ($x % 2 == 0) ? 1 : -1;
        if (isset($sumMap[$current])) $maxLen = max($maxLen, $i - $sumMap[$current]);
        else $sumMap[$current] = $i;
    }
    return $maxLen;
}

python

def longest_balanced_parity_subarray(nums: list) -> int:
    sum_map = {0: -1}
    max_len = 0
    current = 0
    for i, x in enumerate(nums):
        current += 1 if x % 2 == 0 else -1
        if current in sum_map:
            max_len = max(max_len, i - sum_map[current])
        else: sum_map[current] = i
    return max_len

rust

use std::collections::HashMap;
pub fn longest_balanced_parity_subarray(nums: Vec<i32>) -> i32 {
    let mut map = HashMap::new();
    map.insert(0, -1);
    let mut max_len = 0;
    let mut current = 0;
    for (i, &x) in nums.iter().enumerate() {
        current += if x % 2 == 0 { 1 } else { -1 };
        if let Some(&prev) = map.get(&current) {
            max_len = std::cmp::max(max_len, i as i32 - prev);
        } else {
            map.insert(current, i as i32);
        }
    }
    max_len
}

typescript

function longest_balanced_parity_subarray(nums: number[]): number {
    const sumMap: {[key: number]: number} = {0: -1};
    let maxLen = 0, current = 0;
    for (let i = 0; i < nums.length; i++) {
        current += (nums[i] % 2 === 0) ? 1 : -1;
        if (current in sumMap) maxLen = Math.max(maxLen, i - sumMap[current]);
        else sumMap[current] = i;
    }
    return maxLen;
}

Related Array Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Longest Balanced Parity Subarray

Example Input & Output

Algorithm Flow

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Array Challenges

Longest Alternating Parity Subarray

Longest Balanced Subarray

Missing Seat Number

Running Sum of Purchases

Sum of Unique Elements

Maximum Product Subarray

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.