How hard is LeetCode 1756. Design Most Recently Used Queue?

LeetCode 1756. Design Most Recently Used Queue is rated Medium on LeetCode.

What is the time complexity of LeetCode 1756. Design Most Recently Used Queue?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1756. Design Most Recently Used Queue?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1756. Design Most Recently Used Queue cover?

LeetCode 1756. Design Most Recently Used Queue is tagged Design, Array, Linked List, Divide and Conquer, Doubly-Linked List and Simulation on LeetCode.

Is LeetCode 1756. Design Most Recently Used Queue a premium problem?

Yes. LeetCode 1756. Design Most Recently Used Queue is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Design Most Recently Used Queue — LeetCode 1756 Python Solution

MediumLeetCode PremiumDesignArrayLinked ListDivide and ConquerDoubly-Linked ListSimulation

Problem: #1756
Pattern: Linked List
Reading time: 3 min
Source: leetcode.com

The 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].

Example

Input: ["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
Output: [null, 3, 6, 2, 2]
Explanation: MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].

Python solution

Python

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[k - 1 : k] = []
        self.q.append(ans)
        return ans


# Your MRUQueue object will be instantiated and called as such:
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1756. Design Most Recently Used Queue is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List and Doubly-Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1756. Design Most Recently Used Queue?: LeetCode 1756. Design Most Recently Used Queue is rated Medium on LeetCode.
What is the time complexity of LeetCode 1756. Design Most Recently Used Queue?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1756. Design Most Recently Used Queue?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1756. Design Most Recently Used Queue cover?: LeetCode 1756. Design Most Recently Used Queue is tagged Design, Array, Linked List, Divide and Conquer, Doubly-Linked List and Simulation on LeetCode.
Is LeetCode 1756. Design Most Recently Used Queue a premium problem?: Yes. LeetCode 1756. Design Most Recently Used Queue is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.