1206. Design Skiplist - Solution & Explanation

Q: Is Design Skiplist easy or hard?

Design Skiplist is classified as a hard problem because it requires implementing a probabilistic data structure with multiple levels and pointer updates. Understanding how traversal works across layers and how random level generation maintains balance makes the implementation challenging compared to typical linked list problems.

Q: Design Skiplist Python or Java solution

Most implementations maintain a head node with maximum levels and store forward pointers in each node. Python solutions typically generate random levels using the random module, while Java versions use Random or Math.random(). Both follow the same algorithm: search from the top level, track predecessors, and update pointers during insertion or deletion.

Q: How to solve Design Skiplist in O(log n)?

Use a layered linked list where higher levels skip over multiple nodes. Start searching from the top level and move right until the next value exceeds the target, then drop down a level. For insertion, track previous nodes at each level and update forward pointers after generating a random level for the new node. This probabilistic balancing keeps operations near O(log n).

Q: What is the best approach for Design Skiplist?

The classic skiplist implementation using random levels is the preferred approach. Each inserted node is assigned a level using probabilistic promotion (commonly p = 0.5), which creates multiple layers of linked lists. Searching starts at the top level and moves down while skipping large ranges of nodes. This design gives average O(log n) time for search, insert, and delete.

Q: Is Design Skiplist asked at Google/Amazon/Meta?

Skiplist design problems appear in system design and data structure interviews at large tech companies because they test understanding of probabilistic structures and ordered data operations. Variants of skiplist or ordered set design have been reported in interviews at companies like Google, Amazon, and Meta.

Q: What data structure is used in Design Skiplist?

A skiplist is built from multiple layers of sorted linked lists. Each node contains forward pointers to nodes in higher levels, allowing the algorithm to skip over large sections of the list during traversal. The structure combines ideas from linked lists, probabilistic balancing, and hierarchical indexing.

Q: What is the time complexity of Design Skiplist?

Search, insertion, and deletion run in O(log n) average time due to probabilistic balancing of levels. In the worst case the structure can degrade to O(n), but the probability is extremely small when random level generation is used. Space complexity is O(n) because nodes store multiple forward pointers.

The 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:

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.

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 * 10⁴
At most 5 * 10⁴ calls will be made to search, add, and erase.

Approach overview

Problem Overview: Design a data structure that supports search, add, and erase operations efficiently. The structure should behave like a balanced sorted list where operations run in logarithmic time on average.

Approach 1: Basic Level Implementation (O(n) search, O(n) space)

This approach builds a simplified skiplist using multiple linked lists stacked as levels. Each level skips over some nodes from the level below, but level promotion is handled manually rather than probabilistically. To search, you traverse horizontally until the next node exceeds the target, then drop down a level. Because balancing is not guaranteed, the structure can degrade and operations may reach O(n) time in the worst case. Useful for understanding how layered navigation works before introducing randomization.

Approach 2: Advanced Implementation with Probability Factor (Average O(log n) time, O(n) space)

This version introduces probabilistic balancing. When inserting a node, you repeatedly flip a virtual coin to decide how many levels the node should occupy. Higher levels contain fewer nodes, creating exponentially decreasing density. During search, you start from the highest level and move right while values are smaller than the target, dropping down levels when necessary. Random level assignment maintains balanced height statistically, giving average O(log n) search, insertion, and deletion.

Approach 3: Classic Skiplist with Random Levels (Average O(log n) time, O(n) space)

The classic skiplist maintains a head node with multiple forward pointers. Each inserted node receives a random level using geometric probability (commonly p = 0.5). During insertion, you track predecessor nodes at each level while traversing from the top layer downward. After generating the new node's level, you update forward pointers for all affected layers. This implementation closely follows the original skiplist design and provides efficient ordered operations comparable to balanced trees without complex rotations.

Approach 4: Deterministic Balanced Skiplist (O(log n) time, O(n) space)

