1206. Design Skiplist

Problem Description

The task is to design a Skiplist, a data structure that supports insertion, searching, and deletion operations in O(log(n)) average time complexity. In contrast with other data structures that offer similar performance, like treaps and red-black trees, Skiplists have the advantage of often being easier to implement. A Skiplist is essentially a set of multiple linked lists that together form a hierarchical structure with different levels. Each level is a linked list, and higher levels provide fast lanes for traversing the data structure quickly, as they skip over multiple elements in the lower levels.

The operations that need to be supported are as follows:

Skiplist(): A constructor that initializes the skiplist.
bool search(int target): Searches for a value in the skiplist and returns true if the value is found and false if it isn't.
void add(int num): Inserts a value into the skiplist.
bool erase(int num): Removes a value from the skiplist, returning true if the operation is successful and false if the value is not found.

The design should handle multiple occurrences of the same number, meaning duplicates are allowed.

Intuition

The intuition behind the Skiplist is to overlay multiple layers of linked lists to enable faster navigation for add, search, and erase operations than would be possible in a standard single-level linked list. Each subsequent layer above the base layer has fewer nodes and skips over multiple nodes of the layer directly beneath it, creating shortcuts. In the context of highway systems, these can be thought of as express lanes where certain exits are skipped to allow for faster transit across long distances.

To implement these operations efficiently, a Node class is defined, with each node having a val and an array of pointers, next, to the subsequent nodes at each level of the Skiplist. In a Skiplist, each node can potentially be part of multiple linked lists at different levels, rather than just one.

The search operation starts from the top level and moves horizontally until it encounters a node with the next value greater than the target. It then moves down a level and continues this process until it reaches the bottom level to determine if the target exists in the list.

The add operation involves creating a new node with randomly determined levels to insert it into all applicable levels, maintaining the sorting order.

The erase operation finds and removes the node across all levels of the list where it exists.

Random level generation (for determining the number of levels a new node should be part of) is crucial as it impacts the balance and performance of the Skiplist. If too many nodes are at high levels, the benefits of skipping will be reduced, whereas too few can lead to numerous lower-level traversals, degenerating the structure to a basic linked list.

The provided solution code thus does the following:

Manages the pointers between nodes at various levels to maintain the skiplist structure during additions, deletions, and searches.
Chooses levels randomly during insertion (with an upper limit, max_level) to ensure that the average complexity remains logarithmic.
Iteratively performs each step, taking care to handle edge cases such as the need to update the skiplist levels after deletions.

Learn more about Linked List patterns.

Solution Approach

The Skiplist structure is implemented with a Node class that holds a value and an array of pointers representing the nodes it points to at various levels. The Skiplist class manages these nodes and performs operations upon them. Here's how the implementation takes shape:

Node Structure: Each Node consists of a value and an array next that stores pointers to the nodes at various levels that come after the current node. The length of the next array determines how many levels the node is part of.
Initialization: The Skiplist is initialized with a dummy head node at all levels up to max_level, which is set to a constant that determines the maximum number of levels a node can have. The actual number of levels a Skiplist is using is stored in self.level, which starts at 0 and increases as higher-level nodes are added.
Search Operation: To search for a target value, the algorithm starts from the highest level of the head node and traverses to the right until it encounters a node with a value greater than the target. It then drops down one level and continues this process until it either finds the target (returning true) or reaches the bottom level (returning false if the target is not found).
Random Level Generation: The random_level function determines the level of a new node being added by using a loop that continues promoting the level with a probability defined by p until the level reaches max_level or the promotion stops randomly.
Insertion: The add function inserts a node by first determining the random level for the new node. Starting from the top level of the head node, it finds the appropriate spot to insert the node at every level up to the node's level. It rearranges pointers such that each next pointer at a level less than the node's level points to the new node, and the corresponding pointer in the new node points to the next node in the sequence.
Deletion: The erase function searches for the node with the matching value starting from the top level, and if found, rearranges pointers at every level to bypass the node being deleted. If a node is removed, the function also adjusts the self.level of the Skiplist if the top levels become empty.
Level Adjustment: After any erase operation, the levels of the skiplist are checked to see if the top level is unused (no nodes except the head). If so, the level is decremented, which helps to keep the skiplist from having unnecessary empty levels at the top.

