# Design Skiplist
**Difficulty:** HARD
[External](https://leetcode.com/problems/design-skiplist)
Canonical: https://scaleengineer.com/dsa/problems/design-skiplist
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Skip List](https://scaleengineer.com/algorithms/skip-list)
**Data structures:** Linked List
**Companies:** [eBay](https://scaleengineer.com/companies/ebay), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [X](https://scaleengineer.com/companies/x)
---
## Problem
Design a **Skiplist** without using any built-in libraries.

A **skiplist** is a data structure that takes `O(log(n))` time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.

For example, we have a Skiplist containing `[30,40,50,60,70,90]` and we want to add `80` and `45` into it. The Skiplist works this way:

![](https://assets.glich.co/dsa/design-skiplist/image0.gif)  
Artyom Kalinin \[CC BY-SA 3.0\], via [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Skip%5Flist%5Fadd%5Felement-en.gif "Artyom Kalinin [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons")

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than `O(n)`. It can be proven that the average time complexity for each operation is `O(log(n))` and space complexity is `O(n)`.

See more about Skiplist: <https://en.wikipedia.org/wiki/Skip%5Flist>

Implement the `Skiplist` class:

* `Skiplist()` Initializes the object of the skiplist.
* `bool search(int target)` Returns `true` if the integer `target` exists in the Skiplist or `false` otherwise.
* `void add(int num)` Inserts the value `num` into the SkipList.
* `bool erase(int num)` Removes the value `num` from the Skiplist and returns `true`. If `num` does not exist in the Skiplist, do nothing and return `false`. If there exist multiple `num` values, removing any one of them is fine.

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

**Example 1:**

**Input**
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
**Output**
[null, null, null, null, false, null, true, false, true, false]

**Explanation**
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // return False
skiplist.add(4);
skiplist.search(1); // return True
skiplist.erase(0);  // return False, 0 is not in skiplist.
skiplist.erase(1);  // return True
skiplist.search(1); // return False, 1 has already been erased.

**Constraints:**

* `0 <= num, target <= 2 * 104`
* At most `5 * 104` calls will be made to `search`, `add`, and `erase`.

# Approaches
## Standard Skiplist Implementation
A skiplist is a probabilistic data structure that allows for efficient search, insertion, and deletion operations, all averaging O(log n) time complexity. It's built upon multiple layers of sorted linked lists. The bottom-most layer (level 0) is a regular sorted linked list containing all the elements. Each higher layer acts as an 'express lane' for the layers below it, containing a subsequence of the elements from the layer below.
**Time:** O(log n) on average for `search`, `add`, and `erase`. The height of the skiplist is O(log n) with high probability. At each level, we traverse a constant number of nodes on average. In the worst case (which is extremely unlikely), the structure can degenerate into a single linked list, leading to O(n) complexity. · **Space:** O(n). Each of the `n` elements is stored in a node. The expected number of pointers per node is `1 / (1 - p)`, where `p` is the probability factor (commonly 0.5). So, the total space is proportional to `n`.
**Pros:** Achieves O(log n) average time complexity for search, insertion, and deletion, making it as efficient as balanced binary search trees.; Relatively simpler to implement compared to self-balancing trees like Red-Black Trees or AVL Trees, as it uses randomization instead of complex rotation and rebalancing rules.; Naturally lends itself to concurrent modifications, making it a good choice for multithreaded environments.
**Cons:** Uses more memory than balanced binary search trees due to the storage of multiple forward pointers in each node.; The performance guarantees are probabilistic, not deterministic. There is a very small but non-zero probability of worst-case O(n) performance.
### Explanation
The core idea is that when we insert a new element, we randomly determine its 'level' or 'height'. This means the new node will be part of the linked lists from level 0 up to its determined level. A common way to determine the level is to simulate flipping a coin: start at level 1, and for each 'heads', increase the level by one. This results in approximately half the nodes being at level 1, a quarter at level 2, and so on, creating a sparse hierarchy of express lanes. This probabilistic approach ensures that, on average, the height of the skiplist is logarithmic with respect to the number of elements, which is the key to its efficiency.

### Node Structure
A node in the skiplist needs to store its value and an array of pointers to the next node at each level it participates in.
```java
class Node {
    int val;
    Node[] forward;

    public Node(int val, int level) {
        this.val = val;
        this.forward = new Node[level];
    }
}
```

### Skiplist Structure
The main class will manage the skiplist, holding a reference to a sentinel `head` node, the maximum possible level, the current highest level in the list, and the probability factor for level generation.
```java
class Skiplist {
    private static final int MAX_LEVEL = 32;
    private static final double P_FACTOR = 0.5;
    private Node head;
    private int currentLevel;
    private Random random;

    public Skiplist() {
        this.head = new Node(-1, MAX_LEVEL);
        this.currentLevel = 0;
        this.random = new Random();
    }
    // ... methods
}
```

### Operations
All operations (`search`, `add`, `erase`) begin by traversing the skiplist from the highest level of the `head` node down to the bottom level to find the relevant position or node.

#### `search(int target)`
To search for a target, we start at the highest level and move forward as long as the next node's value is less than the target. If the next node is too large or we reach the end of the level, we drop down to the next lower level and repeat the process. This efficiently narrows down the search space. Finally, at the bottom level, we check if the immediate next node contains the target value.

#### `add(int num)`
Adding a number involves first finding the correct insertion points at all levels, just like in a search. We keep track of the last node we visited at each level before dropping down; these will be the predecessors of our new node. After finding the position, we determine a random level for the new node. Then, we create the new node and link it into the skiplist at each level from 0 up to its randomly determined level, using the predecessor nodes we saved.

#### `erase(int num)`
Erasing is similar to adding. We first search for the node containing `num`, while also keeping track of the predecessor nodes at each level. If the node is found, we 'bypass' it by updating the `forward` pointers of its predecessors at all levels to point to the node that comes after the one being deleted. If the deletion results in the highest levels becoming empty, we can decrease the `currentLevel` of the skiplist.
### Algorithm
### Node and Skiplist Initialization
1.  Define a `Node` class with an integer `val` and an array `forward` of `Node` pointers.
2.  In the `Skiplist` class, initialize a sentinel `head` node with a value smaller than any possible element (e.g., -1) and the maximum possible level. Initialize `currentLevel` to 0.

### `search(target)` Algorithm
1.  Initialize a `curr` pointer to `head`.
2.  Iterate from `currentLevel - 1` down to 0.
3.  In the inner loop, traverse forward at the current level `i`: `while (curr.forward[i] != null && curr.forward[i].val < target) { curr = curr.forward[i]; }`.
4.  After the loops, `curr` is the predecessor to the potential target at level 0.
5.  Move to the next node: `curr = curr.forward[0]`.
6.  Return `true` if `curr` is not null and `curr.val == target`, otherwise `false`.
```java
public boolean search(int target) {
    Node curr = this.head;
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (curr.forward[i] != null && curr.forward[i].val < target) {
            curr = curr.forward[i];
        }
    }
    curr = curr.forward[0];
    return curr != null && curr.val == target;
}
```

### `add(num)` Algorithm
1.  Create an `update` array of `Node`s to store the predecessors of the new node at each level.
2.  Initialize `curr` to `head`.
3.  Traverse from `currentLevel - 1` down to 0, finding the insertion point at each level and storing the predecessor in `update[i]`. `while (curr.forward[i] != null && curr.forward[i].val < num) { curr = curr.forward[i]; } update[i] = curr;`
4.  Generate a random level `newLevel` for the new node.
5.  If `newLevel > currentLevel`, update `currentLevel` and fill the new levels in `update` with `head`.
6.  Create a `newNode` with value `num` and height `newLevel`.
7.  Iterate from `i = 0` to `newLevel - 1`, and for each level, insert `newNode` using the `update` array: `newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode;`
```java
public void add(int num) {
    Node[] update = new Node[MAX_LEVEL];
    Arrays.fill(update, head);
    Node curr = this.head;

    for (int i = currentLevel - 1; i >= 0; i--) {
        while (curr.forward[i] != null && curr.forward[i].val < num) {
            curr = curr.forward[i];
        }
        update[i] = curr;
    }

    int newLevel = randomLevel();
    if (newLevel > currentLevel) {
        currentLevel = newLevel;
    }

    Node newNode = new Node(num, newLevel);
    for (int i = 0; i < newLevel; i++) {
        newNode.forward[i] = update[i].forward[i];
        update[i].forward[i] = newNode;
    }
}

private int randomLevel() {
    int level = 1;
    while (random.nextDouble() < P_FACTOR && level < MAX_LEVEL) {
        level++;
    }
    return level;
}
```

### `erase(num)` Algorithm
1.  Create and populate an `update` array with predecessors, just like in `add`.
2.  Move to the node to be potentially deleted: `curr = curr.forward[0]`.
3.  If `curr` is null or `curr.val != num`, the element doesn't exist. Return `false`.
4.  Iterate from `i = 0` to `currentLevel - 1`. If `update[i].forward[i] == curr`, bypass it: `update[i].forward[i] = curr.forward[i]`.
5.  After deletion, check if the top levels are now empty. If `head.forward[currentLevel - 1] == null`, decrement `currentLevel`.
6.  Return `true`.
```java
public boolean erase(int num) {
    Node[] update = new Node[MAX_LEVEL];
    Node curr = this.head;

    for (int i = currentLevel - 1; i >= 0; i--) {
        while (curr.forward[i] != null && curr.forward[i].val < num) {
            curr = curr.forward[i];
        }
        update[i] = curr;
    }

    curr = curr.forward[0];
    if (curr == null || curr.val != num) {
        return false;
    }

    for (int i = 0; i < currentLevel; i++) {
        if (update[i].forward[i] != curr) {
            break;
        }
        update[i].forward[i] = curr.forward[i];
    }

    while (currentLevel > 0 && head.forward[currentLevel - 1] == null) {
        currentLevel--;
    }
    return true;
}
```

# Solutions
### Java

```java
class Skiplist { private static final int MAX_LEVEL = 32 ; private static final double P = 0.25 ; private static final Random RANDOM = new Random (); private final Node head = new Node (- 1 , MAX_LEVEL ); private int level = 0 ; public Skiplist () { } public boolean search ( int target ) { Node curr = head ; for ( int i = level - 1 ; i >= 0 ; -- i ) { curr = findClosest ( curr , i , target ); if ( curr . next [ i ] != null && curr . next [ i ]. val == target ) { return true ; } } return false ; } public void add ( int num ) { Node curr = head ; int lv = randomLevel (); Node node = new Node ( num , lv ); level = Math . max ( level , lv ); for ( int i = level - 1 ; i >= 0 ; -- i ) { curr = findClosest ( curr , i , num ); if ( i < lv ) { node . next [ i ] = curr . next [ i ]; curr . next [ i ] = node ; } } } public boolean erase ( int num ) { Node curr = head ; boolean ok = false ; for ( int i = level - 1 ; i >= 0 ; -- i ) { curr = findClosest ( curr , i , num ); if ( curr . next [ i ] != null && curr . next [ i ]. val == num ) { curr . next [ i ] = curr . next [ i ]. next [ i ]; ok = true ; } } while ( level > 1 && head . next [ level - 1 ] == null ) { -- level ; } return ok ; } private Node findClosest ( Node curr , int level , int target ) { while ( curr . next [ level ] != null && curr . next [ level ]. val < target ) { curr = curr . next [ level ]; } return curr ; } private static int randomLevel () { int level = 1 ; while ( level < MAX_LEVEL && RANDOM . nextDouble () < P ) { ++ level ; } return level ; } static class Node { int val ; Node [] next ; Node ( int val , int level ) { this . val = val ; next = new Node [ level ]; } } } /** * Your Skiplist object will be instantiated and called as such: * Skiplist obj = new Skiplist(); * boolean param_1 = obj.search(target); * obj.add(num); * boolean param_3 = obj.erase(num); */
```

### CPP

```cpp
struct Node { int val ; vector < Node *> next ; Node ( int v , int level ) : val ( v ) , next ( level , nullptr ) {} }; class Skiplist { public: const int p = RAND_MAX / 4 ; const int maxLevel = 32 ; Node * head ; int level ; Skiplist () { head = new Node ( - 1 , maxLevel ); level = 0 ; } bool search ( int target ) { Node * curr = head ; for ( int i = level - 1 ; ~ i ; -- i ) { curr = findClosest ( curr , i , target ); if ( curr -> next [ i ] && curr -> next [ i ] -> val == target ) return true ; } return false ; } void add ( int num ) { Node * curr = head ; int lv = randomLevel (); Node * node = new Node ( num , lv ); level = max ( level , lv ); for ( int i = level - 1 ; ~ i ; -- i ) { curr = findClosest ( curr , i , num ); if ( i < lv ) { node -> next [ i ] = curr -> next [ i ]; curr -> next [ i ] = node ; } } } bool erase ( int num ) { Node * curr = head ; bool ok = false ; for ( int i = level - 1 ; ~ i ; -- i ) { curr = findClosest ( curr , i , num ); if ( curr -> next [ i ] && curr -> next [ i ] -> val == num ) { curr -> next [ i ] = curr -> next [ i ] -> next [ i ]; ok = true ; } } while ( level > 1 && ! head -> next [ level - 1 ]) -- level ; return ok ; } Node * findClosest ( Node * curr , int level , int target ) { while ( curr -> next [ level ] && curr -> next [ level ] -> val < target ) curr = curr -> next [ level ]; return curr ; } int randomLevel () { int lv = 1 ; while ( lv < maxLevel && rand () < p ) ++ lv ; return lv ; } }; /** * Your Skiplist object will be instantiated and called as such: * Skiplist* obj = new Skiplist(); * bool param_1 = obj->search(target); * obj->add(num); * bool param_3 = obj->erase(num); */
```

### Python

```python
class Node : __slots__ = [ 'val' , 'next' ] def __init__ ( self , val : int , level : int ): self . val = val self . next = [ None ] * level class Skiplist : max_level = 32 p = 0.25 def __init__ ( self ): self . head = Node ( - 1 , self . max_level ) self . level = 0 def search ( self , target : int ) -> bool : curr = self . head for i in range ( self . level - 1 , - 1 , - 1 ): curr = self . find_closest ( curr , i , target ) if curr . next [ i ] and curr . next [ i ]. val == target : return True return False def add ( self , num : int ) -> None : curr = self . head level = self . random_level () node = Node ( num , level ) self . level = max ( self . level , level ) for i in range ( self . level - 1 , - 1 , - 1 ): curr = self . find_closest ( curr , i , num ) if i < level : node . next [ i ] = curr . next [ i ] curr . next [ i ] = node def erase ( self , num : int ) -> bool : curr = self . head ok = False for i in range ( self . level - 1 , - 1 , - 1 ): curr = self . find_closest ( curr , i , num ) if curr . next [ i ] and curr . next [ i ]. val == num : curr . next [ i ] = curr . next [ i ]. next [ i ] ok = True while self . level > 1 and self . head . next [ self . level - 1 ] is None : self . level -= 1 return ok def find_closest ( self , curr : Node , level : int , target : int ) -> Node : while curr . next [ level ] and curr . next [ level ]. val < target : curr = curr . next [ level ] return curr def random_level ( self ) -> int : level = 1 while level < self . max_level and random . random () < self . p : level += 1 return level # Your Skiplist object will be instantiated and called as such: # obj = Skiplist() # param_1 = obj.search(target) # obj.add(num) # param_3 = obj.erase(num)
```