Given an array of size n, with elements between 1 and n find the maximum number of elements that occur exactly twice in any subarray. Constraints (1 <= n <= 100000)↵
↵
~~~~~↵
6↵
1 3 1 3 2 1↵
Output: 2 (subarray 1-4, 1-5)↵
↵
12↵
5 5 1 3 9 9 9 1 3 5 2 1↵
Output: 3 (subarray 1-9, 2-10, 2-11)↵
~~~~~↵
↵
I have partial points, running O(n^2) solution shown below.↵
↵
~~~~~↵
int ans = 0;↵
for(int i = 0; i < n; i++){↵
map<int,int> cnt;↵
int cans = 0;↵
for(int j = i; j < n; j++){↵
cnt[arr[j]]++;↵
if(cnt[arr[j]] == 2)↵
cans++;↵
else if(cnt[arr[j]] == 3)↵
cans--;↵
↵
ans = max(ans, cans);↵
}↵
}↵
cout<<ans<<endl;↵
~~~~~↵
↵
Any ideas how to solve the problem in O(n log n).
↵
~~~~~↵
6↵
1 3 1 3 2 1↵
Output: 2 (subarray 1-4, 1-5)↵
↵
12↵
5 5 1 3 9 9 9 1 3 5 2 1↵
Output: 3 (subarray 1-9, 2-10, 2-11)↵
~~~~~↵
↵
I have partial points, running O(n^2) solution shown below.↵
↵
~~~~~↵
int ans = 0;↵
for(int i = 0; i < n; i++){↵
map<int,int> cnt;↵
int cans = 0;↵
for(int j = i; j < n; j++){↵
cnt[arr[j]]++;↵
if(cnt[arr[j]] == 2)↵
cans++;↵
else if(cnt[arr[j]] == 3)↵
cans--;↵
↵
ans = max(ans, cans);↵
}↵
}↵
cout<<ans<<endl;↵
~~~~~↵
↵
Any ideas how to solve the problem in O(n log n).
