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.

Description Hints 2 Solution Video 12:31

3719. Longest Balanced Subarray I

Medium65.6% acceptance4 companies

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] <= 10⁵

Asked at 4 companies

Intuit Bloomberg

Google Amazon

Topics

Hints open one at a time

Hint 1

Use brute force

Hint 2

Try every subarray and use a map/set data structure to track the distinct even and odd numbers

12:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestBalanced(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,5,4,3]

Input

[3,2,2,5,4]

Input

[1,2,3,2]

Your code is saved on this device.Solution