Formatted question description: https://leetcode.ca/all/1206.html

1206. Design Skiplist

Level

Hard

Description

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

Image text

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).

To be specific, your design should include these functions:

  • bool search(int target): Return whether the target exists in the Skiplist or not.
  • void add(int num): Insert a value into the SkipList.
  • bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

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 <= 20000
  • At most 50000 calls will be made to search, add, and erase.

Solution

Create a class Node that contains val, prev, next and down, which correspond to the node’s value, its previous node in the same level, its next node in the same level, and the node with the same value in the lower level.

In the class Skiplist, maintain a list heads that stores each level’s header.

For the constructor, initialize heads and add a new node with value -1 into heads.

For method search, search from the highest level. At each level, if target is found, return true. Otherwise, move to the next node if the next node’s value is less than target, or go to the lower level if the next node does not exist or the next node’s value is greater than target. If target is not found, return false.

For method add, first find the corresponding node in each level (the node that has value num or if no node with value num exists, the rightmost node that has value less than num), and then insert the new node with value num at the correct position in the lowest level. Then do coin flip. If the coin flip result is true, then find the position of insertion in the higher level and do insertion, or create a new level and insert the node just after the header of the level. Otherwise, stop processing further.

For method erase, first find the corresponding node in each level, as in method add, and then for each level, delete the corresponding node if the node’s value equals num. Return true if and only if at least one node is deleted.

class Skiplist {
    List<Node> heads;

    public Skiplist() {
        heads = new ArrayList<Node>();
        heads.add(new Node(-1));
    }
    
    public boolean search(int target) {
        int level = heads.size() - 1;
        Node searchNode = heads.get(level);
        while (level >= 0) {
            while (searchNode.next != null) {
                Node nextNode = searchNode.next;
                if (nextNode.val == target)
                    return true;
                else if (nextNode.val < target)
                    searchNode = nextNode;
                else
                    break;
            }
            level--;
            searchNode = searchNode.down;
        }
        return false;
    }
    
    public void add(int num) {
        Node node = new Node(num);
        Node[] nodes = searchNodes(num);
        int levels = nodes.length;
        Node prev = nodes[0];
        Node next = prev.next;
        node.prev = prev;
        node.next = next;
        if (prev != null)
            prev.next = node;
        if (next != null)
            next.prev = node;
        int level = 1;
        while (coinFlip()) {
            Node levelHead;
            if (level < levels)
                levelHead = nodes[level];
            else {
                levelHead = new Node(-level - 1);
                heads.add(levelHead);
                levelHead.down = heads.get(level - 1);
            }
            Node levelNode = new Node(num);
            levelNode.down = node;
            Node levelNext = levelHead.next;
            levelNode.prev = levelHead;
            levelNode.next = levelNext;
            if (levelHead != null)
                levelHead.next = levelNode;
            if (levelNext != null)
                levelNext.prev = levelNode;
            node = levelNode;
            level++;
        }
    }
    
    public boolean erase(int num) {
        Node[] nodes = searchNodes(num);
        int levels = nodes.length;
        boolean flag = false;
        for (int i = 0; i < levels; i++) {
            Node node = nodes[i];
            if (node.val == num) {
                flag = true;
                delete(node);
            }
        }
        return flag;
    }

    private Node[] searchNodes(int target) {
        Node[] nodes = new Node[heads.size()];
        int level = heads.size() - 1;
        Node searchNode = heads.get(level);
        while (level >= 0) {
            while (searchNode.next != null) {
                Node nextNode = searchNode.next;
                if (nextNode.val == target) {
                    searchNode = nextNode;
                    while (level >= 0) {
                        nodes[level] = searchNode;
                        searchNode = searchNode.down;
                        level--;
                    }
                    return nodes;
                } else if (nextNode.val < target)
                    searchNode = nextNode;
                else
                    break;
            }
            nodes[level] = searchNode;
            level--;
            searchNode = searchNode.down;
        }
        return nodes;
    }

    private boolean coinFlip() {
        int coinFlip = (int) (Math.random() * 2);
        return coinFlip == 1;
    }

    private void delete(Node node) {
        Node prev = node.prev, next = node.next;
        if (prev != null)
            prev.next = next;
        if (next != null)
            next.prev = prev;
    }
}

class Node {
    int val;
    Node prev;
    Node next;
    Node down;

    public Node(int val) {
        this.val = val;
        prev = null;
        next = null;
        down = null;
    }
}

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

All Problems

All Solutions