Revision en2, by NAACDI, 2022-06-26 03:08:17

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 NAACDI 2022-06-26 03:08:17 0 (published)
en1 NAACDI 2022-06-26 03:00:33 725 Initial revision (saved to drafts)