LeetCode Entry

146. LRU Cache

18.07.2023 medium 2023 kotlin

use firstNode and lastNode

146. LRU Cache medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/279

Intuition

We can use Doubly-Linked List representing access time in its order.

Approach

• use firstNode and lastNode

Complexity

• Time complexity: \(O(1)\), for each call get or put

• Space complexity: \(O(1)\), for each element

Code

class LRUCache(val capacity: Int) {
    class Node(val key: Int, var left: Node? = null, var right: Node? = null)
    var size = 0
    val map = mutableMapOf<Int, Int>()
    val firstNode = Node(-1)
    var lastNode = firstNode
    val keyToNode = mutableMapOf<Int, Node>()

    fun disconnect(node: Node) {
      val leftNode = node.left
      val rightNode = node.right
      node.left = null
      node.right = null
      leftNode?.right = rightNode
      rightNode?.left = leftNode
      if (node === lastNode) lastNode = leftNode!!
    }

    fun updateNode(key: Int) {
      val node = keyToNode[key]!!
      if (node === lastNode) return
      disconnect(node)
      lastNode.right = node
      node.left = lastNode
      lastNode = node
    }

    fun get(key: Int): Int = map[key]?.also { updateNode(key) } ?: -1

    fun put(key: Int, value: Int) {
      if (!map.contains(key)) {
        if (size == capacity) {
          firstNode.right?.let {
            map.remove(it.key)
            keyToNode.remove(it.key)
            disconnect(it)
          }
        } else size++
        keyToNode[key] = Node(key)
      }
      updateNode(key)
      map[key] = value
    }

}