C++ Solution using Map and List; Complexity(T, S): [O(capacity), O(capacity)]


#1

Both operations(Get() & Set()) have same complexities.

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

map<int, int> table;
list<int> recents;
int mxsize;

LRUCache::LRUCache(int capacity) 
{
    mxsize=capacity;
    recents.clear();
    table.clear();
}
int LRUCache::get(int key) 
{
    bool keyExists = (table.find(key)!=table.end());
    
    if(keyExists)
    {
        recents.remove(key);
        recents.push_front(key);
        return table[key];
    }
    else
        return -1;
}

void LRUCache::set(int key, int value) 
{
    bool keyExists = (table.find(key)!=table.end());
    if(keyExists)
    {
        recents.remove(key);
        recents.push_front(key);
    }
    else
    {
        if(recents.size()>=mxsize)
        {
            table.erase(recents.back());
            recents.pop_back();
        }
        
        recents.push_front(key);
    }
    
    table[key]=value;
}