LeetCode 1756 - Design Most Recently Used Queue

LeetCode Problem 1756

Difficulty: 🟡 Medium
Topics: Array, Linked List, Divide and Conquer, Design, Simulation, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to design a special queue called an "Most Recently Used Queue", abbreviated as MRUQueue. Initially, the queue contains the integers from 1 to n in increasing order.

The key operation is fetch(k), where k is 1-indexed. This operation does two things:

1. It finds the kth element in the current queue.
2. It removes that element from its current position and appends it to the end of the queue.

The method then returns the value of that moved element.

For example, if the queue is:

[1, 2, 3, 4, 5]

and we call:

fetch(2)

then the second element is 2. We remove it and move it to the end:

[1, 3, 4, 5, 2]

and return 2.

The constraints are relatively small:

• n <= 2000
• At most 2000 fetch operations

These constraints mean that even an O(n) solution per operation is acceptable in practice because the total work remains manageable. However, the follow-up explicitly asks for something more efficient than linear time per fetch, so we should explore a better design.

There are several important edge cases to consider:

• Fetching the last element, since moving it to the end changes nothing.
• Repeatedly fetching the same position, because the queue order continuously changes.
• Very small queues such as n = 1, where every fetch must simply return the single element.
• Correct handling of 1-indexed positions, since array-based implementations naturally use 0-indexing.

A naive implementation can easily introduce off-by-one errors when converting between 1-indexed fetch positions and 0-indexed array indices.

Approaches

Brute Force Approach

The simplest implementation is to directly simulate the queue using a dynamic array or list.

For each fetch(k) operation:

1. Access the element at index k - 1.
2. Remove it from the array.
3. Append it to the end.
4. Return the value.

This works because arrays preserve the exact queue order, so every operation directly reflects the problem definition.

However, removing an element from the middle of an array requires shifting all later elements one position to the left. In the worst case, this costs O(n) time per fetch operation.

Although this passes given the small constraints, it does not satisfy the follow-up challenge.

Optimal Approach

The key observation is that the expensive part is repeatedly shifting elements after removals.

We can improve this by using square root decomposition, also called block decomposition.

The idea is to divide the queue into several smaller blocks. Instead of storing all elements in one large list, we split them into chunks of roughly equal size.

For example:

[1,2,3] [4,5,6] [7,8]

Now, when we need the kth element:

1. We locate which block contains the position.
2. Remove the element from that block.
3. Shift only between blocks rather than across the entire array.
4. Append the fetched value to the last block.

Because each block is small, operations become much faster than scanning or shifting the entire queue.

This reduces the amortized complexity of each fetch to approximately O(sqrt(n)).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per fetch	O(n)	Direct list simulation with middle removal
Optimal	O(sqrt(n)) per fetch	O(n)	Uses block decomposition for faster movement

Algorithm Walkthrough

Optimal Square Root Decomposition Algorithm

1. During initialization, divide the numbers 1 through n into blocks of size approximately sqrt(n).

For example, if n = 8, we may create:

[1,2,3]
[4,5,6]
[7,8]

Using blocks keeps each internal operation small. 2. When fetch(k) is called, convert the position into block coordinates.

We repeatedly subtract block sizes until we find the block containing the kth element. 3. Remove the target element from its block.

Since each block is small, removing from the middle is inexpensive. 4. Rebalance the blocks.

After removing an element, later blocks may need adjustment so that the logical queue order remains correct.

We do this by repeatedly taking the first element from the next block and appending it to the current block. 5. Append the fetched value to the final block.

This simulates moving the most recently used element to the end of the queue. 6. Return the fetched value.

Why it works

The algorithm maintains the invariant that concatenating all blocks in order always produces the exact queue state.

When an element is removed from a block, shifting the first element from subsequent blocks preserves the overall ordering of elements. Appending the fetched element to the final block exactly matches the required MRU behavior.

Because each block has size approximately sqrt(n), operations inside individual blocks remain efficient.

Python Solution

from math import sqrt
from collections import deque
from typing import List

class MRUQueue:

    def __init__(self, n: int):
        self.block_size = int(sqrt(n)) + 1
        self.blocks = []

        current_block = []

        for value in range(1, n + 1):
            current_block.append(value)

            if len(current_block) == self.block_size:
                self.blocks.append(deque(current_block))
                current_block = []

        if current_block:
            self.blocks.append(deque(current_block))

    def fetch(self, k: int) -> int:
        k -= 1

        block_index = 0

        while k >= len(self.blocks[block_index]):
            k -= len(self.blocks[block_index])
            block_index += 1

        value = self.blocks[block_index][k]
        del self.blocks[block_index][k]

        for i in range(block_index, len(self.blocks) - 1):
            shifted = self.blocks[i + 1].popleft()
            self.blocks[i].append(shifted)

        self.blocks[-1].append(value)

        return value

The implementation begins by computing an appropriate block size using the square root of n. This balances the number of blocks against the size of each block.

The constructor builds the queue incrementally and stores elements inside deques. Each deque represents one block.

Inside fetch, we first convert the 1-indexed position into a 0-indexed position. Then we determine which block contains the requested element by subtracting block sizes until the target position fits within a block.

After locating the correct block, we remove the target element. Since the block size is small, this operation is efficient.

Next, we rebalance the structure. Each block pulls the first element from the next block to preserve the correct overall ordering.

Finally, we append the fetched value to the final block and return it.

Go Solution

package main

import "math"

type MRUQueue struct {
	blocks [][]int
	size   int
}

