LeetCode Solutions Blog

Design Most Recently Used Queue

Number: 1903

Difficulty: Medium

Paid? Yes

Problem Description

Design a queue-like data structure that supports a fetch operation where the kth element (1-indexed) is removed from its current position, returned, and appended to the end of the queue.

Key Insights

The main task is to support efficient kth-element extraction and then update the data structure to simulate moving that element to the back of the queue.
A naive approach using an array would take O(n) per fetch operation when removing the kth element.
Advanced data structures such as a Binary Indexed Tree (BIT), Balanced BST, or Ordered Set can be used to achieve an improvement (e.g., O(log n) per fetch).
The BIT (Fenwick Tree) can maintain frequencies corresponding to positions, allowing the kth element to be located using prefix sum queries in logarithmic time.

Space and Time Complexity

Time Complexity: O(log n) per fetch call using BIT. Space Complexity: O(n) where n is the total number of elements (including newly appended ones).

Solution

We use a Binary Indexed Tree (BIT) to keep track of the positions of elements. Every element starting in the initial array has a frequency of 1. When fetching the kth element, we use BIT to locate the actual index corresponding to the kth element by performing a prefix sum query. After identifying the element, we update the BIT to remove it from its current location (by setting its frequency to 0) and then append the element at a new index at the back (updating BIT accordingly). This method efficiently simulates both the kth-element extraction and the subsequent reordering.

Code Solutions

# Python solution using a Binary Indexed Tree (Fenwick Tree)

class MRUQueue:
    def __init__(self, n: int):
        self.n = n
        # Increase capacity to allow appending elements.
        self.capacity = n + 2000  
        self.fenw = [0] * (self.capacity + 1)  # 1-indexed BIT array
        self.values = [0] * (self.capacity + 1)  # Stores actual element values
        # Initialize first n positions
        for i in range(1, n + 1):
            self.fenw[i] = 1
            self.values[i] = i
        # Build the BIT for the initial frequencies
        for i in range(1, self.capacity + 1):
            j = i + (i & -i)
            if j <= self.capacity:
                self.fenw[j] += self.fenw[i]
        # Pointer for the next index to append at the end
        self.nextIndex = n + 1

    # Update BIT at position idx with delta
    def update(self, idx: int, delta: int) -> None:
        while idx <= self.capacity:
            self.fenw[idx] += delta
            idx += idx & -idx

    # Query prefix sum from 1 to idx
    def query(self, idx: int) -> int:
        s = 0
        while idx > 0:
            s += self.fenw[idx]
            idx -= idx & -idx
        return s

    # Find the position with cumulative frequency equal to or greater than k
    def findKth(self, k: int) -> int:
        idx = 0
        # Start with the highest bit within capacity range
        bit_mask = 1 << (self.capacity.bit_length() - 1)
        while bit_mask:
            t_idx = idx + bit_mask
            if t_idx <= self.capacity and self.fenw[t_idx] < k:
                k -= self.fenw[t_idx]
                idx = t_idx
            bit_mask //= 2
        return idx + 1

    def fetch(self, k: int) -> int:
        # Find the index of the kth element using BIT
        idx = self.findKth(k)
        result = self.values[idx]
        # Remove the element from its current position in BIT
        self.update(idx, -1)
        # Append the element at the end of the queue
        self.values[self.nextIndex] = result
        self.update(self.nextIndex, 1)
        self.nextIndex += 1
        return result

# Example usage:
# mRUQueue = MRUQueue(8)
# print(mRUQueue.fetch(3))  # Expect 3
# print(mRUQueue.fetch(5))  # Expect 6
# print(mRUQueue.fetch(2))  # Expect 2
# print(mRUQueue.fetch(8))  # Expect 2