LeetCode 1206: Design Skiplist Solution

Master LeetCode problem 1206 (Design Skiplist), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1206. Design Skiplist

Hard

Linked List Design

Problem Explanation

Explanation:

A SkipList is a data structure that allows for efficient search, insertion, and deletion operations with an average time complexity of O(log(n)). It consists of multiple levels of linked lists where each level contains a subset of the elements from the lower level. By "skipping" elements at higher levels, operations can be performed more efficiently.

Algorithmic Idea:

Initialize a SkipList with a head node containing the value Integer.MIN_VALUE and maximum level MAX_LEVEL.
Each node in the SkipList contains a value, an array of pointers to nodes at different levels, and a level indicating its height.
Perform search, add, and erase operations by traversing the SkipList from the highest level to the lowest level.
When adding a new node, randomly determine its level to maintain the SkipList property.

Time Complexity:

Search, Add, and Erase operations: O(log(n)) on average, where n is the number of elements in the SkipList.

Space Complexity:

O(n) where n is the total number of elements stored in the SkipList.

Solution Code

class SkipList {
    private static final int MAX_LEVEL = 16;
    private Node head;

    public SkipList() {
        head = new Node(Integer.MIN_VALUE, MAX_LEVEL);
    }

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

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node curr = head;
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }

        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;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node curr = head;
        boolean found = false;

        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }

        curr = curr.forward[0];
        if (curr != null && curr.val == num) {
            found = true;
            for (int i = 0; i < curr.level; i++) {
                update[i].forward[i] = curr.forward[i];
            }
        }

        return found;
    }

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

    class Node {
        int val, level;
        Node[] forward;

        public Node(int val, int level) {
            this.val = val;
            this.level = level;
            forward = new Node[level];
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1206 (Design Skiplist)?

This page provides optimized solutions for LeetCode problem 1206 (Design Skiplist) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1206 (Design Skiplist)?

The time complexity for LeetCode 1206 (Design Skiplist) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1206 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1206 in Java, C++, or Python.

Back to LeetCode Solutions