4047 Longest Balanced Subarray Ii
4047 Longest Balanced Subarray Ii
Longest Balanced Subarray II 
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:
1
2
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:
1
2
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:
1
2
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
2
1 <= nums.length <= 105
1 <= nums[i] <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
class LazyTag:
def __init__(self):
self.to_add = 0
def add(self, other):
self.to_add += other.to_add
return self
def has_tag(self):
return self.to_add != 0
def clear(self):
self.to_add = 0
class SegmentTreeNode:
def __init__(self):
self.min_value = 0
self.max_value = 0
self.lazy_tag = LazyTag()
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [SegmentTreeNode() for _ in range(self.n * 4 + 1)]
self._build(data, 1, self.n, 1)
def add(self, l, r, val):
tag = LazyTag()
tag.to_add = val
self._update(l, r, tag, 1, self.n, 1)
def find_last(self, start, val):
if start > self.n:
return -1
return self._find(start, self.n, val, 1, self.n, 1)
def _apply_tag(self, i, tag):
self.tree[i].min_value += tag.to_add
self.tree[i].max_value += tag.to_add
self.tree[i].lazy_tag.add(tag)
def _pushdown(self, i):
if self.tree[i].lazy_tag.has_tag():
tag = LazyTag()
tag.to_add = self.tree[i].lazy_tag.to_add
self._apply_tag(i << 1, tag)
self._apply_tag((i << 1) | 1, tag)
self.tree[i].lazy_tag.clear()
def _pushup(self, i):
self.tree[i].min_value = min(
self.tree[i << 1].min_value, self.tree[(i << 1) | 1].min_value
)
self.tree[i].max_value = max(
self.tree[i << 1].max_value, self.tree[(i << 1) | 1].max_value
)
def _build(self, data, l, r, i):
if l == r:
self.tree[i].min_value = data[l - 1]
self.tree[i].max_value = data[l - 1]
return
mid = l + ((r - l) >> 1)
self._build(data, l, mid, i << 1)
self._build(data, mid + 1, r, (i << 1) | 1)
self._pushup(i)
def _update(self, target_l, target_r, tag, l, r, i):
if target_l <= l and r <= target_r:
self._apply_tag(i, tag)
return
self._pushdown(i)
mid = l + ((r - l) >> 1)
if target_l <= mid:
self._update(target_l, target_r, tag, l, mid, i << 1)
if target_r > mid:
self._update(target_l, target_r, tag, mid + 1, r, (i << 1) | 1)
self._pushup(i)
def _find(self, target_l, target_r, val, l, r, i):
if self.tree[i].min_value > val or self.tree[i].max_value < val:
return -1
if l == r:
return l
self._pushdown(i)
mid = l + ((r - l) >> 1)
if target_r >= mid + 1:
res = self._find(target_l, target_r, val, mid + 1, r, (i << 1) | 1)
if res != -1:
return res
if l <= target_r and mid >= target_l:
return self._find(target_l, target_r, val, l, mid, i << 1)
return -1
class Solution:
def longestBalanced(self, nums: List[int]) -> int:
occurrences = defaultdict(deque)
def sgn(x):
return 1 if x % 2 == 0 else -1
length = 0
prefix_sum = [0] * len(nums)
prefix_sum[0] = sgn(nums[0])
occurrences[nums[0]].append(1)
for i in range(1, len(nums)):
prefix_sum[i] = prefix_sum[i - 1]
occ = occurrences[nums[i]]
if not occ:
prefix_sum[i] += sgn(nums[i])
occ.append(i + 1)
seg = SegmentTree(prefix_sum)
for i in range(len(nums)):
length = max(length, seg.find_last(i + length, 0) - i)
next_pos = len(nums) + 1
occurrences[nums[i]].popleft()
if occurrences[nums[i]]:
next_pos = occurrences[nums[i]][0]
seg.add(i + 1, next_pos - 1, -sgn(nums[i]))
return length
This post is licensed under CC BY 4.0 by the author.