Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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?

Solution

Method 1 – List with Direct Access (O(n) per fetch)

Intuition

We can use a simple list/array to represent the queue. For each fetch, we remove the k-th element and append it to the end. This is straightforward and works well for small n (as in constraints).

Approach

  1. Store the queue as a list of integers from 1 to n.
  2. For fetch(k), remove the (k-1)-th element and append it to the end, then return it.
  3. This is O(n) per fetch, which is acceptable for n ≤ 2000.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class MRUQueue {
    vector<int> q;
public:
    MRUQueue(int n) {
        for (int i = 1; i <= n; ++i) q.push_back(i);
    }
    int fetch(int k) {
        int ans = q[k-1];
        q.erase(q.begin() + k-1);
        q.push_back(ans);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

type MRUQueue struct {
    q []int
}
func Constructor(n int) MRUQueue {
    q := make([]int, n)
    for i := 0; i < n; i++ {
        q[i] = i + 1
    }
    return MRUQueue{q}
}
func (m *MRUQueue) Fetch(k int) int {
    ans := m.q[k-1]
    m.q = append(m.q[:k-1], m.q[k:]...)
    m.q = append(m.q, ans)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class MRUQueue {
    private List<Integer> q;
    public MRUQueue(int n) {
        q = new ArrayList<>();
        for (int i = 1; i <= n; ++i) q.add(i);
    }
    public int fetch(int k) {
        int ans = q.get(k-1);
        q.remove(k-1);
        q.add(ans);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class MRUQueue(n: Int) {
    private val q = MutableList(n) { it + 1 }
    fun fetch(k: Int): Int {
        val ans = q[k-1]
        q.removeAt(k-1)
        q.add(ans)
        return ans
    }
}
1
2
3
4
5
6
7
8

class MRUQueue:
    def __init__(self, n: int):
        self.q = list(range(1, n+1))
    def fetch(self, k: int) -> int:
        ans = self.q[k-1]
        self.q.pop(k-1)
        self.q.append(ans)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct MRUQueue {
    q: Vec<i32>,
}
impl MRUQueue {
    fn new(n: i32) -> Self {
        Self { q: (1..=n).collect() }
    }
    fn fetch(&mut self, k: i32) -> i32 {
        let idx = (k-1) as usize;
        let ans = self.q[idx];
        self.q.remove(idx);
        self.q.push(ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class MRUQueue {
    private q: number[];
    constructor(n: number) {
        this.q = Array.from({length: n}, (_, i) => i + 1);
    }
    fetch(k: number): number {
        const ans = this.q[k-1];
        this.q.splice(k-1, 1);
        this.q.push(ans);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) per fetch, since removing from the middle of a list is O(n).
  • 🧺 Space complexity: O(n), for storing the queue.