Olympiad Problem
Difference between en1 and en2, changed 0 character(s)
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).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NAACDI 2022-06-26 03:08:17 0 (published)
en1 English NAACDI 2022-06-26 03:00:33 725 Initial revision (saved to drafts)