Day 14 of LeetCode

Q1

141. Linked List Cycle

Easy. Linked list

Slow and fast pointers.

From Neetcode, youtube.com/watch?v=gBTe7lFR3vc

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False

Q2

287. Find the Duplicate Number

Medium. Linked list

It's a linked list and cycle problem.

The value becomes the index.

From Neetcode, youtube.com/watch?v=wjYnzkAhcNk

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0
        # Find the intersection
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Find the head of the cycle
        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

Q3

146. LRU Cache

Medium. Linked list

Double linked list + hashmap

class Node:

    def __init__(self, key: int, val: int):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # map key to nodes

        self.left = self.right = Node(0, 0)
        # left.next=lru, right.prev=most recent
        self.left.next, self.right.prev = self.right, self.left

    # Remove the node from the linked list
    def remove(self, node: Node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    # Insert the node to the right
    def insert(self, node: Node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.prev, node.next = prev, nxt

    def get(self, key: int) -> int:
        if key in self.cache:
            # Make it the most recent node
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val

        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        # Update hashmap
        self.cache[key] = Node(key, value)
        # Insert it to the right
        self.insert(self.cache[key])

        if len(self.cache) > self.capacity:
            lru = self.left.next
            # Remove the lru
            self.remove(lru)
            # Delete it from the hashmap
            del self.cache[lru.key]