Not Simple Solution. Giving TLE for Larger input. But have a look you wont be disappointed


#1
map<int,pair<int,int>> m;
class vec
{
    vector<pair<int,int>> v;
    static auto comp(pair<int,int> a , pair<int,int> b)
    {
    return a.second < b.second;
    }
public:


vec()
{
    
}

void push(pair<int,int> p)
{
    v.push_back(p);
    sort(v.begin(),v.end(),comp);
}

void pop()
{
    if(v.size()>0)
        v.erase(v.begin());
}
bool empty()
{
    return v.size()==0;
}
pair<int,int> top()
{
    return v[0];
}
void erase(pair<int,int> p)
{
    auto it = find(v.begin() , v.end(), p);
    if(it != v.end())
        v.erase(it);
}
};

vec pq;
int currTime=0;
int cap =0;
LRUCache::LRUCache(int capacity) 
{
    while(!pq.empty())
        pq.pop();
    m.clear();
    currTime=0;
    cap = capacity;
}

int LRUCache::get(int key) {
    if(m.find(key) != m.end())
    {
        currTime++;
        pq.erase({key,m[key].second});
        m[key].second = currTime;
        pq.push({key,currTime});
        return m[key].first;
    }
    else
        return -1;
}

void LRUCache::set(int key, int value) {
    if(m.find(key) != m.end())
    {
        currTime++;
        pq.erase({key,m[key].second});
        m[key].first = value;
        m[key].second = currTime;
        pq.push({key,currTime});
    }
    else if(m.size() < cap)
    {
        currTime++;
        m[key].first = value;
        m[key].second = currTime;
        pq.push({key,currTime});
    }
    else
    {
        currTime++;
        auto top = pq.top();pq.pop();
        m.erase(top.first);
        m[key].first = value;
        m[key].second = currTime;
        pq.push({key,currTime});
    }
}