4033. Valid K-Unique Subarrays I
You are given an integer array nums and an integer k.
You are also given a 2D integer array queries, where queries[i] = [l_i, r_i] represents the subarray nums[l_i..r_i].
For each query, the subarray nums[l_i..r_i] is considered valid if:
- It contains exactly
k distinct numbers, and
- The frequency of every number in the subarray is even.
Return a boolean array ans, where ans[i] is true if nums[l_i..r_i] is valid, and false otherwise.
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
|
struct Counter {
unordered_map<int,int> mp;
int odds = 0;
void update(int x, int op) {
mp[x] += op;
if(mp[x] & 1) odds++;
else odds--;
if(mp[x] == 0) mp.erase(x);
}
bool ok(int k) {
if(mp.size() != k) return false;
return !odds;
}
};
class Solution {
public:
vector<bool> validSubarrays(vector<int>& nums, int k, vector<vector<int>>& queries) {
Counter c;
vector<array<int,3>> Q;
vector<int> counts{0};
unordered_set<int> us;
for(int i = 0; i < nums.size(); i++) {
us.insert(nums[i]);
counts.push_back(us.size());
}
for(int i = 0; i < queries.size(); i++) {
int l = queries[i][0], r = queries[i][1];
int len = r - l + 1;
if(len & 1) continue;
if(len < 2 * k) continue;
if(counts[r+1] - counts[l] > k) continue;
if(len % k) continue;
Q.push_back({l, r, i});
}
int sq = sqrt(queries.size());
sort(begin(Q), end(Q), [&](auto& a, auto& b) {
int asq = a[0] / sq, bsq = b[0] / sq;
if (asq == bsq) {
return a[1] < b[1];
}
return asq < bsq;
});
vector<bool> res(queries.size());
int l = 0, r = 0;
for(auto& [le,ri,idx] : Q) {
while(r <= ri) c.update(nums[r++],1);
while(l > le) c.update(nums[--l], 1);
while(r > ri + 1) c.update(nums[--r],-1);
while(l < le) c.update(nums[l++], -1);
res[idx] = c.ok(k);
}
return res;
}
};
|
