LeetCode Solutions Blog

Design Skiplist

Number: 1337

Difficulty: Hard

Paid? No

Problem Description

Design a Skiplist data structure that supports search, add, and erase operations. Each operation should have an average time complexity of O(log(n)). Duplicate values may exist, and if multiple instances are present, removing any one instance is acceptable.

Key Insights

A Skiplist is composed of multiple layers of sorted linked lists, where the bottom layer contains all the elements.
Higher layers accelerate search and insertion by “skipping” over many nodes, thus achieving O(log(n)) average time per operation.
Each node maintains an array (or list) of pointers for different levels.
The level of each new node is determined probabilistically (e.g., using a coin toss with probability 0.5), ensuring a balanced structure without costly rebalancing.
Adjust the maximum level if higher layers become empty after deletions.

Space and Time Complexity

Time Complexity:

Average: O(log(n)) per search, insertion, and deletion.
Worst-case: O(n) in degenerate scenarios. Space Complexity: O(n)

Solution

We implement the Skiplist using a Node structure that contains a value and an array of forward pointers (each pointer corresponding to a level). The Skiplist class maintains a head node that acts as a sentinel and tracks the current maximum level. For each operation:

For search, we start at the highest level and move forward as long as the next node’s value is less than the target before descending to the next level.
For insertion, we record the update path (a list of nodes whose forward pointers must be updated) while searching. Then, we generate a new random level for the new node and update the forward pointers accordingly.
For deletion, we similarly use the update array; if the target exists at level 0, we update the pointers at every level that includes the node and then reduce the current level if necessary. Random level generation is achieved by simulating a coin toss (probability 0.5) to decide whether to advance to a higher level, maintaining the probabilistic balance of the structure.

Code Solutions

import random

# Node class for Skiplist with a value and an array of forward pointers
class Node:
    def __init__(self, val, level):
        self.val = val
        # forward pointers for each level, initialized as None
        self.forward = [None] * (level + 1)

# Skiplist class with search, add, and erase operations
class Skiplist:
    def __init__(self):
        self.max_level = 16  # maximum allowed level
        self.head = Node(-1, self.max_level)  # sentinel head node with dummy value
        self.level = 0  # current highest level in the skiplist

    # Randomly generates a level for the new node using coin toss method
    def randomLevel(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.max_level:
            lvl += 1
        return lvl

    # Search for the target value in the skiplist
    def search(self, target):
        current = self.head
        # Start from the highest level and move down
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < target:
                current = current.forward[i]
        current = current.forward[0]
        return current is not None and current.val == target

    # Insert num into the skiplist
    def add(self, num):
        update = [None] * (self.max_level + 1)
        current = self.head
        # Find the path where new node should be inserted
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < num:
                current = current.forward[i]
            update[i] = current
        new_level = self.randomLevel()
        # If new node’s level exceeds current highest level, initialize update pointers for new levels
        if new_level > self.level:
            for i in range(self.level+1, new_level+1):
                update[i] = self.head
            self.level = new_level
        new_node = Node(num, new_level)
        # Insert node by adjusting pointers at each level
        for i in range(new_level+1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    # Erase a num from the skiplist if it exists; returns True if removed
    def erase(self, num):
        update = [None] * (self.max_level + 1)
        current = self.head
        # Find update pointers
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < num:
                current = current.forward[i]
            update[i] = current
        target = current.forward[0]
        if target is None or target.val != num:
            return False
        # Remove target by rearranging forward pointers
        for i in range(self.level+1):
            if update[i].forward[i] != target:
                break
            update[i].forward[i] = target.forward[i]
        # Adjust current level if necessary
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        return True