Leetcode 146 Solution

This article provides solution to leetcode question 146 (lru-cache)

Tags:

Access this page by simply typing in "lcs 146" in your browser address bar if you have bunnylol configured.

Leetcode Question Link

Solution

class LRUCache {
    unordered_map<int, pair<int, list<int>::iterator>> m;
    list<int> last;

    int m_cap;
public:
    LRUCache(int capacity) {
        m_cap = capacity;
    }

    int get(int key) {
        auto it = m.find(key);

        if (it == m.end())
            return -1;

        last.erase(m[key].second);
        last.push_back(key);
        it->second.second = --last.end();

        return it->second.first;
    }

    void put(int key, int value) {
        int old_value = get(key);

        if (old_value != -1)
        {
            m[key].first = value;
            return;
        }

        if (m.size() == m_cap)
        {
            int key_to_delete = *last.begin();
            last.pop_front();
            m.erase(key_to_delete);
        }

        last.push_back(key);
        m[key] = make_pair(value, --last.end());
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */