NEED HELP! Why my O(1) solution get TLE!!!!!????

  • -1

    I am 100% sure my code works correctly.

    I have tried the testcase that I got TLE on my own machine (VC2013). It literally takes only 3ms!
    I am not sure about the performance under g++.

    Somebody please HELP me about this. Thanks so much!

    I doubt the time limit is too tight.

    class LRUCache{
      unordered_map<int, list<pair<int, int>>::iterator> M;
      list<pair<int, int> > L;  // list of  (key,value) pair
      int cap;
      LRUCache(int capacity) {
        cap = capacity;
      int get(int key) {
        if (M.count(key) == 0) return -1;
        else {
          auto it = M[key];
          int value = it->second;
          L.push_front(make_pair(key, value));
          M[key] = L.begin();
          return value;
      void set(int key, int value) {
        if (M.count(key) != 0){
          auto it = M[key];
        L.push_front(make_pair(key, value));
        M[key] = L.begin();
        if (L.size() >= cap) {
          int removed_key = prev(L.end())->first;

  • 0

    I suggest you use a set to record existing keys to avoid useless iterating when key is invalid.

    Notice: you should know set is implemented as tree, so it's time complexity is NlgN

    I found one's solution without lib tools is easy to TLE.

Log in to reply

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