JavaScript O(1) solution


  • 0
    H

    To get constant time lookup in JavaScript, the most natural technique is to use a JavaScript Object that just stores the key/value pairs for whatever you're remembering. But since JavaScript objects are not ordered, there's no way to keep track of the most recently updated keys in O(1) time. The most natural solution there is an array which you can treat like a stack. So I decided to store the data in the object for lookup, and keep track of when the keys were updated by storing them in order in an array, adding each to the end of the array whenever it gets updated and (if necessary) removing it from its previous position in the array. To facilitate FINDING where the key used to be in the array, I actually am storing a 1-indexed version of its array index on the Object itself and updating that position on the object whenever I change it in the array.

    Finally, there's a challenge about the array, which is that if you bother to delete the old key when you update and want to add the updated key to the end of the array, you are potentially shifting everything in the array over, which would become O(n). There is a known solution to this kind of problem, which is to amortize the garbage collection. If you wait for the array to become double the size of the cache before you collect the garbage, then you can add n items to the end of it before doing the O(n) clean up. But by only doing the O(n) operation so infrequently (namely, with 1/n frequency) the denominator and numerator cancel each other out and leave you with O(1).

    var LRUCache = function(capacity) {
      this.stack = []
      this.hash = {}
      this.capacity = capacity
      this.currNum = 0
    };
    
    LRUCache.prototype.get = function(key) {
      if(this.hash[key]){
        this._updateStack(key)
        return this.hash[key].value
      }else return -1
    };
    
    LRUCache.prototype._updateStack = function(key) {
      if(this.hash[key].position){
        this.stack[this.hash[key].position-1]=undefined
      }
    
    //Note: I didn't want the position to ever be 0 since 0 is falsey, so I'm using the length of the array after adding the item, which is what .push returns. That number is the index + 1.
    
      let newPosition = this.stack.push(key)
      this.hash[key].position = newPosition
      if(this.stack.length===this.capacity*2){
        this._removeGarbage()
      }
    }
    
    LRUCache.prototype._removeGarbage = function() {
      let newArr = this.stack.filter(item=>{
        if(!!item || item==='0' || item===false || item===0)return true
        else return false
      })
      newArr.forEach((key,i)=>this.hash[key].position=i+1)
      this.stack = newArr
    }
    LRUCache.prototype._removeOldest = function() {
      let i = 0
      while(!this.stack[i])i++
      let oldestKey = this.stack[i]
      this.stack[i]=undefined
      delete this.hash[oldestKey]
    }
    
    LRUCache.prototype.put = function(key, value) {
      if(!this.hash[key]){
        this.hash[key]={}
        if(this.currNum === this.capacity){
          this._removeOldest()
        }else{
          this.currNum++
        }
      }
      this._updateStack(key)
      this.hash[key].value = value
    };
    

    I think since I'm storing so much data (3 pieces for each item), and amortizing deletion, this implementation will require the actual number of items stored to be many times smaller than the total volume might otherwise be. That's a common tradeoff: added space complexity in exchange for reduced time complexity.


Log in to reply
 

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