3719. Longest Balanced Subarray I

Description

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.

What is a subarray?

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Example 2:

Example 3:

Approach

Now although in the question the constraints are pretty light and we can examine subarrays starting from each index, but recomputing each distinct count for every subarray would be very inefficient. Our approach could be,

1. We can fix an index, lets say i for the subarray.
2. We can now initialize two frequency maps -> (1) one for even numbers (2) one for odd numbers.
3. Now will also keep counters to check for distinct even and odd values.
4. We will now expand the subarray by moving the ending index j from i to the end of the array.
5. For each new element nums[j]: If it is even, update the even frequency map and increase the distinct even count if it appears for the first time. If it is odd, update the odd frequency map and increase the distinct odd count if it appears for the first time.
6. Now after each expansion, check whether the number of distinct even values equals the number of distinct odd values. If yes, update the maximum length of the balanced subarray.

We will repeat this process for all possible starting indices and return the maximum length found.

This avoids reprocessing entire subarrays and ensures the solution runs efficiently.

Code

Complexity Analysis

• Time Complexity: O(n^2) -> 2 nested loops to expand subarrays with each step updating count in constant time.
• Space Complexity: O(n) -> Frequency maps can store up to n distinct numbers in the worst case scenario.