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;
}
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.
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 #definefast 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;
}
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!
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 #definefast 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;
}
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.
Why am i getting TLE for this code using multiset?
I think the time complexity for my code is O(m*(logn)^2) which is sufficient to get passed but itās not.
int n,m;
cin >> n >> m;
multiset<int> M;
for(int i=0;i<n;i++){
int x;
cin >> x;
M.insert(x);
}
for(int i=0;i<m;i++){
int x;
cin >> x;
auto it = upper_bound(all(M),x);
if(it == M.begin()){
cout << -1 << endl;
}else{
--it;
cout << (*it) << endl;
M.erase(M.find((*it))); // to erase only one element
}
}