O(1) accepted C++ solution, 272 ms


  • 0
    V

    Hashtable + doubly-linked list -- all operations are O(1) expected time. Highly optimized code: minimal memory allocations, minimal copying.

    struct my_pair {
    	int key, value;
    	my_pair(int k, int v) : key(k), value(v) {}
    };
    
    class LRUCache {
    
    public:
    
    	LRUCache(int capacity) : capacity(capacity) {
    		pair_map.reserve(capacity);
    	}
    	
    	int get(int key) {
    		auto it = pair_map.find(key);
    		if (it == pair_map.end()) {
    			return -1;
    		}
    		list_type::iterator list_it = it->second;
    		update_freshness(list_it);
    		//cout << "get(" << key << ") = " << it->second->second << endl;
    		return list_it->value;
    	}
    	
    	void set(int key, int value) {
    		//cout << "set(" << key << ", " << value << ")" << endl;
    		auto it = pair_map.find(key);
    		if (it != pair_map.end()) {
    			// key already in cache, update it and return
    			list_type::iterator list_it = it->second;
    			list_it->value = value;
    			update_freshness(list_it);
    			return;
    		}
    
    		// new key-value pair, insert it
    		if (pair_map.size() == capacity) {
    			invalidate_lru();
    		}
    		pair_list.emplace_front(my_pair(key, value));   // O(1)
    		pair_map.emplace(make_pair(key, pair_list.begin()));
    	}
    	
    private:
    
    	typedef list<my_pair> list_type;
    	typedef unordered_map<int,list_type::iterator> map_type;
    
    	const int capacity;
    	list_type pair_list;
    	map_type pair_map;
    
    	void invalidate_lru() {
    		auto pair = pair_list.back();   // O(1)
    		//cout << "invalidating (" << pair.first << ", " << pair.second << ")" << endl;
    		// remove least recently used element
    		pair_map.erase(pair.key);  // O(1)
    		pair_list.pop_back();    // O(1)
    	}
    
    	void update_freshness(list_type::iterator it) {
                        // runtime error with std::swap in some cases, don't know why
    		//std::swap(*it, const_cast<my_pair&>(*(pair_list.begin())));
    		pair_list.emplace_front(*it);
    		list_type::iterator it_new = pair_list.begin();
    		pair_map[it->key] = it_new;
    		pair_list.erase(it);
    	}
    	
    };

  • 0
    J

    Can you give more notes about your optimization? :-$ My solution is very similar to yours, but it is just ~250ms slower even if I use own struct for pairs.

    class LRUCache{
    private:
        typedef list<pair<int, int>> plist;
        int capacity_;
        plist pairs_;  // (key, value)
        unordered_map<int, plist::iterator> its_;  // key -> &pair
        void touch(plist::iterator it) {
            pairs_.erase(it);
            pairs_.emplace_front(it->first, it->second);
            its_[it->first] = pairs_.begin();
        }
    public:
        LRUCache(int capacity) {
            capacity_ = capacity;
            its_.reserve(capacity);
        }
        int get(int key) {
            auto it = its_.find(key);
            if (it != its_.end()) {
                int value = it->second->second;
                touch(it->second);
                return value;
            }
            return -1;
        }
        void set(int key, int value) {
            auto it = its_.find(key);
            if (it == its_.end()) {
                if (pairs_.size() == capacity_) {
                    int oldestKey = pairs_.back().first;
                    its_.erase(oldestKey);
                    pairs_.pop_back();
                }
                pairs_.emplace_front(key, value);
                its_[key] = pairs_.begin();
            } else {
                it->second->second = value;
                touch(it->second);
            }
        }
    };
    

  • 0
    V

    Is your code getting AC? Because in the touch(...) function you're using the iterator after you've erased it -- erasing it invalidates the iterator. See the Iterator validity section in the documentation for std::list::erase.


  • 0
    J

    Yes, it got AC. Thank you. I've corrected my code, but it still takes ~520ms.

    class LRUCache {
    private:
        typedef list<pair<int, int>> plist;
        int capacity_;
        plist pairs_;  // (key, value)
        unordered_map<int, plist::iterator> its_;  // key -> &pair
        void touch(plist::iterator it) {
            pairs_.emplace_front(it->first, it->second);
            its_[it->first] = pairs_.begin();
            pairs_.erase(it);
        }
    public:
        LRUCache(int capacity) {
            capacity_ = capacity;
            its_.reserve(capacity);
        }
        int get(int key) {
            auto it = its_.find(key);
            if (it == its_.end()) return -1;
            int value = it->second->second;
            touch(it->second);
            return value;
        }
        void set(int key, int value) {
            auto it = its_.find(key);
            if (it == its_.end()) {
                if (pairs_.size() == capacity_) {
                    int oldestKey = pairs_.back().first;
                    pairs_.pop_back();
                    its_.erase(oldestKey);
                }
                pairs_.emplace_front(key, value);
                its_[key] = pairs_.begin();
                return;
            }
            it->second->second = value;
            touch(it->second);
        }
    };
    

  • 0
    J

    Still don't know why, but I borrowed another idea from another post. Finally 260ms :)

    class LRUCache {
    private:
        typedef list<int> Keys;
        typedef pair<int, Keys::iterator> Pair;  // (value, &key)
        typedef unordered_map<int, Pair> Map;  // key -> (value, &key)
        int capacity_;
        Keys keys_;
        Map pairs_;
        Keys::iterator touch(Keys::iterator it) {
            keys_.push_front(*it);
            keys_.erase(it);
            return keys_.begin();
        }
    public:
        LRUCache(int capacity) : capacity_(capacity) {
            pairs_.reserve(capacity);
        }
        int get(int key) {
            auto it = pairs_.find(key);
            if (it == pairs_.end()) return -1;
            auto &pair = it->second;
            pair.second = touch(pair.second);
            return pair.first;
        }
        void set(int key, int value) {
            auto it = pairs_.find(key);
            if (it == pairs_.end()) {
                if (pairs_.size() == capacity_) {
                    pairs_.erase(keys_.back());
                    keys_.pop_back();
                }
                keys_.push_front(key);
                pairs_.insert(make_pair(key, Pair(value, keys_.begin())));
                return;
            }
            auto &pair = it->second;
            pair.second = touch(pair.second);
            pair.first = value;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.