A deterministic version removes randomness and enforces level structure using a fixed promotion rule. Nodes are promoted based on deterministic balancing criteria or fixed probability thresholds. When the structure becomes unbalanced, level reduction or restructuring keeps height near log n. This design improves predictability and avoids randomness while still maintaining fast navigation across layers. It is useful in environments where deterministic behavior is preferred.

Recommended for interviews: The classic probabilistic skiplist is what interviewers usually expect. Implementing random levels shows understanding of probabilistic balancing and layered traversal. The basic implementation helps explain the concept, but the optimized random-level design demonstrates stronger design skills and efficient use of linked list structures.

Approach 1: Approach 1: Basic Level Implementation

In the first approach, we'll implement a basic Skiplist with explicit support for multiple levels. Each node holds multiple forward pointers, one for each level, and we'll decide to promote nodes to higher levels based on a random mechanism.

The Skiplist maintains multiple levels in a hierarchical manner. Each element has a 50% chance to be promoted to the next level to efficiently handle search, insertion, and deletion operations.

Python

import random

class Node:
    def __init__(self, level, val=None):
        self.val = val
        self.forward = [None] * (level + 1)

class Skiplist:
    def __init__(self):
        self.maxLevel = 4  # Define the maximum possible levels for a node
        self.head = Node(self.maxLevel)
        self.levels = 0

    def randomLevel(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.maxLevel:
            lvl += 1
        return lvl

    def search(self, target: int) -> bool:
        current = self.head
        for i in reversed(range(self.levels + 1)):
            while current.forward[i] and current.forward[i].val < target:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.val == target

    def add(self, num: int) -> None:
        update = [None] * (self.maxLevel + 1)
        current = self.head

        for i in reversed(range(self.levels + 1)):
            while current.forward[i] and current.forward[i].val < num:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current is None or current.val != num:
            nodeLevel = self.randomLevel()
            if nodeLevel > self.levels:
                for i in range(self.levels + 1, nodeLevel + 1):
                    update[i] = self.head
                self.levels = nodeLevel
            newNode = Node(nodeLevel, num)
            for i in range(nodeLevel + 1):
                newNode.forward[i] = update[i].forward[i]
                update[i].forward[i] = newNode

    def erase(self, num: int) -> bool:
        update = [None] * (self.maxLevel + 1)
        current = self.head

        for i in reversed(range(self.levels + 1)):
            while current.forward[i] and current.forward[i].val < num:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current is None or current.val != num:
            return False

        for i in range(self.levels + 1):
            if update[i].forward[i] != current:
                break
            update[i].forward[i] = current.forward[i]

        while self.levels > 0 and self.head.forward[self.levels] == None:
            self.levels -= 1

        return True

This solution implements a Skiplist class using a head Node initialized with the maximum level of the Skiplist. The methods randomLevel, search, add, and erase utilize the structure's properties to efficiently handle elements.

1. search: Starts from the topmost level and moves laterally until the target is found or surpassed.

2. add: Uses an update array to keep track of pointers that need redirection upon adding a new node with a randomly assigned level.

3. erase: Similar to search, it finds the target node and adjusts the pointers to remove it if present.

Complexity

Time Complexity: O(log n) on average for search, add and erase operations.

Space Complexity: O(n), n being the number of elements in the Skiplist.

Try this approach in the editor

Approach 2: Approach 2: Advanced Level Implementation with Probability Factor

This approach further refines the previous implementation by introducing a configurable probability factor for determining node promotion to higher levels. This allows flexibility in tuning the space used versus time efficiency trade-offs.

Java

import java.util.Random;

class Node {
    int value;
    Node[] forward;
    public Node(int level, int value) {
        this.value = value;
        this.forward = new Node[level + 1];
    }
}

public class Skiplist {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    private final Node head = new Node(MAX_LEVEL, -1);
    private final Random random = new Random();
    private int level;

    public boolean search(int target) {
        Node current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < target) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == target;
    }

    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextDouble() < P) {
            lvl++;
        }
        return lvl;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < num) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }
        Node newNode = new Node(newLevel, num);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < num) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        current = current.forward[0];
        if (current == null || current.value != num) {
            return false;
        }
        for (int i = 0; i <= level; i++) {
            if (update[i].forward[i] != current) {
                break;
            }
            update[i].forward[i] = current.forward[i];
        }
        while (level > 0 && head.forward[level] == null) {
            level--;
        }
        return true;
    }
}