func Constructor(n int) MRUQueue {
	blockSize := int(math.Sqrt(float64(n))) + 1

	blocks := [][]int{}
	current := []int{}

	for value := 1; value <= n; value++ {
		current = append(current, value)

		if len(current) == blockSize {
			blocks = append(blocks, current)
			current = []int{}
		}
	}

	if len(current) > 0 {
		blocks = append(blocks, current)
	}

	return MRUQueue{
		blocks: blocks,
		size:   blockSize,
	}
}

func (this *MRUQueue) Fetch(k int) int {
	k--

	blockIndex := 0

	for k >= len(this.blocks[blockIndex]) {
		k -= len(this.blocks[blockIndex])
		blockIndex++
	}

	value := this.blocks[blockIndex][k]

	this.blocks[blockIndex] = append(
		this.blocks[blockIndex][:k],
		this.blocks[blockIndex][k+1:]...,
	)

	for i := blockIndex; i < len(this.blocks)-1; i++ {
		shifted := this.blocks[i+1][0]

		this.blocks[i] = append(this.blocks[i], shifted)

		this.blocks[i+1] = this.blocks[i+1][1:]
	}

	this.blocks[len(this.blocks)-1] =
		append(this.blocks[len(this.blocks)-1], value)

	return value
}

The Go version follows the same overall strategy as the Python implementation. The primary difference is that Go slices require manual element removal using slice concatenation.

Unlike Python's deque, Go does not provide a built-in double-ended queue, so we simulate block behavior using slices.

Integer overflow is not a concern because all values remain within very small bounds.

Worked Examples

Example 1

Initial queue:

[1,2,3,4,5,6,7,8]

Suppose blocks are:

[1,2,3]
[4,5,6]
[7,8]

Operation 1: fetch(3)

The 3rd element is 3.

Remove 3:

[1,2]
[4,5,6]
[7,8]

Rebalance:

• Move 4 forward

[1,2,4]
[5,6]
[7,8]

• Move 7 forward

[1,2,4]
[5,6,7]
[8]

Append 3:

[1,2,4]
[5,6,7]
[8,3]

Final queue:

[1,2,4,5,6,7,8,3]

Return:

3

Operation 2: fetch(5)

Current queue:

[1,2,4,5,6,7,8,3]

The 5th element is 6.

After removal and rebalancing:

[1,2,4]
[5,7,8]
[3,6]

Final queue:

[1,2,4,5,7,8,3,6]

Return:

6

Operation 3: fetch(2)

Current queue:

[1,2,4,5,7,8,3,6]

The 2nd element is 2.

After movement:

[1,4,5]
[7,8,3]
[6,2]

Final queue:

[1,4,5,7,8,3,6,2]

Return:

2

Operation 4: fetch(8)

Current queue:

[1,4,5,7,8,3,6,2]

The 8th element is already 2 at the end.

The queue remains unchanged.

Return:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(n)) per fetch	Each operation touches at most one block plus block rebalancing
Space	O(n)	All queue elements are stored exactly once

The queue is partitioned into approximately sqrt(n) blocks, each containing roughly sqrt(n) elements.

Finding the correct block requires traversing at most sqrt(n) blocks. Removing from a block costs at most O(sqrt(n)), and rebalancing also affects at most sqrt(n) blocks.

Therefore, each fetch operation runs in approximately O(sqrt(n)) time.

Test Cases

# Provided example
queue = MRUQueue(8)
assert queue.fetch(3) == 3      # move middle element
assert queue.fetch(5) == 6      # fetch after reorder
assert queue.fetch(2) == 2      # another reorder
assert queue.fetch(8) == 2      # last element already at end

# Single element queue
queue = MRUQueue(1)
assert queue.fetch(1) == 1      # only element

# Small queue repeated fetches
queue = MRUQueue(3)
assert queue.fetch(1) == 1      # [2,3,1]
assert queue.fetch(1) == 2      # [3,1,2]
assert queue.fetch(1) == 3      # [1,2,3]

# Fetch last element repeatedly
queue = MRUQueue(5)
assert queue.fetch(5) == 5      # already at end
assert queue.fetch(5) == 5      # remains at end

# Fetch first element repeatedly
queue = MRUQueue(4)
assert queue.fetch(1) == 1      # [2,3,4,1]
assert queue.fetch(1) == 2      # [3,4,1,2]
assert queue.fetch(1) == 3      # [4,1,2,3]

# Boundary size test
queue = MRUQueue(2000)
assert queue.fetch(2000) == 2000  # maximum valid position
assert queue.fetch(1) == 1        # fetch front element

Test Summary

Test	Why
Example sequence	Validates correctness against official example
Single element queue	Tests minimum boundary
Repeated front fetches	Verifies queue reordering
Repeated last fetches	Ensures no corruption when element already at end
Small cyclic movement	Confirms order maintenance
Maximum size queue	Tests upper constraint handling

Edge Cases

Fetching the Last Element

When k equals the current queue length, the selected element is already at the end of the queue. A buggy implementation might accidentally duplicate the element or corrupt ordering during removal and reinsertion.

This implementation safely removes the element and appends it back to the final block, producing the same logical queue state.

Queue Size of One

A queue containing only one element is a special case because every fetch operation must return the same value and preserve the queue unchanged.

The implementation handles this naturally because the single block contains one element, and removal followed by append restores the original state.

Repeated Reordering

Successive fetch operations continuously mutate queue order. A naive implementation may incorrectly compute positions using stale assumptions about original indices.

This solution always computes positions from the current block structure, ensuring correctness after arbitrary reorderings.