June LunchTime Increasing Decreasing Problem

help
1

This is my approach where I use map as frequency table.
I checked cases when freq of element >3 and max element occurring twice.

I’ve looked accepted answers in C++ majorly use the same logic but uses frequency array instead of map. Can anyone point to me where my approach is going wrong?

 #include<bits/stdc++.h>
 using namespace std;
 int main() {
 int t;
 cin>>t;
 while(t--)
 {
     long long n;
     cin>>n;
     vector<long long> a(n);
     for(long long i=0;i<n;i++)
    cin>>a[i];
    map<long long,long long> h;
    bool flag=false;
    long long maxx=-INT_MAX;
    for(auto i:a)
    {   
        maxx=max(maxx,i);
        if(h.find(i)!=h.end())
        {
            h[i]+=1;
            if(h[i]>2)
            {
                cout<<"NO\n";
                flag=true;
                break;
            }
        }       
        else
            h[i]=1;
    }
    
    if(flag)
        continue;
    if(h[maxx]>1)
    {
        cout<<"NO\n";
        continue;
    }
    
        for(auto i:h)
        {
            cout<<i.first<<" ";
            h[i.first]--;        
        }
        for(auto i:h)
            if(h[i.first]==0)
                h.erase(i.first);
    
        if(!h.empty())
        { for(auto itr = h.rbegin(); itr != h.rend(); ++itr)
               cout<<itr->first<<" ";
        }    
    cout<<endl;
}
return 0;
}

`

2

Well, I used map… so my solution may help you…
https://www.codechef.com/viewsolution/34807834

1 Like
3

Thanks btw. Just a doubt, do u know if using map(which internally sorts indices) instead of unordered map will push time complexity to O(nlogn).

My soln in the 1st turn will print once in sort order as stored in map and for duplicate elements, I’ve used reverse iterator to print in descending order… Unless I see the test case, I don’t understand where it is going wrong…

4

Map is definitely more expensive than unordered_map and should be only used when ordering matters…
But I don’t think the constraints were large enough in this problem to affect the solution…