This implementation takes advantage of the "fast lane" concept with multiple levels of linked lists to provide efficient logarithmic-time operations on average, mimicking what binary search trees offer but in a more lightweight fashion that leverages randomness for balancing.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for implementing a Skiplist. Consider we are working with a Skiplist that has a max_level of 3.

Initialization: When the Skiplist is created, a dummy head node is initialized with a next pointer array of size max_level. Initially, all the next pointers point to None, indicating that the Skiplist is empty.

Adding Elements: Let's begin by inserting the numbers 3, 6, and 9 into the Skiplist.

When adding 3, suppose the random_level function decides that the new node will only be at level 1 (0-indexed). The new node with value 3 is inserted right after the head node at level 1. The Skiplist now looks something like this:

Level 2: head -> None
Level 1: head -> [3] -> None
Level 0: head -> [3] -> None

We add 6 next, and let's say it's also added at level 1. The Skiplist updates to:

Level 2: head -> None
Level 1: head -> [3] -> [6] -> None
Level 0: head -> [3] -> [6] -> None

Finally, we add 9, and it is determined to be at level 2. It gets inserted at each level up to level 2:

Level 2: head -> [9] -> None
Level 1: head -> [3] -> [6] -> [9] -> None
Level 0: head -> [3] -> [6] -> [9] -> None

Searching: Let's search for the number 6 in the Skiplist. The search starts at the highest level (level 2):
- At Level 2, the head points directly to 9, which is greater than 6. So, we go down to the next level (1).
- At Level 1, the head points to 3, and 3 points to 6. Since 6 is the number we are searching for, we return true.
Erasing Elements: To erase the number 6, the operation will start at the highest level (level 2) and work its way down:
- At Level 2, there's no node before 9 that points to 6, so we move down to Level 1.
- At Level 1, 3 points to 6, and 6 points to 9. We remove 6 and update 3 to point to 9. The Skiplist now looks like:
```
Level 2: head -> [9] -> None
Level 1: head -> [3] -> [9] -> None
Level 0: head -> [3] -> [9] -> None
```
- If the removed node happened to be the highest-level node, the Skiplist would also need to update the self.level to reflect the removed level.

This example demonstrates how a Skiplist can provide logarithmic time complexity for add, search, and erase operations by employing multiple levels of linked lists and using randomization to maintain balance within the structure.

Solution Implementation

1import random
2
3class Node:
4    def __init__(self, value: int, level: int):
5        """
6        Initialize a Node with a given value and level.
7        The level corresponds to the number of forward references (pointers)
8        it has to other nodes.
9        """
10        self.value = value
11        self.next = [None] * level
12
13class Skiplist:
14    MAX_LEVEL = 32  # Maximum level for the skip list
15    P = 0.25  # Probability factor for determining the level of a new node
16
17    def __init__(self):
18        """
19        Initialize the SkipList with a head node of maximum level, setting
20        the current level to 0.
21        """
22        self.head = Node(-1, self.MAX_LEVEL)  
23        self.current_level = 0
24
25    def search(self, target: int) -> bool:
26        """
27        Search for a target element in the skip list. Returns True if the
28        element is found, False otherwise.
29        """
30        current = self.head
31        # Traverse from the top level of the skip list down to the bottom
32        for i in range(self.current_level - 1, -1, -1):
33            # Move to the node closest to the target at the current level
34            current = self._find_closest(current, i, target)
35            # Check if the target is found at the current level
36            if current.next[i] and current.next[i].value == target:
37                return True
38        return False
39
40    def add(self, num: int) -> None:
41        """
42        Add a new element to the skip list.
43        """
44        current = self.head
45        new_node_level = self._random_level()
46        new_node = Node(num, new_node_level)
47        # Update the skip list's current level if necessary
48        self.current_level = max(self.current_level, new_node_level)
49        for i in range(self.current_level - 1, -1, -1):
50            current = self._find_closest(current, i, num)
51            # Link the new node if the level is less than the new node's level
52            if i < new_node_level:
53                new_node.next[i] = current.next[i]
54                current.next[i] = new_node
55
56    def erase(self, num: int) -> bool:
57        """
58        Erase an element from the skip list. Returns True if the element was
59        successfully removed, False if it was not found.
60        """
61        current = self.head
62        removed = False
63        # Try to find and remove the node with the given value
64        for i in range(self.current_level - 1, -1, -1):
65            current = self._find_closest(current, i, num)
66            if current.next[i] and current.next[i].value == num:
67                # Skip over the to-be-removed node
68                current.next[i] = current.next[i].next[i]
69                removed = True
70        # Adjust the skip list level if the top level is now empty
71        while self.current_level > 1 and self.head.next[self.current_level - 1] is None:
72            self.current_level -= 1
73        return removed
74
75    def _find_closest(self, current: Node, level: int, target: int) -> Node:
76        """
77        Find the node at the specified level whose value is closest to,
78        but not greater than, the target.
79        """
80        while current.next[level] and current.next[level].value < target:
81            current = current.next[level]
82        return current
83
84    def _random_level(self) -> int:
85        """
86        Randomly determine the level for a new node.
87        """
88        level = 1
89        # Use a geometric distribution with probability P to determine the level
90        while level < self.MAX_LEVEL and random.random() < self.P:
91            level += 1
92        return level
93
94# Example usage:
95# skiplist = Skiplist()
96# skiplist.add(1)
97# print(skiplist.search(1))  # Output: True
98# skiplist.erase(1)
99# print(skiplist.search(1))  # Output: False
100

