1756. Design Most Recently Used Queue

class MRUQueue:
    def __init__(self, n: int):
        pass

    def fetch(self, k: int):
        pass

Problem¶

Maintain a queue initially containing \(1,\ldots,n\). fetch(k) removes the 1-indexed \(k\)th element, appends it to the end, and returns it.

MRUQueue(4) → [1, 2, 3, 4]
fetch(2)   → returns 2; queue = [1, 3, 4, 2]
fetch(3)   → returns 4; queue = [1, 3, 2, 4]
fetch(4)   → returns 4; queue = [1, 3, 2, 4]

Key trick¶

Use square-root decomposition: split the queue into blocks of about \(\sqrt n\) elements; after removal, pull one element from each following block to restore block sizes.

Trap¶

A linked list makes moving a known node cheap, but finding the \(k\)th node still costs \(O(n)\); positions are not stable keys as in an LRU cache.

Why is it interesting?¶

It separates the cost of locating an element by rank from the cost of moving it, illustrating how blocking balances both.

Python solution¶

from collections import deque
import math


class MRUQueue:
    def __init__(self, n: int):
        self.n = n
        size = math.isqrt(n)
        self.blocks = [
            deque(range(start, min(start + size, n + 1)))
            for start in range(1, n + 1, size)
        ]

    def fetch(self, k: int) -> int:
        if k == self.n:
            return self.blocks[-1][-1]

        # Find the block containing the kth element.
        for i, block in enumerate(self.blocks):
            if k > len(block):
                k -= len(block)
            else:
                # Indexed access and deletion cost O(block size).
                val = block[k - 1]
                del block[k - 1]
                break

        # Shift the gap right, preserving each block's original size.
        # Each popleft/append pair costs O(1).
        for j in range(i, len(self.blocks) - 1):
            self.blocks[j].append(self.blocks[j + 1].popleft())

        self.blocks[-1].append(val)
        return val

• Initialization: \(O(n)\) time.
• Each fetch: \(O(\sqrt n)\) time; fetching the last element takes \(O(1)\).
• Space: \(O(n)\).

Comment on my solution¶

• Your diagnosis is correct: moving a node is constant time, but locating it by rank is the bottleneck.
• The constructor never inserts nodes containing \(1,\ldots,n\), so the first fetch attempts to remove a sentinel.
• tail is undefined in fetch; both references must be self.tail.
• Once repaired, your approach takes \(O(k)\) per fetch, worst-case \(O(n)\), with \(O(n)\) space.
• Prefer fetch(self, k) so the position is not confused with the queue size.

# Ideas:
# - it reminds me of LRU cache problem
#   - which uses a doubly linked list move/remove element in O(1)
#   - and a hash map mapping key to node
# - moving the kth element to the end invalid indices of the elements
#   after (k+1)
#  1,2,3,4,5,6,7,8
# [1,2,3,4,5,6,7,8]
# fetch(4)
#  1,2,3,4,5,6,7,8
# [1,2,3,5,6,7,8,4]
#        . . . . . (these indices have changed)
# [1,2,3,.,5,6,7,8,4]
# fetch(5)
#
# [1,2,3]
# [5,6,7,8,4]
# fetch(5) -> 6
# [1,2,3]
# [5]
# [7,8,4,6]
# fetch(4) -> 5
# [1,2,3]
# [7,8,4,6,5]
# - I don't see how to do better than O(n)

# WRONG
class MRUQueue:
    class Node:
        def __init__(self, key: int):
            self.key = key
            self.prev = None
            self.next = None

    def __init__(self, n: int):
        self.head = self.Node(0)
        self.tail = self.Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def fetch(self, n: int):
        prev = self.head
        for _ in range(n - 1):
            prev = prev.next
        node = prev.next
        prev.next = prev.next.next
        prev.next.prev = prev
        prev_tail = self.tail.prev
        prev_tail.next = node
        node.prev = prev_tail
        node.next = tail
        tail.prev = node
        return node.key

Extra¶

Problem description¶

Design a queue-like data structure that moves the most recently used element to the end of the queue.

Implement the MRUQueue class:

• MRUQueue(int n) constructs the MRUQueue with n elements: [1,2,3,...,n].
• int fetch(int k) moves the kth element (1-indexed) to the end of the queue and returns it.

Example 1:

Input:
["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]
Output:
[null, 3, 6, 2, 2]

Explanation:
MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become [1,2,4,5,6,7,8,3] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become [1,2,4,5,7,8,3,6] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become [1,4,5,7,8,3,6,2] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.

Constraints:

• 1 <= n <= 2000
• 1 <= k <= n
• At most 2000 calls will be made to fetch.

Follow up: Finding an O(n) algorithm per fetch is a bit easy. Can you find an algorithm with a better complexity for each fetch call?

Complement on solution, specifically why using square root as block size¶

• Is it the standard way to call them "blocks". Why not "buckets" for instance?
• Is square root decomposition a known decomposition or you just made the name?
• Is choosing block size equal to the integer square root arbitrary? Could have we pick another size?
• When we choose square root as size how many block there are? I don't get the \(O(\sqrt n)\) time complexity. I'm missing something about what square root represent.

"Blocks" versus "buckets"¶

Both are reasonable names, but blocks is conventional when splitting a sequence into contiguous pieces that preserve order.

Buckets more often means grouping elements by a property, such as a hash value or numeric range; elements in a bucket need not be adjacent in the original sequence.

Is square-root decomposition a real technique?¶

Yes. Square-root decomposition is a standard algorithmic technique: divide data into roughly \(\sqrt n\) blocks, each containing roughly \(\sqrt n\) elements.

It is often used when processing an entire sequence is expensive, but managing individual elements also creates too much overhead.

Why choose the square root?¶

You can choose any block size \(B\). The number of blocks is

In a typical square-root decomposition algorithm, the work consists of:

• Visiting up to \(n/B\) blocks.
• Processing up to \(B\) elements inside one block.

That gives

These costs pull in opposite directions:

• Small blocks make local work cheap, but there are many blocks.
• Large blocks mean fewer blocks, but more local work.

Choosing \(B \approx \sqrt n\) balances them:

Using the integer square root is simply a convenient rounding choice. Nearby sizes have the same asymptotic complexity.

What does the square root represent?¶

Suppose \(n = 10{,}000\):

At the balanced choice, both the block size and the number of blocks are \(\sqrt n\).

Processing one block plus visiting all blocks costs

But processing every element of every block costs