This Java solution inculcates configurable probability support, influencing how frequently nodes are elevated up levels. The Skiplist class holds a constant probability P, tuned to the desired performance vs space trade-offs.

The rest of the structure and logic adhere similarly to the previous foundational approach but offers finer control over node promotions through the probabilistic function.

Complexity

Time Complexity: O(log n) on average for search, add and erase operations.

Space Complexity: O(n * log n), due to tower-like structure supporting flexible balancing.

Try this approach in the editor

Approach 3: Approach 1: Classic Skiplist Implementation with Random Levels

This approach involves creating a skiplist using multiple levels of linked lists. Each element has a chance to appear in the higher-level lists. This approach gives an average time complexity of O(log n) for search, insert, and delete operations.

We use random coin flips (or a function) to determine the level of each new node. This randomness ensures the balance of the skiplist dynamically.

Steps:

Design Node and Skiplist classes.
Implement search(), add(), and erase() functions.
Use randomness to decide the node's level while inserting.

Python

import random

class Node:
    def __init__(self, value=None, level=0):
        self.value = value
        self.forward = [None] * (level + 1)

class Skiplist:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = Node(None, self.MAX_LEVEL)

    def random_level(self):
        level = 0
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    def search(self, target: int) -> bool:
        current = self.head
        for i in reversed(range(self.MAX_LEVEL + 1)):
            while current.forward[i] and current.forward[i].value < target:
                current = current.forward[i]
        current = current.forward[0]
        return current is not None and current.value == target

    def add(self, num: int) -> None:
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.head
        for i in reversed(range(self.MAX_LEVEL + 1)):
            while current.forward[i] and current.forward[i].value < num:
                current = current.forward[i]
            update[i] = current
        level = self.random_level()
        new_node = Node(num, level)
        for i in range(level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def erase(self, num: int) -> bool:
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.head
        for i in reversed(range(self.MAX_LEVEL + 1)):
            while current.forward[i] and current.forward[i].value < num:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]
        if current is None or current.value != num:
            return False
        for i in range(self.MAX_LEVEL + 1):
            if update[i].forward[i] != current:
                break
            update[i].forward[i] = current.forward[i]
        return True

Java

import java.util.Random;
import java.util.ArrayList;

class Skiplist {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    private final Node head;
    private final Random random;

    private class Node {
        int value;
        ArrayList<Node> forward;

        Node(int value, int level) {
            this.value = value;
            forward = new ArrayList<>(level);
            for (int i = 0; i < level; i++) {
                forward.add(null);
            }
        }
    }

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        random = new Random();
    }

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

    public boolean search(int target) {
        Node current = head;
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).value < target) {
                current = current.forward.get(i);
            }
        }
        current = current.forward.get(0);
        return current != null && current.value == target;
    }

    public void add(int num) {
        Node current = head;
        ArrayList<Node> update = new ArrayList<>(MAX_LEVEL);
        for (int i = 0; i < MAX_LEVEL; i++) {
            update.add(null);
        }
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).value < num) {
                current = current.forward.get(i);
            }
            update.set(i, current);
        }
        int level = randomLevel();
        Node newNode = new Node(num, level);
        for (int i = 0; i < level; i++) {
            newNode.forward.set(i, update.get(i).forward.get(i));
            update.get(i).forward.set(i, newNode);
        }
    }

    public boolean erase(int num) {
        Node current = head;
        ArrayList<Node> update = new ArrayList<>(MAX_LEVEL);
        for (int i = 0; i < MAX_LEVEL; i++) {
            update.add(null);
        }
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).value < num) {
                current = current.forward.get(i);
            }
            update.set(i, current);
        }
        current = current.forward.get(0);
        if (current == null || current.value != num) return false;
        for (int i = 0; i < MAX_LEVEL; i++) {
            if (update.get(i).forward.get(i) != current) break;
            update.get(i).forward.set(i, current.forward.get(i));
        }
        return true;
    }
}