1import java.util.Random;
2
3public class Skiplist {
4  
5    // Maximum level for the skiplist
6    private static final int MAX_LEVEL = 32;
7    // Probability for the randomLevel method
8    private static final double PROBABILITY = 0.25;
9    // Random number generator for generating levels
10    private static final Random random = new Random();
11  
12    // The head node of the skiplist
13    private final Node head = new Node(-1, MAX_LEVEL);
14  
15    // Current level of the skiplist
16    private int level = 0;
17  
18    public Skiplist() {
19    }
20
21    // Search for a value in the skiplist
22    public boolean search(int target) {
23        Node current = head;
24        for (int i = level - 1; i >= 0; --i) {
25            current = findClosest(current, i, target);
26            if (current.next[i] != null && current.next[i].value == target) {
27                // We found the target value
28                return true;
29            }
30        }
31        // Target value not found
32        return false;
33    }
34
35    // Add a value to the skiplist
36    public void add(int num) {
37        Node current = head;
38        int newLevel = randomLevel();
39        Node newNode = new Node(num, newLevel);
40        // Potentially increase skiplist current level
41        level = Math.max(level, newLevel);
42        for (int i = level - 1; i >= 0; --i) {
43            current = findClosest(current, i, num);
44            if (i < newLevel) {
45                newNode.next[i] = current.next[i];
46                current.next[i] = newNode;
47            }
48        }
49    }
50
51    // Erase a value from the skiplist
52    public boolean erase(int num) {
53        Node current = head;
54        boolean found = false;
55        for (int i = level - 1; i >= 0; --i) {
56            current = findClosest(current, i, num);
57            if (current.next[i] != null && current.next[i].value == num) {
58                // Remove the node
59                current.next[i] = current.next[i].next[i];
60                found = true;
61            }
62        }
63        // Reduce the level of the skiplist if needed
64        while (level > 1 && head.next[level - 1] == null) {
65            --level;
66        }
67        return found;
68    }
69
70    // Find the node closest to a given value at a given level
71    private Node findClosest(Node current, int levelIndex, int target) {
72        while (current.next[levelIndex] != null && current.next[levelIndex].value < target) {
73            current = current.next[levelIndex];
74        }
75        return current;
76    }
77
78    // Randomly determine the level for a new node
79    private static int randomLevel() {
80        int newLevel = 1;
81        while (newLevel < MAX_LEVEL && random.nextDouble() < PROBABILITY) {
82            ++newLevel;
83        }
84        return newLevel;
85    }
86
87    // Inner class to represent a node in the skiplist
88    static class Node {
89        int value;
90        Node[] next;
91
92        Node(int value, int level) {
93            this.value = value;
94            this.next = new Node[level];
95        }
96    }
97}
98
99/**
100 * The Skiplist class can be used as follows:
101 * Skiplist skiplist = new Skiplist();
102 * boolean isFound = skiplist.search(target); // Search for 'target' in the skiplist
103 * skiplist.add(number); // Add 'number' to the skiplist
104 * boolean isErased = skiplist.erase(number); // Remove 'number' from the skiplist
105 */
106

