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);
 */

############

class Skiplist {
    private static final int MAX_LEVEL = 32;
    private static final double P = 0.25;
    private static final Random RANDOM = new Random();
    private final Node head = new Node(-1, MAX_LEVEL);
    private int level = 0;

    public Skiplist() {
    }

    public boolean search(int target) {
        Node curr = head;
        for (int i = level - 1; i >= 0; --i) {
            curr = findClosest(curr, i, target);
            if (curr.next[i] != null && curr.next[i].val == target) {
                return true;
            }
        }
        return false;
    }

    public void add(int num) {
        Node curr = head;
        int lv = randomLevel();
        Node node = new Node(num, lv);
        level = Math.max(level, lv);
        for (int i = level - 1; i >= 0; --i) {
            curr = findClosest(curr, i, num);
            if (i < lv) {
                node.next[i] = curr.next[i];
                curr.next[i] = node;
            }
        }
    }

    public boolean erase(int num) {
        Node curr = head;
        boolean ok = false;
        for (int i = level - 1; i >= 0; --i) {
            curr = findClosest(curr, i, num);
            if (curr.next[i] != null && curr.next[i].val == num) {
                curr.next[i] = curr.next[i].next[i];
                ok = true;
            }
        }
        while (level > 1 && head.next[level - 1] == null) {
            --level;
        }
        return ok;
    }

    private Node findClosest(Node curr, int level, int target) {
        while (curr.next[level] != null && curr.next[level].val < target) {
            curr = curr.next[level];
        }
        return curr;
    }

    private static int randomLevel() {
        int level = 1;
        while (level < MAX_LEVEL && RANDOM.nextDouble() < P) {
            ++level;
        }
        return level;
    }

    static class Node {
        int val;
        Node[] next;

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

/**
 * 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);
 */

// OJ: https://leetcode.com/problems/design-skiplist/
// Time: 
//      Skiplist: O(1)
//      search, add, erase: O(logN)
// Space: O(N)
struct Node {
    int val;
    Node *right = nullptr, *down = nullptr;
    Node(int val) : val(val) {};
    Node(int val, Node *right, Node *down) : val(val), right(right), down(down) {}
};
class Skiplist {
    Node *head = new Node(-1, nullptr, nullptr);
public:
    Skiplist() {}
    bool search(int target) {
        auto p = head;
        while (p) {
            while (p->right && p->right->val < target) p = p->right;
            if (p->right && p->right->val == target) return true;
            p = p->down;
        }
        return false;
    }
    void add(int n) {
        vector<Node*> insertionPoints;
        auto p = head;
        while (p) {
            while (p->right && p->right-> val < n) p = p->right;
            insertionPoints.push_back(p);
            p = p->down;
        }
        bool insertUp = true;
        Node *downNode = nullptr;
        while (insertUp && insertionPoints.size()) {
            auto ins = insertionPoints.back();
            insertionPoints.pop_back();
            ins->right = downNode = new Node(n, ins->right, downNode);
            insertUp = rand() % 2;
        }
        if (insertUp) head = new Node(-1, new Node(n, nullptr, downNode), head);
    }
    bool erase(int n) {
        auto p = head;
        bool seen = false;
        while (p) {
            while (p->right && p->right->val < n) p = p->right;
            if (p->right && p->right->val == n) {
                seen = true;
                auto rm = p->right;
                p->right = rm->right;
                delete rm;
            }
            p = p->down;
        }
        return seen;
    }
};

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)

func init() { rand.Seed(time.Now().UnixNano()) }

const (
	maxLevel = 16
	p        = 0.5
)

type node struct {
	val  int
	next []*node
}

func newNode(val, level int) *node {
	return &node{
		val:  val,
		next: make([]*node, level),
	}
}

type Skiplist struct {
	head  *node
	level int
}

func Constructor() Skiplist {
	return Skiplist{
		head:  newNode(-1, maxLevel),
		level: 1,
	}
}

func (this *Skiplist) Search(target int) bool {
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, target)
		if p.next[i] != nil && p.next[i].val == target {
			return true
		}
	}
	return false
}

func (this *Skiplist) Add(num int) {
	level := randomLevel()
	if level > this.level {
		this.level = level
	}
	node := newNode(num, level)
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if i < level {
			node.next[i] = p.next[i]
			p.next[i] = node
		}
	}
}

func (this *Skiplist) Erase(num int) bool {
	ok := false
	p := this.head
	for i := this.level - 1; i >= 0; i-- {
		p = findClosest(p, i, num)
		if p.next[i] != nil && p.next[i].val == num {
			p.next[i] = p.next[i].next[i]
			ok = true
		}
	}
	for this.level > 1 && this.head.next[this.level-1] == nil {
		this.level--
	}
	return ok
}

func findClosest(p *node, level, target int) *node {
	for p.next[level] != nil && p.next[level].val < target {
		p = p.next[level]
	}
	return p
}

func randomLevel() int {
	level := 1
	for level < maxLevel && rand.Float64() < p {
		level++
	}
	return level
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */

1206 - Design Skiplist

1206. Design Skiplist

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1206. Design Skiplist

Level

Description

Solution

All Problems

All Solutions