C++

#include <iostream>
#include <vector>
#include <cstdlib>

class Node {
public:
    int value;
    std::vector<Node*> forward;
    Node(int value, int level) : value(value), forward(level, nullptr) {}
};

class Skiplist {
public:
    const static int MAX_LEVEL = 16;
    const static float P;

    Node* head;

    Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }

    int randomLevel() {
        int level = 1;
        while ((((float) rand()) / RAND_MAX) < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    bool search(int target) {
        Node* current = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (current->forward[i] && current->forward[i]->value < target) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return current && current->value == target;
    }

    void add(int num) {
        Node* current = head;
        std::vector<Node*> update(MAX_LEVEL);
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (current->forward[i] && current->forward[i]->value < num) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        int level = randomLevel();
        Node* newNode = new Node(num, level);
        for (int i = 0; i < level; ++i) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    bool erase(int num) {
        Node* current = head;
        std::vector<Node*> update(MAX_LEVEL);
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (current->forward[i] && current->forward[i]->value < num) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        current = current->forward[0];
        if (!current || current->value != num) return false;
        for (int i = 0; i < MAX_LEVEL; ++i) {
            if (update[i]->forward[i] != current) break;
            update[i]->forward[i] = current->forward[i];
        }
        delete current;
        return true;
    }
};

const float Skiplist::P = 0.5;

This solution uses a Node class to represent each node in the skiplist and a Skiplist class to manage the operations. The random_level method randomly determines the level of each node, effectively balancing the skiplist by distributing nodes over multiple levels.

The search function looks for a given target by traversing from the topmost level down to level 0, taking advantage of the skiplist's structure to skip over large segments.

The add function not only inserts the new node at the found position but also handles node insertion at all appropriate levels according to the determined node level. The erase function removes the node if it exists, updating all pointers affected by the removal.

Complexity

Time Complexity: For each operation (search, add, erase), the expected average time complexity is O(log n) because of the multi-level linked list design.

Space Complexity: O(n) because each node maintains up to a logarithmic number of pointers.

Try this approach in the editor

Approach 4: Approach 2: Deterministic Balanced Skiplist with Fixed Coin Probability and Level Reduction

In this method, a deterministic approach is followed that emulates random choice but gives a semblance of control. Here, instead of true randomness, fixed levels for new nodes can be decided after every operation by ensuring a balance factor (based on a pre-defined coin probability) is maintained.

This approach ensures that skiplists retain efficient time complexity while assisting in balancing node distributions across levels.

JavaScript

class Skiplist {
  constructor() {
    this.head = new Node(-1, Skiplist.MAX_LEVEL);
  }

  static MAX_LEVEL = 16;
  static P = 0.5;

  randomLevel() {
    let level = 1;
    while (Math.random() < Skiplist.P && level < Skiplist.MAX_LEVEL) {
      level += 1;
    }
    return level;
  }

  search(target) {
    let current = this.head;
    for (let i = Skiplist.MAX_LEVEL - 1; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < target) {
        current = current.forward[i];
      }
    }
    current = current.forward[0];
    return current !== undefined && current.value === target;
  }

  add(num) {
    const update = new Array(Skiplist.MAX_LEVEL).fill(null);
    let current = this.head;
    for (let i = Skiplist.MAX_LEVEL - 1; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < num) {
        current = current.forward[i];
      }
      update[i] = current;
    }
    const level = this.randomLevel();
    const newNode = new Node(num, level);
    for (let i = 0; i < level; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }

  erase(num) {
    const update = new Array(Skiplist.MAX_LEVEL).fill(null);
    let current = this.head;
    for (let i = Skiplist.MAX_LEVEL - 1; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < num) {
        current = current.forward[i];
      }
      update[i] = current;
    }
    current = current.forward[0];
    if (current === undefined || current.value !== num) return false;
    for (let i = 0; i < Skiplist.MAX_LEVEL; i++) {
      if (update[i].forward[i] !== current) break;
      update[i].forward[i] = current.forward[i];
    }
    return true;
  }
}

