BudiBadu Logo

Longest Balanced Subarray

Array Easy 0 views
Like15

In a field experiment, some entries capture calm intervals (even numbers) while others reflect fluctuations (odd numbers). Your goal in Longest Balanced Subarray is to find the longest contiguous segment where these two states appear in Perfect Balance—meaning the number of even elements equals the number of odd elements.

The "secret sauce" here is a Prefix Difference Tracker. Treat each even number as a +1 and each odd number as a -1. As you walk the array, keep a running total of the balance. If you hit a balance value (like 3) that you've seen before at an earlier index, it means the section between those two points is perfectly balanced! By storing the first occurrence of each balance in a map, you can find the maximum length in a single O(n) pass. Negative numbers and duplicates follow the same parity logic. This allows the team to pinpoint the longest harmonized stretch in the lab data instantly! Return the length of that stretch as an integer.

Examples

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

The entire array has three evens and three odds, forming the longest balanced subarray.

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

There is no subarray where even and odd counts match.

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

The full array balances four even numbers with four odd numbers.

Algorithm Flow

Recommendation Algorithm Flow for Longest Balanced Subarray - Budibadu
Recommendation Algorithm Flow for Longest Balanced Subarray - Budibadu

Best Answers

java
import java.util.*;
class Solution {
    public int find_longest_balanced_segment(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++) {
            if (nums[i] > 0) current++;
            else if (nums[i] < 0) current--;
            else continue;
            if (map.containsKey(current)) maxLen = Math.max(maxLen, i - map.get(current));
            else map.put(current, i);
        }
        return maxLen;
    }
}