Problem statement

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

Solution

Not very difficult problem from idea point of view: we need to follow the definition of skiplist, but it is quite heavy to code and avoid all corner cases.

  1. We will keep collection of linked lists, that is in fact data stracture with nodes, where each node can have right (next) and bottom (down) elements. In the beginning we initialize it as Node(-inf), that is one linked list with dummy head.
  2. Also I use axuilary function move, which given node p in some level and limit num move to the right in this list and find the rightest element where it is still less than this limit.
  3. How search(num) will work: we start from self.head and iterate first level. If next node after the node we stopped is equal to num, we can return True immidietly. In other case we go down.
  4. add(num) will work like this: first, we need to traverse our skiplist and find in each layer places before which we need to perform our insertion. Then we need to start from the top layer (that one which have full linked list) and decide with probability 0.5 (or in fact there are different choices can be done) if we want to go to the next layer or not. We pop last value from to_insert list and reattach ins.next = Node(num, ins.next, down). Also we go one level to the the down. Also it can happen that we need to crate one more layer, because we out of bound: for this we have condition self.head = Node(-inf, Node(num, None, down), self.head): what we have here is we create empty node Node(-inf, nxt, dwn), where nxt = Node(num, None, down) and dwn = down, that is new layer will look like -inf -> num now with vertical connection for num node as well to previous layer. 5.To erase(num) we start with self.head. Also we say that seen = False, we did not seen num yet. First, we move p to the right. Then if we have p.next.val == num, it means that we found our num and we put seen = True. Also we reattach node: p.next = p.next.next. And we go one level down. We repeat this for each level, that is we erase num from each level. In the end we return seen.

Complexity

Time complexity is O(log n) in average for search, add, erase and O(1) for num. Space complexity is O(n). For more details of proof, see wikipedia.

Code

class Node: 
    def __init__(self, val, nxt = None, dwn = None): 
        self.val = val
        self.next = nxt
        self.down = dwn
        
class Skiplist:
    def __init__(self):
        self.head = Node(-inf)
        
    def move(self, p, num):
        while p.next and p.next.val < num: p = p.next
        return p
                    
    def search(self, num):
        p = self.head
        while p:
            p = self.move(p, num)
            if p.next and p.next.val == num:
                return True
            else: 
                p = p.down
        return False

    def add(self, num):
        to_insert = []
        p = self.head
        while p:
            p = self.move(p, num)
            to_insert.append(p)
            p = p.down
            
        down = None
        coin = True
        while coin and len(to_insert) > 0:
            ins = to_insert.pop()
            ins.next = Node(num, ins.next, down)
            down = ins.next
            coin = random.choice([True, False])
            
        if coin:
            self.head = Node(-inf, Node(num, None, down), self.head)
            
       
    def erase(self, num):
        p = self.head
        seen = False
        while p:
            p = self.move(p, num)
            if p.next and p.next.val == num:
                seen = True
                p.next = p.next.next
            p = p.down
          
        return seen