class Node {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level).fill(null);
  }
}

using System;
using System.Collections.Generic;

public class Node {
    public int Value;
    public List<Node> Forward;
    public Node(int value, int level) {
        Value = value;
        Forward = new List<Node>(new Node[level + 1]);
    }
}

public class Skiplist {
    private const int MAX_LEVEL = 16;
    private const double P = 0.5;
    private Node head;
    private Random random;

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        random = new Random();
    }

    private int RandomLevel() {
        int level = 1;
        while (random.NextDouble() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    public bool Search(int target) {
        var current = head;
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.Forward[i] != null && current.Forward[i].Value < target) {
                current = current.Forward[i];
            }
        }
        current = current.Forward[0];
        return current != null && current.Value == target;
    }

    public void Add(int num) {
        var current = head;
        var update = new Node[MAX_LEVEL];
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.Forward[i] != null && current.Forward[i].Value < num) {
                current = current.Forward[i];
            }
            update[i] = current;
        }
        int level = RandomLevel();
        var newNode = new Node(num, level);
        for (int i = 0; i < level; i++) {
            newNode.Forward[i] = update[i].Forward[i];
            update[i].Forward[i] = newNode;
        }
    }

    public bool Erase(int num) {
        var current = head;
        var update = new Node[MAX_LEVEL];
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.Forward[i] != null && current.Forward[i].Value < num) {
                current = current.Forward[i];
            }
            update[i] = current;
        }
        current = current.Forward[0];
        if (current == null || current.Value != num) return false;
        for (int i = 0; i < MAX_LEVEL; i++) {
            if (update[i].Forward[i] != current) break;
            update[i].Forward[i] = current.Forward[i];
        }
        return true;
    }
}

This solution implements a Javascript skiplist utilizing a Node class with array-based forward pointers. The skiplist operations manipulate the pointers strategically, following a fixed structure for level determination maintained by rehashed 'random' probabilities.

It effectively handles search, insert, and removal operations while maintaining overall balance across levels under deterministic configurations.

Complexity

Time Complexity: Each main operation is justified through steps averaging complexity limited by the log scale of maximum elements, maintaining average O(log n) efficiency.

Space Complexity: The space, predominantly used for structure maintenance in nodes, fits within an O(n) bound.

Try this approach in the editor

Approach 5: Data Structure

The core idea of a skip list is to use multiple "levels" to store data, with each level acting as an index. Data starts from the bottom level linked list and gradually rises to higher levels, eventually forming a multi-level linked list structure. Each level's nodes only contain part of the data, allowing for jumps to reduce search time.

In this problem, we use a Node class to represent the nodes of the skip list. Each node contains a val field and a next array. The length of the array is level, indicating the next node at each level. We use a Skiplist class to implement the skip list operations.

The skip list contains a head node head and the current maximum level level. The head node's value is set to -1 to mark the starting position of the list. We use a dynamic array next to store pointers to successor nodes.

For the search operation, we start from the highest level of the skip list and traverse downwards until we find the target node or determine that the target node does not exist. At each level, we use the find_closest method to jump to the node closest to the target.

For the add operation, we first randomly decide the level of the new node. Then, starting from the highest level, we find the node closest to the new value at each level and insert the new node at the appropriate position. If the level of the inserted node is greater than the current maximum level of the skip list, we need to update the level of the skip list.

For the erase operation, similar to the search operation, we traverse each level of the skip list to find and delete the target node. When deleting a node, we need to update the next pointers at each level. If the highest level of the skip list has no nodes, we need to decrease the level of the skip list.

