Level 3:    1 ----------- 9 ----------- 20
Level 2:    1 ---- 5 ---- 9 ---- 14 ---- 20
Level 1:    1 - 3 - 5 - 7 - 9 - 12 - 14 - 17 - 20
Level 0:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

import random

MAX_LEVEL = 16  # limit height for simplicity
P_FACTOR = 0.5  # probability to grow a level (like coin toss)


class Node:
    """Each node stores a value and forward pointers to next nodes at different levels."""
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)  # forward[i] points to next node at level i


class Skiplist:
    def __init__(self):
        self.head = Node(-float("inf"), MAX_LEVEL)  # head sentinel node
        self.level = 0  # current highest level in the list

    # ------------- Helper -------------
    def random_level(self):
        """Randomly decide the level of a new node (like flipping a coin)."""
        lvl = 0
        while random.random() < P_FACTOR and lvl < MAX_LEVEL:
            lvl += 1
        return lvl

    # ------------- Search -------------
    def search(self, target: int) -> bool:
        """
        Start from top level and move right until next is >= target.
        Then drop down one level. Repeat until level 0.
        """
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < target:
                curr = curr.forward[i]
        curr = curr.forward[0]
        return curr is not None and curr.val == target

    # ------------- Insert -------------
    def insert(self, num: int) -> None:
        """
        1. Record nodes at each level just before where new node will go.
        2. Randomly choose new node's height.
        3. Insert and adjust forward pointers.
        """
        update = [None] * (MAX_LEVEL + 1)
        curr = self.head

        # Step 1: move right/down to find insert position
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr

        # Step 2: choose random level for new node
        lvl = self.random_level()

        # if new node is higher than current max, link head at new levels
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl

        # Step 3: create and insert node
        new_node = Node(num, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    # ------------- Erase -------------
    def erase(self, num: int) -> bool:
        """
        1. Like insert, find nodes before target at each level (update[]).
        2. If found, reconnect pointers to skip target node.
        3. Adjust top level if necessary.
        """
        update = [None] * (MAX_LEVEL + 1)
        curr = self.head

        # Step 1: find predecessors
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr

        curr = curr.forward[0]
        if curr is None or curr.val != num:
            return False  # not found

        # Step 2: unlink the target node
        for i in range(self.level + 1):
            if update[i].forward[i] != curr:
                continue
            update[i].forward[i] = curr.forward[i]

        # Step 3: reduce list level if top level becomes empty
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1

        return True

Level 2:  1 ---- 5 ---- 9 ---- 18 ---- 20
Level 1:  1 - 3 - 5 - 7 - 9 - 12 - 17 - 18 - 20
Level 0:  1 2 3 4 5 6 7 8 9 10 11 12 13 17 18 19 20

| Level | Traverse path    | Stop at node | Reason         | update[i]      |
| ----- | ---------------- | ------------ | -------------- | -------------- |
| 2     | head → 1 → 5 → 9 | 9            | next (18) > 14 | update[2] = 9  |
| 1     | start at 9 → 12  | 12           | next (17) > 14 | update[1] = 12 |
| 0     | start at 12 → 13 | 13           | next (17) > 14 | update[0] = 13 |

| Level | Traverse path    | Stop at node | Reason         | update[i]      |
| ----- | ---------------- | ------------ | -------------- | -------------- |
| 2     | head → 1 → 5 → 9 | 9            | next (18) > 14 | update[2] = 9  |
| 1     | start at 9 → 12  | 12           | next (17) > 14 | update[1] = 12 |
| 0     | start at 12 → 13 | 13           | next (17) > 14 | update[0] = 13 |

Operation	Average Time	Worst Time	Space
Search	O(log n)	O(n)	O(n)
Insert	O(log n)	O(n)	O(n)
Erase	O(log n)	O(n)	O(n)