LeetCode 1206 - Design Skiplist

LeetCode Problem 1206

Difficulty: 🔴 Hard
Topics: Linked List, Design

Solution

Problem Understanding

This problem asks us to implement a Skiplist from scratch, a probabilistic data structure that allows efficient search, insertion, and deletion operations. A skiplist consists of multiple levels of sorted linked lists, where each higher level acts as an "express lane" to skip over multiple elements in lower levels. The bottom-most level contains all elements in sorted order, while higher levels contain increasingly sparse subsets of elements.

The input consists of method calls to the Skiplist class, such as add, search, and erase. Each operation may modify the data structure or return a boolean indicating whether a value exists. The expected output is the sequence of results from the operations, such as True or False for searches and erases.

Constraints indicate that the number of operations can be up to 5 * 10^4, and values are bounded between 0 and 2 * 10^4. This rules out naive linear search or insertion for each operation, as O(n) per operation would be too slow for the upper bound. Additionally, duplicates are allowed, so the skiplist must support multiple occurrences of the same number.

Important edge cases include inserting duplicate values, erasing a number not present in the list, searching for numbers outside the current range, and handling an empty skiplist.

Approaches

The brute-force approach is to use a standard sorted linked list. To add a number, we traverse from the head to find the correct position. Searching or erasing also requires traversing the entire list if the element is not present. While this approach is correct, it requires O(n) time for every operation, which is too slow given the constraints.

The optimal approach uses the skiplist structure with multiple levels. Each node contains an array of forward pointers at different levels. Higher levels allow skipping over multiple nodes in lower levels. The key insight is that by choosing node levels randomly (with probability 0.5, for example), the expected number of levels is O(log n). This allows search, insertion, and deletion to run in expected O(log n) time.

Algorithm Walkthrough

1. Node Structure: Each node contains a value and an array of forward pointers, one for each level the node occupies. The head node has the maximum number of levels.
2. Random Level Generation: For insertion, we generate a random level using a geometric distribution, where each level has probability 0.5 of being added. This ensures a logarithmic height on average.
3. Search Operation: Start at the top-most level from the head node. Move forward while the next node’s value is less than the target. Drop down one level and repeat until the bottom level is reached. If the node’s value matches the target, return True; otherwise, return False.
4. Add Operation: Traverse similar to search while maintaining an update array that stores the last node at each level before the insertion point. Generate a random level for the new node, update forward pointers, and insert the new node at all appropriate levels.
5. Erase Operation: Similar traversal to add to fill the update array. If the target node exists, update the forward pointers to skip it. Adjust the current maximum level if necessary.

Why it works: The skiplist maintains sorted order at every level. The update array ensures that forward pointers are always correctly updated during insertion or deletion. Randomized levels ensure that on average, operations run in O(log n) time.

Python Solution

import random

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

class Skiplist:

    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = Node(-1, self.MAX_LEVEL)
        self.level = 0

    def random_level(self) -> int:
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, target: int) -> bool:
        current = self.head
        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

    def add(self, num: int) -> None:
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.head
        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
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(num, lvl)
        for i in range(lvl + 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 range(self.level, -1, -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.level + 1):
            if update[i].forward[i] != current:
                continue
            update[i].forward[i] = current.forward[i]
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        return True

Explanation: The Node class stores value and forward pointers. The Skiplist manages the head node, current level, and maximum level. random_level decides how many levels the new node should occupy. search traverses from top to bottom. add inserts while updating forward pointers at each level. erase removes the node while maintaining skiplist structure.

Go Solution

package main

import (
    "math/rand"
    "time"
)

type Node struct {
    val     int
    forward []*Node
}

type Skiplist struct {
    head  *Node
    level int
}

const MAX_LEVEL = 16
const P = 0.5

func Constructor() Skiplist {
    rand.Seed(time.Now().UnixNano())
    head := &Node{-1, make([]*Node, MAX_LEVEL+1)}
    return Skiplist{head: head, level: 0}
}

func randomLevel() int {
    lvl := 0
    for rand.Float64() < P && lvl < MAX_LEVEL {
        lvl++
    }
    return lvl
}

func (this *Skiplist) Search(target int) bool {
    current := this.head
    for i := this.level; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].val < target {
            current = current.forward[i]
        }
    }
    current = current.forward[0]
    return current != nil && current.val == target
}

func (this *Skiplist) Add(num int) {
    update := make([]*Node, MAX_LEVEL+1)
    current := this.head
    for i := this.level; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].val < num {
            current = current.forward[i]
        }
        update[i] = current
    }
    lvl := randomLevel()
    if lvl > this.level {
        for i := this.level + 1; i <= lvl; i++ {
            update[i] = this.head
        }
        this.level = lvl
    }
    newNode := &Node{num, make([]*Node, lvl+1)}
    for i := 0; i <= lvl; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
}

func (this *Skiplist) Erase(num int) bool {
    update := make([]*Node, MAX_LEVEL+1)
    current := this.head
    for i := this.level; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].val < num {
            current = current.forward[i]
        }
        update[i] = current
    }
    current = current.forward[0]
    if current == nil || current.val != num {
        return false
    }
    for i := 0; i <= this.level; i++ {
        if update[i].forward[i] != current {
            continue
        }
        update[i].forward[i] = current.forward[i]
    }
    for this.level > 0 && this.head.forward[this.level] == nil {
        this.level--
    }
    return true
}

Notes on Go: Go uses slices instead of arrays for forward pointers. Nil pointers represent the end of each