Additionally, we define a random_level method to randomly decide the level of the new node. This method generates a random number between [1, max_level] until the generated random number is greater than or equal to p. We also have a find_closest method to find the node closest to the target value at each level.

The time complexity of the above operations is O(log n), where n is the number of nodes in the skip list. The space complexity is O(n).

TypeScript

class Node {
    val: number;
    next: (Node | null)[];

    constructor(val: number, level: number) {
        this.val = val;
        this.next = Array(level).fill(null);
    }
}

class Skiplist {
    private static maxLevel: number = 32;
    private static p: number = 0.25;
    private head: Node;
    private level: number;

    constructor() {
        this.head = new Node(-1, Skiplist.maxLevel);
        this.level = 0;
    }

    search(target: number): boolean {
        let curr = this.head;
        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, target);
            if (curr.next[i] && curr.next[i]!.val === target) {
                return true;
            }
        }
        return false;
    }

    add(num: number): void {
        let curr = this.head;
        const level = this.randomLevel();
        const node = new Node(num, level);
        this.level = Math.max(this.level, level);

        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, num);
            if (i < level) {
                node.next[i] = curr.next[i];
                curr.next[i] = node;
            }
        }
    }

    erase(num: number): boolean {
        let curr = this.head;
        let ok = false;

        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, num);
            if (curr.next[i] && curr.next[i]!.val === num) {
                curr.next[i] = curr.next[i]!.next[i];
                ok = true;
            }
        }

        while (this.level > 1 && this.head.next[this.level - 1] === null) {
            this.level--;
        }

        return ok;
    }

    private findClosest(curr: Node, level: number, target: number): Node {
        while (curr.next[level] && curr.next[level]!.val < target) {
            curr = curr.next[level]!;
        }
        return curr;
    }

    private randomLevel(): number {
        let level = 1;
        while (level < Skiplist.maxLevel && Math.random() < Skiplist.p) {
            level++;
        }
        return level;
    }
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * var obj = new Skiplist()
 * var param_1 = obj.search(target)
 * obj.add(num)
 * var param_3 = obj.erase(num)
 */

func init() { rand.Seed(time.Now().UnixNano()) }

const (
	maxLevel = 16
	p        = 0.5
)

type node struct {
	val  int
	next []*node
}

func newNode(val, level int) *node {
	return &node{
		val:  val,
		next: make([]*node, level),
	}
}

type Skiplist struct {
	head  *node
	level int
}

func Constructor() Skiplist {
	return Skiplist{
		head:  newNode(-1, maxLevel),
		level: 1,
	}
}

func (this *Skiplist) Search(target int) bool {
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, target)
		if p.next[i] != nil && p.next[i].val == target {
			return true
		}
	}
	return false
}

func (this *Skiplist) Add(num int) {
	level := randomLevel()
	if level > this.level {
		this.level = level
	}
	node := newNode(num, level)
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if i < level {
			node.next[i] = p.next[i]
			p.next[i] = node
		}
	}
}

func (this *Skiplist) Erase(num int) bool {
	ok := false
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if p.next[i] != nil && p.next[i].val == num {
			p.next[i] = p.next[i].next[i]
			ok = true
		}
	}
	for this.level > 1 && this.head.next[this.level-1] == nil {
		this.level--
	}
	return ok
}

func findClosest(p *node, level, target int) *node {
	for p.next[level] != nil && p.next[level].val < target {
		p = p.next[level]
	}
	return p
}

