Skip to content

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.

 

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

Solutions

Solution 1: Hash Table + Enumeration

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 \(\textit{vis}\) to record the numbers that have appeared in the subarray, and use an array \(\textit{cnt}\) of length \(2\) to record the count of distinct even numbers and distinct odd numbers in the subarray respectively. When \(\textit{cnt}[0] = \textit{cnt}[1]\), we update the answer \(\textit{ans} = \max(\textit{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 \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            cnt = [0, 0]
            vis = set()
            for j in range(i, n):
                if nums[j] not in vis:
                    cnt[nums[j] & 1] += 1
                    vis.add(nums[j])
                if cnt[0] == cnt[1]:
                    ans = max(ans, j - i + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestBalanced(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            Set<Integer> vis = new HashSet<>();
            int[] cnt = new int[2];
            for (int j = i; j < n; ++j) {
                if (vis.add(nums[j])) {
                    ++cnt[nums[j] & 1];
                }
                if (cnt[0] == cnt[1]) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            unordered_set<int> vis;
            int cnt[2]{};
            for (int j = i; j < n; ++j) {
                if (!vis.contains(nums[j])) {
                    vis.insert(nums[j]);
                    ++cnt[nums[j] & 1];
                }
                if (cnt[0] == cnt[1]) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func longestBalanced(nums []int) (ans int) {
    n := len(nums)
    for i := 0; i < n; i++ {
        vis := map[int]bool{}
        cnt := [2]int{}
        for j := i; j < n; j++ {
            if !vis[nums[j]] {
                vis[nums[j]] = true
                cnt[nums[j]&1]++
            }
            if cnt[0] == cnt[1] {
                ans = max(ans, j-i+1)
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function longestBalanced(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const vis = new Set<number>();
        const cnt: number[] = Array(2).fill(0);
        for (let j = i; j < n; ++j) {
            if (!vis.has(nums[j])) {
                vis.add(nums[j]);
                ++cnt[nums[j] & 1];
            }
            if (cnt[0] === cnt[1]) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
}

Comments