#1206

Hard

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Design Skiplist

Implement a Skiplist efficiently using linked-list pointer manipulation to support search, add, and erase operations in logarithmic time.

linked list design

Problem Statement

Design a Skiplist data structure without using built-in libraries. A Skiplist maintains multiple levels of linked lists, allowing fast insertion, search, and deletion by skipping over elements with higher-level links. Each level provides shortcuts, reducing traversal time from linear to logarithmic complexity.

Implement the Skiplist with methods to add a number, erase a number, and search for a number. Operations should maintain the Skiplist's layered structure and ensure correctness of all forward pointers after modifications, handling edge cases like duplicates and non-existent elements.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Solution Approach

Layered Linked List Structure

Create multiple levels of linked lists, where each node may appear in several consecutive levels. Higher levels allow skipping multiple nodes to reduce search time. Each node maintains forward pointers for each level it participates in, enabling efficient traversal.

Randomized Level Assignment

When adding a new node, randomly determine its level, promoting it to higher levels with a fixed probability (commonly 0.5). This randomization ensures expected logarithmic height, balancing search, add, and erase performance without complex rebalancing.

Pointer Updates During Operations

For add and erase operations, maintain an array of update pointers for each level to correctly adjust forward links. Search uses these update pointers to traverse levels from top to bottom efficiently. Carefully handle edge cases to prevent dangling references or skipped nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) expected for search, add, and erase due to randomized level heights and top-down traversal. Space complexity depends on the number of nodes and levels, typically O(n log n) in expectation, because each node stores multiple forward pointers.

What Interviewers Usually Probe

Candidate correctly identifies layered linked-list pointer manipulation.
Handles random level assignment for nodes and explains expected performance.
Properly updates forward pointers during insertions and deletions without errors.

Common Pitfalls or Variants

Common pitfalls

Incorrectly updating forward pointers leading to broken links.
Neglecting randomization for node levels, causing linear-time operations.
Failing to handle edge cases like duplicate values or non-existent elements during erase.

Follow-up variants

Implement Skiplist with custom probability for level promotion to optimize for search-heavy workloads.
Support range search queries using additional pointers or skip pointers within levels.
Design a persistent Skiplist that preserves previous versions while allowing insertions and deletions.

FAQ

What is the best approach to implement Design Skiplist efficiently?

Use a multi-level linked list with randomized node levels and carefully update forward pointers during add, erase, and search.

Why is random level assignment important in a Skiplist?

Randomizing levels ensures the Skiplist remains balanced in expectation, giving O(log n) time for operations without complex rebalancing.

How do I prevent pointer errors when erasing nodes?

Maintain an update array to store predecessors at each level and adjust forward pointers consistently to avoid dangling links.

Can Design Skiplist handle duplicates?

Yes, duplicates can be managed by allowing multiple nodes with the same value and correctly updating pointers during insertions and deletions.

What is the key pattern in Design Skiplist?

Linked-list pointer manipulation across multiple levels is the central pattern, enabling efficient traversal and modification of the Skiplist.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

class Node:
    __slots__ = ['val', 'next']

    def __init__(self, val: int, level: int):
        self.val = val
        self.next = [None] * level


class Skiplist:
    max_level = 32
    p = 0.25

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

    def search(self, target: int) -> bool:
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            curr = self.find_closest(curr, i, target)
            if curr.next[i] and curr.next[i].val == target:
                return True
        return False

    def add(self, num: int) -> None:
        curr = self.head
        level = self.random_level()
        node = Node(num, level)
        self.level = max(self.level, level)
        for i in range(self.level - 1, -1, -1):
            curr = self.find_closest(curr, i, num)
            if i < level:
                node.next[i] = curr.next[i]
                curr.next[i] = node

    def erase(self, num: int) -> bool:
        curr = self.head
        ok = False
        for i in range(self.level - 1, -1, -1):
            curr = self.find_closest(curr, i, num)
            if curr.next[i] and curr.next[i].val == num:
                curr.next[i] = curr.next[i].next[i]
                ok = True
        while self.level > 1 and self.head.next[self.level - 1] is None:
            self.level -= 1
        return ok

    def find_closest(self, curr: Node, level: int, target: int) -> Node:
        while curr.next[level] and curr.next[level].val < target:
            curr = curr.next[level]
        return curr

    def random_level(self) -> int:
        level = 1
        while level < self.max_level and random.random() < self.p:
            level += 1
        return level


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

Continue Practicing

#1472 design browser history #1670 design front middle back queue #707 design linked list