Olympiad Problem

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