Help in CSES Problem Playlist

[skankhunt_42]

I am trying to solve the CSES Playlist problem.

https://cses.fi/problemset/task/1141/

I was thinking of a solution with using sets, as given in the code below.
It giving WA for 2 cases. But as this problem comes under Sorting and Searching, I have a feeling as there might be better solutions for this.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
ll n;
cin >> n;
set<ll> elm;
ll ans = 0, length = 0;
for (ll i = 0; i < n; i++)
{
    int temp;
    cin >> temp;
    int size1 = elm.size();
    elm.insert(temp);
    if (elm.size() > size1)
    {
        length = elm.size();
        ans = max(ans, length);
    }
    else
    {
        elm.clear();
        elm.insert(temp);
    }
}
cout << ans;
return 0;
}

Can someone please help out ?

[aayush_84719]

Your code fails for such input :
10
1 2 3 4 1 5 6 7 8 9
Your answer : 6 (the last six elements)
Correct answer : 9 (the last nine elements)
One way to solve this question is using set and two pointer.

[skankhunt_42]

Yeah, I got my mistake. Trying again using two pointers. Thanks for pointing out.

[zephxr]

@skankhunt_42 I was also stuck at this problem.Applied many approaches but then i landed on geeksforgeeks.

Click Here - Understand the O(n) Algorithm and then write the code you will get AC.

You can check my solution too-My Solution
Hope it Helped!

[skankhunt_42]

Thank you !! I was too facing difficulty implementing this.

[ay2306]

I used a simple DP approach. Though normal unordered_map will not work but declaring some initial size smoothen things out to run it in 0.1 s

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int n,ans,arr[N],dp[N];

int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)scanf("%d",arr+i);
	unordered_map<int,int> m(1 << 12);
	for(int i = 1; i <= n; ++i){
		if(!m.count(arr[i]))m[arr[i]]= -1;
		dp[i] = max(ans,min(dp[i-1]+1,i-m[arr[i]]));
		m[arr[i]] = i;
	}	
	return printf("%d",*max_element(dp+1,dp+n+1)),0;
}

[varun_man2810]

Hey Can you help in my Code, I am getting WA but don’t know on which Test Cases?
#include <bits/stdc++.h>
using namespace std;
#define endl ‘\n’
#define int long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int solve(vector &arr, int n)
{
int ans = -1e18;
deque dq;
unordered_map<int,int> hashMap;
for(int i=0; i<n; i++)
{
if(hashMap[arr[i]]==0)
{
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
else
{
ans = max(ans,(int)dq.size());
while(!dq.empty() and hashMap[arr[i]]!=0)
{
intf = dq.front();
if(f==arr[i])
{
hashMap[arr[i]] = 0;
dq.pop_front();
continue;
}
dq.pop_front();
}
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
}
if(!dq.empty()) ans = max(ans,(int)dq.size());
return ans;
}

int32_t main()
{
fast;
int n; cin >> n;
vector arr(n);
for(int i=0; i<n; i++) cin >> arr[i];
cout << solve(arr,n) << endl;
return 0;
}

[zephxr]

Hi,
You can see where you are getting WA on CSES (just Scroll down on the page where you submitted your code).

I was also doing the approach like you did but it failed. Later On, I searched on GeeksForGeeks and i concluded that approach i was applying previously was not able to run on all test cases Correctly.

But GeekForGeeks’s Solution is Simple.

You can view the following solutions and you will surely understand it!

My Solution- Click Here
GeeksForGeeks link-Click Here

[varun_man2810]

Hi,
I found where I am getting WA but now I am getting TLE but same logic is passing on Leetcode and GeeksForGeeks Platform, can you help in finding what is its Time Complexity, I think it is O(2n).
#include <bits/stdc++.h>
using namespace std;
#define endl ‘\n’
#define int long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int32_t main()
{
fast;
int n; cin >> n;
vector arr(n);
for(int i=0; i<n; i++) cin >> arr[i];
int ans = -1e18;
deque dq;
unordered_map<int,int> hashMap;
for(int i=0; i<n; i++)
{
if(hashMap[arr[i]]==0)
{
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
else
{
ans = max(ans,(int)dq.size());
while(!dq.empty() and hashMap[arr[i]]!=0)
{
int f = dq.front();
if(f==arr[i])
{
hashMap[arr[i]] = 0;
dq.pop_front();
continue;
}
dq.pop_front();
hashMap[f] = 0;
}
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
}
if(!dq.empty()) ans = max(ans,(int)dq.size());
cout << ans << endl;
return 0;
}

[zephxr]

Just change “unordered_map” to “map”.
As Worst case complexity of Unordered map is O(n) , Best is O(1)
Map’s Complexity is O(Logn) Throughout.

[varun_man2810]

Thank you so much, it worked!!

[zephxr]

Glad it Helped and surprisingly we both are From Same University!

[piyush_111]

bro could u tell why unordered map work fast when initialized with size

[ay2306]

I don’t know exactly but since reason for slow HashMaps are collisions so I think, it is in that direction somewhere.

[ak4713]

You can track occurences of each element using a map and then keep two pointers at the ends of distinct segment.

My solution

#include<bits/stdc++.h>
    using namespace std;
    int main(void){
    	int n,i,j;
    	cin>>n;
    	int a[n];
    	for(i=0;i<n;i++)
    	cin>>a[i];
    	int l=0,r=0,ans=0;
    	map<int,int>mp1;//counting occurence
    	map<int,int>mp2;//setting positions
    	for(i=0;i<n;i++){
    		mp1[a[i]]++;
    		if(mp1[a[i]]==1){
    			mp2[a[i]]=i;
    			r=i;
    		}
    		else{
    			for(j=l;j<=mp2[a[i]];j++)
    			mp1[a[j]]--;
    			l=mp2[a[i]]+1;
    			r=i;
    			mp2[a[i]]=i;
    		}
    		ans=max(ans,r-l+1);
    	}
    	cout<<ans;
    }

PS:Sorry for my English.