1#include <vector>
2#include <climits>
3#include <algorithm>
4using namespace std;
5
6// Definition of a single Node in the skip list.
7struct Node {
8    int value;
9    vector<Node*> forward; // Pointers to next nodes in different levels
10    Node(int val, int lvl) : value(val), forward(lvl, nullptr) {}
11};
12
13class Skiplist {
14private:
15    static const int probability = RAND_MAX / 4; // Probability of level increase
16    static const int maxLevel = 32; // The maximum level a node can have
17    Node* head; // Pointer to the first node (header) of the skip list
18    int currentLevel; // Current maximum level of the skip list
19
20public:
21    Skiplist() {
22        head = new Node(-1, maxLevel); // Create a header node with -1 as a sentinel value
23        currentLevel = 0;
24    }
25
26    bool search(int target) {
27        Node* currentNode = head;
28        for (int i = currentLevel - 1; i >= 0; --i) {
29            // Move to the node closest to the target at current level
30            currentNode = findClosest(currentNode, i, target);
31            // If the next node at this level is the target, return true
32            if (currentNode->forward[i] && currentNode->forward[i]->value == target) {
33                return true;
34            }
35        }
36        return false; // Target not found
37    }
38
39    void add(int number) {
40        vector<Node*> update(maxLevel, nullptr);
41        Node* currentNode = head;
42        for (int i = currentLevel - 1; i >= 0; --i) {
43            currentNode = findClosest(currentNode, i, number);
44            update[i] = currentNode;
45        }
46      
47        int newLevel = randomLevel(); // Determine new node's level
48        currentLevel = max(currentLevel, newLevel); // Update the highest level used
49        Node* newNode = new Node(number, newLevel);
50
51        for (int i = 0; i < newLevel; ++i) {
52            // Update forward pointers
53            newNode->forward[i] = update[i]->forward[i];
54            update[i]->forward[i] = newNode;
55        }
56    }
57
58    bool erase(int number) {
59        vector<Node*> update(maxLevel, nullptr);
60        Node* currentNode = head;
61        bool found = false;
62        for (int i = currentLevel - 1; i >= 0; --i) {
63            currentNode = findClosest(currentNode, i, number);
64            if (currentNode->forward[i] && currentNode->forward[i]->value == number) {
65                // Remove references to the node to be deleted
66                currentNode->forward[i] = currentNode->forward[i]->forward[i];
67                found = true;
68            }
69        }
70        // Update the current level if top levels have no nodes
71        while (currentLevel > 1 && !head->forward[currentLevel - 1]) {
72            --currentLevel;
73        }
74        return found; // Return whether the node was successfully deleted
75    }
76
77    // Helper function to find the closest node before the target at the given level
78    Node* findClosest(Node* currentNode, int lvl, int target) {
79        while (currentNode->forward[lvl] && currentNode->forward[lvl]->value < target) {
80            currentNode = currentNode->forward[lvl];
81        }
82        return currentNode;
83    }
84
85    // Helper function to determine a random level for a new node
86    int randomLevel() {
87        int lvl = 1;
88        // Increase level with a probability of 1/4
89        while (lvl < maxLevel && rand() < probability) {
90            ++lvl;
91        }
92        return lvl;
93    }
94};
95
96/**
97 * Your Skiplist object will be instantiated and called as such:
98 * Skiplist* obj = new Skiplist();
99 * bool param_1 = obj->search(target);
100 * obj->add(num);
101 * bool param_3 = obj->erase(num);
102 */
103

