Problem statement

https://leetcode.com/problems/design-most-recently-used-queue/

Solution

One way to solve this problem is to use sqrt decomposition: we split our list into sqrt(n) parts of size sqrt(n). We will keep each part as deque. Each time we need to extract element we do the following:

  1. Find the place of chunk k1 and place inside chunk k2.
  2. Delete this element from chunk.
  3. For all the next chunks remove element from the beginning of chunk i+1 to end of chunk i: exactly for this we need queue, not stack.
  4. Finally, put element to the end of last chunk.

Complexity

Time complexity of init is O(n). Then for each fetch we will do it in O(sqrt(n)): this time we need both to delete element from chunk and update all other chunks. Space complexity is O(n).

Code

class MRUQueue:
    def __init__(self, n):
        self.m = m = int(sqrt(n))
        arr = list(range(n+1))
        self.data = [deque(arr[i:i+m]) for i in range(1, n+1, m)]

    def fetch(self, k):
        k1, k2 = divmod(k - 1, self.m)
        elem = self.data[k1][k2]
        del self.data[k1][k2]
        
        for i in range(k1, len(self.data) - 1):
            tmp = self.data[i + 1].popleft()
            self.data[i].append(tmp)
            
        self.data[-1].append(elem)
        return elem

Remark

There is also O(n log n) time complextiy for initialization and O(log n) complexity for fetch solution, using SortedList library..

Alternatively there is solution with complexity O(log(n+2000)^2) for fetch using BIT (or segment tree): create an array with size n+2000. each time we fetch a element, move that to the end of array. Binary search the position where there are exact k elements to the left. It can be improved to O(log(n+2000))