In this guide, you will get 1206. Design Skiplist LeetCode Solution with the best time and space complexity. The solution to Design Skiplist problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
Artyom Kalinin [CC 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_list
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.
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.
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(|\texttt{add()}|)
1206. Design Skiplist LeetCode Solution in C++
struct Node {
int val = -1;
shared_ptr<Node> next;
shared_ptr<Node> down;
};
class Skiplist {
public:
bool search(int target) {
for (shared_ptr<Node> node = dummy; node; node = node->down) {
advance(node, target);
if (node->next && node->next->val == target)
return true;
}
return false;
}
void add(int num) {
// Collect nodes that are before the insertion point.
stack<shared_ptr<Node>> nodes;
for (shared_ptr<Node> node = dummy; node; node = node->down) {
advance(node, num);
nodes.push(node);
}
shared_ptr<Node> down;
bool shouldInsert = true;
while (shouldInsert && !nodes.empty()) {
shared_ptr<Node> prev = nodes.top();
nodes.pop();
prev->next = make_shared<Node>(num, prev->next, down);
down = prev->next;
shouldInsert = rand() % 2 == 1;
}
// Create a topmost new level dummy that points to the existing dummy.
if (shouldInsert)
dummy = make_shared<Node>(-1, nullptr, dummy);
}
bool erase(int num) {
bool found = false;
for (shared_ptr<Node> node = dummy; node; node = node->down) {
advance(node, num);
if (node->next && node->next->val == num) {
node->next = node->next->next;
found = true;
}
}
return found;
}
private:
shared_ptr<Node> dummy = make_shared<Node>(-1);
void advance(shared_ptr<Node>& node, int target) {
while (node->next && node->next->val < target)
node = node->next;
}
}; /* code provided by PROGIEZ */
1206. Design Skiplist LeetCode Solution in Java
class Node {
public int val;
public Node next;
public Node down;
public Node(int val, Node next, Node down) {
this.val = val;
this.next = next;
this.down = down;
}
}
class Skiplist {
public boolean search(int target) {
for (Node node = dummy; node != null; node = node.down) {
node = advance(node, target);
if (node.next != null && node.next.val == target)
return true;
}
return false;
}
public void add(int num) {
// Collect nodes that are before the insertion point.
Deque<Node> nodes = new ArrayDeque<>();
for (Node node = dummy; node != null; node = node.down) {
node = advance(node, num);
nodes.push(node);
}
Node down = null;
boolean shouldInsert = true;
while (shouldInsert && !nodes.isEmpty()) {
Node prev = nodes.poll();
prev.next = new Node(num, prev.next, down);
down = prev.next;
shouldInsert = Math.random() < 0.5;
}
// Create a topmost new level dummy that points to the existing dummy.
if (shouldInsert)
dummy = new Node(-1, null, dummy);
}
public boolean erase(int num) {
boolean found = false;
for (Node node = dummy; node != null; node = node.down) {
node = advance(node, num);
if (node.next != null && node.next.val == num) {
node.next = node.next.next;
found = true;
}
}
return found;
}
private Node dummy = new Node(-1, null, null);
private Node advance(Node node, int target) {
while (node.next != null && node.next.val < target)
node = node.next;
return node;
}
} // code provided by PROGIEZ
1206. Design Skiplist LeetCode Solution in Python
from dataclasses import dataclass
@dataclass
class Node:
val: int = -1
next: 'Node' = None
down: 'Node' = None
class Skiplist:
def __init__(self):
self.dummy = Node()
def search(self, target: int) -> bool:
node = self.dummy
while node:
while node.next and node.next.val < target:
node = node.next
if node.next and node.next.val == target:
return True
# Move to the next level
node = node.down
return False
def add(self, num: int) -> None:
# Collect nodes that are before the insertion point.
nodes = []
node = self.dummy
while node:
while node.next and node.next.val < num:
node = node.next
nodes.append(node)
# Move to the next level
node = node.down
shouldInsert = True
down = None
while shouldInsert and nodes:
node = nodes.pop()
node.next = Node(num, node.next, down)
down = node.next
shouldInsert = random.getrandbits(1) == 0
# Create a topmost new level dummy that points to the existing dummy.
if shouldInsert:
self.dummy = Node(-1, None, self.dummy)
def erase(self, num: int) -> bool:
node = self.dummy
found = False
while node:
while node.next and node.next.val < num:
node = node.next
if node.next and node.next.val == num:
# Delete the node
node.next = node.next.next
found = True
# Move to the next level
node = node.down
return found
# Move to the node s.t. node.next.val >= target
def _advance(self, node: Node, target: int) -> None:
while node.next and node.next.val < target:
node = node.next # code by PROGIEZ
