Leetcode 1206. Design Skiplist

Problem explanation

This problem requires us to build a skip list data structure that allows for fast search, add, and erase operations. The skip list is essentially a series of sorted linked lists, with each subsequent list skipping over a certain number of elements. This allows for fast operations as we can "skip" over many elements when performing searches, additions, or deletions, hence the name "skip list".

For example, suppose we have a skip list consisting of the numbers [30, 40, 50, 60, 70, 90]. If we were to add the number 45 into the skip list, it would be inserted between 40 and 50 in all the linked lists where these two numbers exist. This is because skip lists maintain sorted order of elements within each linked list.

This problem specifies three operations that need to be implemented in the skip list:

• search(target): this should return whether a given target number exists in the skip list.
• add(num): this should insert a given number into the skip list.
• erase(num): this should remove a given number from the skip list. If the number does not exist in the skip list, nothing should be done and the function should return false. If multiple instances of the number exist in the skip list, only one instance needs to be removed.

Solution Walk-Through

The solution uses a Node structure to represent individual elements of the skip list. Each node has a value and two pointers, next and down. next points to the next node in the current linked list, whereas down points to the node in the linked list below with the same value.

The SkipList is implemented as a stack of linked lists. The top of the stack is a dummy node with a -1 value. This dummy node serves as a "sentinel" node that simplifies the code by eliminating the need to deal with edge cases where operations need to be performed on the first node in a linked list.

In search(), we start from the top linked list and work our way down each linked list. In each linked list, we move forward until we reach a node whose next node has a value greater than or equal to the target. If we find a node with a value equal to the target, we return true. If we have traversed all the linked lists and haven't found the target value, we return false.

In add(), we again start from the top linked list and work our way down until we reach the appropriate position for the new number in each linked list. As we find these positions, we keep track of the nodes preceding these positions in a stack. We then pop nodes from the stack and insert the new number after each popped node, linking the new nodes together using the down pointers. There's a random element involved at this step, as we randomly decide whether to insert the new number into the next linked list down.

In erase(), we iterate through each linked list and delete the first node with the given value that we find. If we don't find any node with the given value after traversing all linked lists, we return false. If we have found and removed a node with the given value, we return true.

Solution in Python

1
2python
3import random
4
5class Node:
6    def __init__(self, value=None, right=None, down=None):
7        self.value = value
8        self.right = right
9        self.down = down
10
11class Skiplist:
12    def __init__(self):
13        self.head = Node()
14
15    def search(self, target):
16        node = self.head
17        while node:
18            while node.right and node.right.value < target:
19                node = node.right
20            if node.right and node.right.value == target:
21                return True
22            node = node.down
23        return False
24
25    def add(self, num):
26        nodes = []
27        node = self.head
28        while node:
29            while node.right and node.right.value < num:
30                node = node.right
31            nodes.append(node)
32            node = node.down
33          
34        insert_up = True
35        down_node = None
36        while insert_up and nodes:
37            node = nodes.pop()
38            node.right = Node(num, node.right, down_node)
39            down_node = node.right
40            insert_up = (random.randint(0, 1) == 1)
41          
42        if insert_up:
43            self.head = Node(None, None, self.head)
44
45    def erase(self, num):
46        node = self.head
47        found = False
48        while node:
49            while node.right and node.right.value < num:
50                node = node.right
51            if node.right and node.right.value == num:
52                node.right = node.right.right
53                found = True
54            node = node.down
55        return found

Solution in Java

1
2java
3public class Skiplist {
4
5    private Node head = new Node(0, 20);
6
7    public boolean search(int target) {
8        for (Node p = head; p != null; p = p.down) {
9            while (p.next != null && p.next.val < target) {
10                p = p.next;
11            }
12            if (p.next != null && p.next.val == target) {
13                return true;
14            }
15        }
16        return false;
17    }
18
19    public void add(int num) {
20        Node cur = head;
21        ArrayDeque<Node> stack = new ArrayDeque<>();
22        for (; cur != null; cur = cur.down) {
23            while (cur.next != null && cur.next.val < num) {
24                cur = cur.next;
25            }
26            stack.push(cur);
27        }
28        boolean insertUp = true;
29        Node downNode = null;
30        while (insertUp && !stack.isEmpty()) {
31            Node node = stack.pop();
32            node.next = new Node(num, node.next, downNode);
33            downNode = node.next;
34            insertUp = (Math.random() < 0.5);
35        }
36        if (insertUp) {
37            head = new Node(0, head);
38        }
39    }
40
41    public boolean erase(int num) {
42        boolean exists = false;
43        for (Node p = head; p != null; p = p.down) {
44            while (p.next != null && p.next.val < num) {
45                p = p.next;
46            }
47            if (p.next != null && p.next.val == num) {
48                exists = true;
49                p.next = p.next.next;
50            }
51        }
52        return exists;
53    }
54
55    class Node {
56        int val;
57        Node down;
58        Node next;
59        public Node(int val, Node next) {
60            this.val = val;
61            this.next = next;
62        }
63        public Node(int val, Node down, Node next) {
64            this.val = val;
65            this.down = down;
66            this.next = next;
67        }
68    }
69}

Solution in JavaScript

1
2javascript
3var Node = function(val, right=null, down=null) {
4    this.val = val === undefined ? 0 : val;
5    this.right = right;
6    this.down = down;
7}
8
9var Skiplist = function() {
10    this.head = new Node();
11}
12
13Skiplist.prototype.search = function(target) {
14    let node = this.head;
15    while(node) {
16        // move right in the list
17        while(node.right && node.right.val < target) {
18            node = node.right;
19        }
20        // check the node
21        if(node.right && node.right.val === target) return true;
22        // move down in the list
23        node = node.down;
24    }
25    return false;
26}
27
28Skiplist.prototype.add = function(num) {
29    let nodes = [];
30    let node = this.head;
31    // traverse right and down, similar to search to find the spot
32    while(node) {
33        while(node.right && node.right.val < num) {
34            node = node.right;
35        }
36        nodes.push(node);
37        node = node.down
38    }
39    // insert nodes
40    let insertUp = true;
41    let downNode = null;
42    while(insertUp && nodes.length) {
43        node = nodes.pop();
44        node.right = new Node(num, node.right, downNode);
45        downNode = node.right;
46        insertUp = Math.random() < 0.5;
47    }
48    // insert new head
49    if(insertUp) {
50        this.head = new Node(-1, null, this.head);
51    }
52}
53
54Skiplist.prototype.erase = function(num) {
55    let node = this.head;
56    let found = false;
57    while(node) {
58        while(node.right && node.right.val < num) {
59            node = node.right;
60        }
61        if(node.right && node.right.val === num) {
62            node.right = node.right.right;
63            found = true;
64        }
65        node = node.down;
66    }
67    return found;
68}

This JavaScript implementation follows the same logic as the Python and Java implementations. The Node constructor is defined to represent nodes in the skip list. The Skiplist constructor is used to initialize the head of the list. The search, add, and erase methods are implemented in the Skiplist prototype to carry out their respective operations on the skip list.

In JavaScript, we use the push() function to add nodes to the nodes array and pop() to remove nodes from it. Similar to the Python and Java implementations, we use a while loop to traverse the nodes, and we use Math.random() to randomly decide whether to insert into the next linked list down.