Skip to main content
Talentd

Longest Balanced Subarray I - Solution & Explanation

MediumArrayHash TableDivide and ConquerSegment Tree8 min readAsked at: Amazon, Intuit, Google +1
Practice this problem

Problem Statement

You are given an integer array nums.

A subarray is called balanced if the number of distinct even numbers in the subarray is equal to the number of distinct odd numbers.

Return the length of the longest balanced subarray.

 

Example 1:

Input: nums = [2,5,4,3]

Output: 4

Explanation:

  • The longest balanced subarray is [2, 5, 4, 3].
  • It has 2 distinct even numbers [2, 4] and 2 distinct odd numbers [5, 3]. Thus, the answer is 4.

Example 2:

Input: nums = [3,2,2,5,4]

Output: 5

Explanation:

  • The longest balanced subarray is [3, 2, 2, 5, 4].
  • It has 2 distinct even numbers [2, 4] and 2 distinct odd numbers [3, 5]. Thus, the answer is 5.

Example 3:

Input: nums = [1,2,3,2]

Output: 3

Explanation:

  • The longest balanced subarray is [2, 3, 2].
  • It has 1 distinct even number [2] and 1 distinct odd number [3]. Thus, the answer is 3.

 

Constraints:

  • 1 <= nums.length <= 1500
  • 1 <= nums[i] <= 105

Approach Overview

Problem Overview: You are given an array and need the length of the longest contiguous subarray that is balanced. A balanced subarray means the counts of the two target values (commonly 0 and 1) are equal. The task is to scan the array and return the maximum length of such a subarray.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

The direct way is to check every possible subarray. Use two nested loops: fix a starting index and extend the subarray one element at a time while counting the occurrences of both values. Each time the counts match, update the maximum length. This approach works because it evaluates all candidate ranges, but the nested iteration makes it quadratic. With arrays of size up to tens of thousands, O(n²) quickly becomes too slow.

Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)

The optimal solution uses a prefix sum transformation combined with a hash table. Convert the array so that one value contributes +1 and the other contributes -1. When a subarray contains equal counts, the total sum across that range becomes zero. Maintain a running prefix sum while iterating through the array. Store the first index where each prefix sum appears in a hash map.

If the same prefix sum appears again at index j after first appearing at i, the elements between them form a balanced subarray because the net contribution is zero. The length is j - i. Track the maximum length as you scan. Initializing the map with sum = 0 at index -1 allows balanced subarrays starting from index 0. This technique turns the problem into detecting equal prefix sums, which is why the lookup operation in the hash map is critical for achieving O(n) time.

This method is common in array problems involving equal counts or zero-sum ranges and builds directly on array traversal combined with prefix accumulation.

Recommended for interviews: Interviewers expect the prefix sum + hash map solution. Showing the brute force approach demonstrates you understand the definition of a balanced subarray, but the optimized O(n) solution proves you can recognize prefix-sum patterns and use constant-time hash lookups to eliminate nested loops.

Solution

We can enumerate the left endpoint i of the subarray, and then enumerate the right endpoint j from the left endpoint. During the enumeration process, we use a hash table vis to record the numbers that have appeared in the subarray, and use an array cnt of length 2 to record the count of distinct even numbers and distinct odd numbers in the subarray respectively. When cnt[0] = cnt[1], we update the answer ans = max(ans, j - i + 1).

The time complexity is O(n^2) and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Useful for understanding the problem or when input size is very small
Prefix Sum + Hash TableO(n)O(n)General case and expected interview solution for large arrays

Video Solution

Longest Balanced Subarray I | Simple Explanation | Leetcode 3719 | codestorywithMIK • codestorywithMIK • 12,323 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Balanced Subarray I easy or hard?
Longest Balanced Subarray I is typically rated Medium difficulty. The challenge is recognizing that equal counts can be transformed into a zero-sum problem using prefix sums and then solved efficiently with a hash map.
Longest Balanced Subarray I Python/Java solution
Implement the prefix sum + hash map approach. Track the running sum, store the first index of each sum in a dictionary or HashMap, and update the maximum subarray length whenever the same sum appears again.
How to solve Longest Balanced Subarray I in O(n)?
Use a prefix sum technique. Treat one value as +1 and the other as -1, maintain a running sum, and store the first occurrence of each sum in a hash map. When the same sum appears again, the subarray between the two indices has equal counts, giving a balanced subarray in linear time.
What is the best approach for Longest Balanced Subarray I?
The best approach uses a prefix sum combined with a hash map. Convert one value to +1 and the other to -1, then track the running sum while scanning the array. If the same prefix sum appears at two indices, the subarray between them is balanced. This solution runs in O(n) time with O(n) space.
Is Longest Balanced Subarray I asked at Google/Amazon/Meta?
Balanced subarray problems based on prefix sums and hash maps are common in interviews at companies like Amazon, Google, and Meta. Variants include finding equal numbers of 0s and 1s or the longest zero-sum subarray.
What data structure is used in Longest Balanced Subarray I?
The key data structure is a hash table (hash map) that stores the earliest index for each prefix sum. This allows constant-time lookup to determine whether the same sum has appeared before.
What is the time complexity of Longest Balanced Subarray I?
The optimal solution runs in O(n) time because the array is traversed once while performing constant-time hash map lookups. A naive brute force approach checks all subarrays and takes O(n²) time.

Ready to solve this problem?

Practice Longest Balanced Subarray I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays