Simple solution using map and list


#1

#include
list dq;
map<int,int> m;
int s;

LRUCache::LRUCache(int capacity) {

s = capacity;
dq.clear();
m.clear();

}

int LRUCache::get(int key) {

if(m.find(key)!=m.end())
{
    dq.remove(key);
    dq.push_back(key);
    return m[key];
}

else
{
    return -1;
}

}

void LRUCache::set(int key, int value) {

if(dq.size()==s)
{
    if(m.find(key)!=m.end())
    {
        dq.remove(key);
        dq.push_back(key);
        m[key] = value;
    }
    
    else
    {
        m.erase(dq.front());
        dq.pop_front();
        dq.push_back(key);
        m[key] = value;
        //cout<<"aaaaa";
    }
}

else
{
    if(m.find(key)!=m.end())
    {
        dq.remove(key);
        dq.push_back(key);
        m[key] = value;
    }
    else
    {
        dq.push_back(key);
        m[key] = value;
        
    }
    
}

}


#2

Hey can you tell me the time complexcity of your code thank you.


#3

Complexity

  • Time
    Worst case: O(capacity)
    Best case: O(log(capacity))

  • Space: O(capacity)