1type NodePointer = Node | null;
2
3class Node {
4    public value: number;
5    public forward: NodePointer[];
6
7    constructor(val: number, lvl: number) {
8        this.value = val;
9        this.forward = new Array<NodePointer>(lvl).fill(null);
10    }
11}
12
13// Probability and maximum level constants
14const PROBABILITY = 1 / 4;
15const MAX_LEVEL = 32;
16
17// Global variables replacing class members
18let head: Node = new Node(-1, MAX_LEVEL);
19let currentLevel: number = 0;
20
21// Helper function to generate a random level for a new node
22function randomLevel(): number {
23    let lvl: number = 1;
24    while (lvl < MAX_LEVEL && Math.random() < PROBABILITY) {
25        lvl++;
26    }
27    return lvl;
28}
29
30// Helper function to find the closest node before the target at the given level
31function findClosest(currentNode: Node, lvl: number, target: number): Node {
32    while (currentNode.forward[lvl] && currentNode.forward[lvl]!.value < target) {
33        currentNode = currentNode.forward[lvl]!;
34    }
35    return currentNode;
36}
37
38// Function to search for a target in the skip list
39function search(target: number) : boolean {
40    let currentNode: Node = head;
41    for (let i = currentLevel - 1; i >= 0; i--) {
42        // Move to the closest node to the target at the current level
43        currentNode = findClosest(currentNode, i, target);
44        // If the next node at this level is the target, return true
45        if (currentNode.forward[i] && currentNode.forward[i]!.value === target) {
46            return true;
47        }
48    }
49    // Target not found in the list
50    return false;
51}
52
53// Function to add a number to the skip list
54function add(number: number) : void {
55    let updateArray: Node[] = new Array<Node>(MAX_LEVEL);
56    let currentNode: Node = head;
57
58    // Finding place for the new node
59    for (let i = currentLevel - 1; i >= 0; i--) {
60        currentNode = findClosest(currentNode, i, number);
61        updateArray[i] = currentNode;
62    }
63  
64    let newLevel: number = randomLevel();
65    let newNode: Node = new Node(number, newLevel);
66
67    // Update current level if necessary
68    currentLevel = Math.max(currentLevel, newLevel);
69
70    for (let i = 0; i < newLevel; i++) {
71        // Splice the new node with the forward references
72        newNode.forward[i] = updateArray[i].forward[i];
73        updateArray[i].forward[i] = newNode;
74    }
75}
76
77// Function to remove a number from the skip list
78function erase(number: number) : boolean {
79    let updateArray: Node[] = new Array<Node>(MAX_LEVEL);
80    let currentNode: Node = head;
81    let found: boolean = false;
82
83    // Trying to find and unlink the node with the number to be deleted
84    for (let i = currentLevel - 1; i >= 0; i--) {
85        currentNode = findClosest(currentNode, i, number);
86        if (currentNode.forward[i] && currentNode.forward[i]!.value === number) {
87            // Skip over the node to be removed
88            currentNode.forward[i] = currentNode.forward[i]!.forward[i];
89            found = true;
90        }
91    }
92
93    // Adjust the current level if topmost levels are empty
94    while (currentLevel > 1 && !head.forward[currentLevel-1]) {
95        currentLevel--;
96    }
97
98    return found; // Indicate success of deletion
99}
100
101// Usage example (not part of the standalone functions)
102// let result = search(targetValue);
103// add(numberValue);
104// let wasDeleted = erase(numberValue);
105

Time and Space Complexity

Time Complexity

Search: The search method in the Skiplist has a time complexity of O(log n) on average. This is because the skiplist has a structure where each level has n/p nodes (where p is the probability used to decide the next level during insertion and n is the number of nodes), and this effectively reduces the amount of work needed to find an element compared to a singly linked list.
Add: The add method also has an average time complexity of O(log n) because it traverses the skip list to find the correct position to add the new node. The insertion operation itself is a constant time O(1) process after finding the position. The method potentially updates every level of the skip list (up to the max_level) in the worst case, which is bounded by O(log n) due to the probabilistic balancing of the skip list.
Erase: Similar to search and add, the erase method has an average time complexity of O(log n) because it needs to find the node to be deleted and update the pointers at various levels of the skip list.

Space Complexity

The space complexity of the skiplist is O(n log n) in the worst case. This is because each element in the skiplist can be part of multiple levels up to max_level, which is a logarithmic factor. Since the skiplist is probabilistically balanced, in practice, the space usage will be closer to O(n) due to not all elements having a node at each of max_level levels.

Note: n represents the number of elements in the skiplist, log is the logarithm to base 1/p related to the height of the skiplist, and p is the probability factor used in the random level selection.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know