Design Skiplist - Leetcode Solution

Design Skiplist problem on leetcode can be solved using the concept of skip lists which is a probabilistic data structure that allows faster searching, insertion and deletion of elements as compared to other data structures like linked lists.

The solution can be implemented by creating a class called Skiplist which will have the following methods:

1. init(self): This method will initialize the skiplist with a head node containing a maximum level which will be used to determine the maximum height of the skiplist nodes.

2. search(self, target: int) -> bool: This method will search for the target node in the skiplist and if found, return True otherwise, return False.

3. add(self, num: int) -> None: This method will add a new node with the given number in the skiplist.

4. erase(self, num: int) -> bool: This method will remove a node with the given number from the skiplist.

To implement the skiplist, we can create a Node class with the following attributes:

1. val: The value of the node.
2. right: A reference to the next node on the same level.
3. down: A reference to the node on the level below.

We can then create a Skiplist class which will have the following methods:

init(self):

This method will create a head node with a maximum level which will be used to determine the maximum height of the skiplist nodes.

class Skiplist:
    def __init__(self):
        self.head = Node(None)
        self.head.max_level = 16

search(self, target: int) -> bool:

This method will search for the target node in the skiplist and if found, return True otherwise, return False.

    def search(self, target: int) -> bool:
        cur = self.head
        while cur:
            if cur.right and cur.right.val < target:
                cur = cur.right
            elif cur.right and cur.right.val == target:
                return True
            else:
                cur = cur.down
        return False

add(self, num: int) -> None:

This method will add a new node with the given number in the skiplist.

    def add(self, num: int) -> None:
        node_stack = []
        cur = self.head

        while cur:
            if cur.right and cur.right.val < num:
                cur = cur.right
            else:
                node_stack.append(cur)
                cur = cur.down

        insert = True
        down_node = None

        while insert and node_stack:
            cur = node_stack.pop()
            new_node = Node(num)
            new_node.right = cur.right
            cur.right = new_node
            new_node.down = down_node
            down_node = new_node
            insert = (random.random() < 0.5)  # coin flip to generate new level

        if insert:
            new_node = Node(num)
            new_node.right = self.head.right
            self.head.right = new_node
            new_node.down = down_node

erase(self, num: int) -> bool:

This method will remove a node with the given number from the skiplist.

    def erase(self, num: int) -> bool:
        cur = self.head
        found = False
        while cur:
            if cur.right and cur.right.val < num:
                cur = cur.right
            elif cur.right and cur.right.val == num:
                cur.right = cur.right.right
                found = True
                cur = cur.down
            else:
                cur = cur.down
        return found

The method add uses coin flip to determine the height of the new node. The probability of generating a new level for the node is 50%. If the coin flip results in a heads then the new node is added to the next highest level.

The time complexity of add, search and erase operations are O(log n) on average where n is the number of nodes in the skiplist. The space complexity is O(n) as we are maintaining a separate data structure to store the nodes of the skiplist.

1