func randomLevel() int {
	level := 1
	for level < maxLevel && rand.Float64() < p {
		level++
	}
	return level
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Basic Level Implementation	Time Complexity: O(log n) on average for search, add and erase operations. Space Complexity: O(n), n being the number of elements in the Skiplist.
Approach 2: Advanced Level Implementation with Probability Factor	Time Complexity: O(log n) on average for search, add and erase operations. Space Complexity: O(n * log n), due to tower-like structure supporting flexible balancing.
Approach 1: Classic Skiplist Implementation with Random Levels	Time Complexity: For each operation (search, add, erase), the expected average time complexity is O(log n) because of the multi-level linked list design. Space Complexity: O(n) because each node maintains up to a logarithmic number of pointers.
Approach 2: Deterministic Balanced Skiplist with Fixed Coin Probability and Level Reduction	Time Complexity: Each main operation is justified through steps averaging complexity limited by the log scale of maximum elements, maintaining average O(log n) efficiency. Space Complexity: The space, predominantly used for structure maintenance in nodes, fits within an O(n) bound.
Data Structure	–

Complexity analysis

Approach	Time	Space	When to Use
Basic Level Implementation	O(n)	O(n)	Learning the layered linked-list concept before adding probabilistic balancing
Advanced Probability-Based Skiplist	O(log n) average	O(n)	General implementation where probabilistic balancing keeps operations fast
Classic Random Level Skiplist	O(log n) average	O(n)	Most common interview implementation matching original skiplist design
Deterministic Balanced Skiplist	O(log n)	O(n)	Systems requiring predictable structure without randomness

Frequently asked questions

Is Design Skiplist easy or hard?

Design Skiplist is classified as a hard problem because it requires implementing a probabilistic data structure with multiple levels and pointer updates. Understanding how traversal works across layers and how random level generation maintains balance makes the implementation challenging compared to typical linked list problems.

Design Skiplist Python or Java solution

Most implementations maintain a head node with maximum levels and store forward pointers in each node. Python solutions typically generate random levels using the random module, while Java versions use Random or Math.random(). Both follow the same algorithm: search from the top level, track predecessors, and update pointers during insertion or deletion.

How to solve Design Skiplist in O(log n)?

Use a layered linked list where higher levels skip over multiple nodes. Start searching from the top level and move right until the next value exceeds the target, then drop down a level. For insertion, track previous nodes at each level and update forward pointers after generating a random level for the new node. This probabilistic balancing keeps operations near O(log n).

What is the best approach for Design Skiplist?

The classic skiplist implementation using random levels is the preferred approach. Each inserted node is assigned a level using probabilistic promotion (commonly p = 0.5), which creates multiple layers of linked lists. Searching starts at the top level and moves down while skipping large ranges of nodes. This design gives average O(log n) time for search, insert, and delete.

Is Design Skiplist asked at Google/Amazon/Meta?

Skiplist design problems appear in system design and data structure interviews at large tech companies because they test understanding of probabilistic structures and ordered data operations. Variants of skiplist or ordered set design have been reported in interviews at companies like Google, Amazon, and Meta.

What data structure is used in Design Skiplist?

A skiplist is built from multiple layers of sorted linked lists. Each node contains forward pointers to nodes in higher levels, allowing the algorithm to skip over large sections of the list during traversal. The structure combines ideas from linked lists, probabilistic balancing, and hierarchical indexing.

What is the time complexity of Design Skiplist?

Search, insertion, and deletion run in O(log n) average time due to probabilistic balancing of levels. In the worst case the structure can degrade to O(n), but the probability is extremely small when random level generation is used. Space complexity is O(n) because nodes store multiple forward pointers.

Design Skiplist solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Basic Level Implementation

Approach 2: Approach 2: Advanced Level Implementation with Probability Factor

Approach 3: Approach 1: Classic Skiplist Implementation with Random Levels

Approach 4: Approach 2: Deterministic Balanced Skiplist with Fixed Coin Probability and Level Reduction

Approach 5: Data Structure

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Skiplist solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Basic Level Implementation

Approach 2: Approach 2: Advanced Level Implementation with Probability Factor

Approach 3: Approach 1: Classic Skiplist Implementation with Random Levels

Approach 4: Approach 2: Deterministic Balanced Skiplist with Fixed Coin Probability and Level Reduction

Approach 5: Data Structure

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems