1756. Design Most Recently Used Queue

MediumStackDesignBinary Indexed TreeArrayHash TableOrdered Set
Leetcode Link

Problem Description

The problem is focused on designing a specialized data structure that mimics a queue but with an additional feature: most recently used (MRU) functionality. In essence, we are to create an MRUQueue class with the following behaviors:

  • Initialization with a sequence of integers: When an MRUQueue instance is created with n, it should initialize a queue-like structure filled with integers from 1 to n, in increasing order.
  • Fetching and moving an element: The fetch method retrieves the value of the element at the k-th position (1-indexed, meaning that counting starts from 1, not 0). After fetching, this element should be moved to the end of the queue.

We are to ensure that the fetch operation captures the 'most recently used' aspect by updating the order of the elements within the data structure each time an element is accessed.

Intuition

To address the need to efficiently move elements to the end of the queue and maintain the correct order, the solution leverages a Binary Indexed Tree (BIT) or Fenwick Tree.

Here's why a BIT is suitable:

  • Dynamic querying: BIT allows us to dynamically calculate prefix sums, which is helpful in this context because we need to quickly find the k-th element considering the shifts that have occurred due to previous fetches.
  • Frequency counting: By storing frequency counts (initially 1 for each element since each integer occurs once), we can keep track of whether or not an element has been moved to the end.

Given this understanding, the fetch function then:

  • Uses binary search to locate the position of the k-th element by resolving its actual index in the augmented array, considering prior movements.
  • Once found, the element’s frequency count is increased, signifying that it has moved to the end.
  • Appends the found element to the internal queue representation (which may not be in actual queue order due to index manipulations with the BIT).
  • Returns the value of the found element.

The BinaryIndexedTree class provides support for updating elements (moving to the end after a fetch) and querying efficiently.

This approach is a complex but efficient solution to the problem as it reduces the time complexity when compared to naive list manipulations for every fetch operation.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The solution uses a combination of a Binary Indexed Tree (BIT) and a dynamic array for efficient operations. Here's a step-by-step explanation of the implementation:

Binary Indexed Tree (BIT)

The BinaryIndexedTree class is an auxiliary data structure used for updating frequencies and querying prefix sums. A binary indexed tree offers O(log n) complexity for both update and query operations.

  • Initialization: A list self.c is initialized of size n+1, as the BIT requires a 1-indexed array. This list will be used to store the number of times an index (representing the queue's element) has moved to the end of the queue.
  • Update: The update function increases the frequency count (self.c[x]) for the index x and propagates this update up the tree by manipulating bits based on the principle x += x & -x.
  • Query: The query function retrieves the prefix sum at index x by summing counts while traversing ancestor nodes in the BIT using x -= x & -x.

MRUQueue Class

The MRUQueue class simulates the queue with the MRU feature using the BIT for internal tracking.

  • Initialization: Create a list (self.q) that starts from 1 to n (inclusive) and instantiate a BinaryIndexedTree object. A unique aspect is that the BIT has size n + 2010 which is an arbitrary padding to allow room for future operations, since we don't remove elements after fetching, but only append them.
  • Fetch Operation: This method implements the MRU logic.
    • A binary search is used to find the k-th element as the array has been augmented with additional elements every time a fetch operation is performed. The while loop in fetch is essentially converting 'fetch index' to 'actual index by considering shifts due to prior fetches'.
    • Once the correct index l is found, we identify the element x in the queue at this index.
    • Now, since x is the most recently used, we append it to the list (self.q.append(x)), effectively moving it to the end of the queue.
    • To track this move, we update the BIT with self.tree.update(l, 1).
    • Finally, the function returns the value x.

Intuitive Explanation

The reason for the binary search in the fetch function is because the BIT keeps track of how many times an element has been moved to the end, and thus, the positions of elements in self.q will no longer be in sequence. The binary search and BIT together allow us to find the correct k-th element in log(n) time.

This solution ensures that fetching the most recently used element and updating their position in the queue is done efficiently, improving upon a naive solution of maintaining the actual position of each element which would take linear time for each operation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's walk through a small example to illustrate how the MRUQueue class and the BinaryIndexedTree would work in practice.

Suppose we initialize an MRUQueue with n = 4, so the internal list self.q at the start looks like this:

11 2 3 4

The BIT would also be initialized and would look like this (with size n + 1 for simplicity):

10 1 1 1 1

Now, let's perform a few fetch operations:

  1. Fetch the 3rd element.

    The binary search through the BIT will figure out that the 3rd element is 3 (using the prefix sums and frequency counts). Now, we'll move 3 to the end of self.q and update the BIT.

    self.q after the operation will be 1 2 4 3.

    The BIT would be updated to:

    10 1 1 0 2

    (The zero at position 3 is due to a concept simplification here; in an actual BIT, we would be incrementing the counts in a different manner, but the essence is that the count reflects the frequency of moves to the end.)

  2. Fetch the 2nd element.

    Through the same process, the binary search determines that the 2nd element is now 2. We append 2 to the end and update the BIT.

    self.q now looks like this: 1 4 3 2.

    The BIT is updated again to reflect the move.

  3. Fetch the 1st element.

    Since the 1st element is 1, it's straightforward. We move 1 to the end like before.

    self.q becomes 4 3 2 1.

    After updating, the BIT reflects the changes, keeping a count that ensures the next binary search will correctly find the k-th element despite the rearrangements.

Every fetch operation is moving elements and updating BIT accordingly, which allows the MRU feature to be implemented efficiently. The BIT keeps track of the number of times each index has been fetched, not the actual values at each index. This is crucial as it allows the binary search to correctly adjust what it considers the "k-th" element in the list, as mere list positioning no longer provides this information accurately due to the MRUQueue's dynamic nature.

Solution Implementation

1class BinaryIndexedTree:
2    def __init__(self, size: int):
3        self.size = size
4        # Create a list of zeros with length `size + 1` for 1-based indexing
5        self.tree_array = [0] * (size + 1)
6
7    def update(self, index: int, value: int):
8        # Increment the value at `index` and all its ancestors in tree array
9        while index <= self.size:
10            self.tree_array[index] += value
11            index += index & -index  # Move to the next index to update
12
13    def query(self, index: int) -> int:
14        # Calculate the prefix sum up to `index`
15        total = 0
16        while index:
17            total += self.tree_array[index]
18            index -= index & -index  # Move to the parent index
19        return total
20
21
22class MRUQueue:
23    def __init__(self, n: int):
24        # Initialize the queue with elements `[1, 2, ..., n]`
25        self.queue = list(range(n + 1))
26        # Initialize a Binary Indexed Tree with additional space for updates
27        self.tree = BinaryIndexedTree(n + 2010)
28
29    def fetch(self, k: int) -> int:
30        # Perform a binary search to find the kth element in the queue
31        # considering the offset caused by previously moved elements
32        left, right = 1, len(self.queue) - 1
33        while left < right:
34            mid = (left + right) // 2
35            # The offset is the number of elements moved before `mid`
36            offset = self.tree.query(mid)
37            if mid - offset >= k:
38                right = mid
39            else:
40                left = mid + 1
41      
42        # Once the element is found, it's moved to the end of the queue
43        x = self.queue[left]
44        self.queue.append(x)  # Append the found element to the end
45        self.tree.update(left, 1)  # Mark the previous position as moved
46        return x
47
48
49# Example usage:
50# obj = MRUQueue(n)
51# result = obj.fetch(k)
52
1class BinaryIndexedTree {
2    private int size; // Size of the array
3    private int[] tree; // The Binary Indexed Tree (BIT)
4
5    // Constructor
6    public BinaryIndexedTree(int n) {
7        this.size = n;
8        this.tree = new int[n + 1];
9    }
10
11    // Updates the BIT with a value 'v' at index 'x'
12    public void update(int x, int v) {
13        while (x <= size) {
14            tree[x] += v; // Add 'v' to current index
15            x += x & -x; // Climb up the tree
16        }
17    }
18
19    // Queries the cumulative frequency up to index 'x'
20    public int query(int x) {
21        int sum = 0;
22        while (x > 0) {
23            sum += tree[x]; // Add value at current index to sum
24            x -= x & -x; // Climb down the tree
25        }
26        return sum;
27    }
28}
29
30class MRUQueue {
31    private int currentSize; // Current size of the MRUQueue
32    private int[] queue; // Array to hold the values of the MRUQueue
33    private BinaryIndexedTree binaryIndexedTree; // Instance of BIT to support operations
34
35    // Constructor
36    public MRUQueue(int n) {
37        this.currentSize = n;
38        this.queue = new int[n + 2010]; // Initialize with extra space for modifications
39        for (int i = 1; i <= n; ++i) {
40            queue[i] = i;
41        }
42        // Create a BIT with extra space for modifications
43        binaryIndexedTree = new BinaryIndexedTree(n + 2010);
44    }
45
46    // Fetches the k-th element and moves it to the end
47    public int fetch(int k) {
48        int left = 1, right = currentSize;
49        while (left < right) {
50            int mid = (left + right) >> 1; // Find the midpoint
51            // Modify the condition to find the k-th unaffected position
52            if (mid - binaryIndexedTree.query(mid) >= k) {
53                right = mid;
54            } else {
55                left = mid + 1;
56            }
57        }
58        // Retrieve and update the queue with the fetched element
59        int value = queue[left];
60        queue[++currentSize] = value; // Add the fetched value to the end
61        binaryIndexedTree.update(left, 1); // Mark the original position as affected
62        return value; // Return the fetched value
63    }
64}
65
66/**
67 * The usage of MRUQueue would be as follows:
68 * MRUQueue mruQueue = new MRUQueue(n);
69 * int element = mruQueue.fetch(k);
70 */
71
1#include <vector>
2#include <numeric> // for std::iota
3
4// Binary Indexed Tree (BIT) or Fenwick Tree implementation for performing range query and update operations.
5class BinaryIndexedTree {
6public:
7    // Construct a new Binary Indexed Tree with given size.
8    BinaryIndexedTree(int size)
9        : treeSize_(size)
10        , treeArray_(size + 1, 0) {}
11
12    // Update the BIT at given position x by a given delta value.
13    void update(int x, int delta) {
14        while (x <= treeSize_) {
15            treeArray_[x] += delta;
16            x += x & -x; // Move to the next position to update.
17        }
18    }
19
20    // Query the cumulative frequency up to and including position x.
21    int query(int x) {
22        int sum = 0;
23        while (x > 0) {
24            sum += treeArray_[x];
25            x -= x & -x; // Move to the parent node.
26        }
27        return sum;
28    }
29
30private:
31    int treeSize_; // Size of the tree
32    std::vector<int> treeArray_; // Internal representation of the tree as a vector.
33};
34
35// Most Recently Used (MRU) Queue implemented using a Binary Indexed Tree.
36class MRUQueue {
37public:
38    // Initialize an MRUQueue with n elements.
39    MRUQueue(int n)
40        : index_(n + 1), binaryIndexedTree_(new BinaryIndexedTree(n + 2010)) {
41        std::iota(index_.begin() + 1, index_.end(), 1); // Fill the queue with initial values from 1 to n.
42    }
43
44    // Fetch the kth element from the MRUQueue, making it the most recently used element.
45    int fetch(int k) {
46        int left = 1, right = index_.size() - 1;
47        // Binary search to find the kth (unmoved) position in the queue.
48        while (left < right) {
49            int mid = left + (right - left) / 2;
50            if (mid - binaryIndexedTree_->query(mid) >= k) {
51                right = mid;
52            } else {
53                left = mid + 1;
54            }
55        }
56        // After finding the index, obtain the value, append it to the end and update the BIT.
57        int value = index_[left];
58        index_.push_back(value);
59        binaryIndexedTree_->update(left, 1); // Indicate that the element has been moved to the end.
60        return value;
61    }
62
63    ~MRUQueue() {
64        delete binaryIndexedTree_; // Proper cleanup of the dynamically allocated BIT.
65    }
66
67private:
68    std::vector<int> index_; // Internal queue representation.
69    BinaryIndexedTree* binaryIndexedTree_; // BIT for maintaining the MRU state.
70};
71
72// Usage of MRUQueue can be done as follows:
73// MRUQueue* obj = new MRUQueue(n);
74// int param_1 = obj->fetch(k);
75// delete obj; // Remember to delete the object to avoid memory leaks.
76
1// Global variable for the number of elements in the Binary Indexed Tree
2let size: number;
3// Global array for the Binary Indexed Tree
4let BIT: number[];
5
6// Initialize the Binary Indexed Tree with a specified size
7function initBIT(n: number): void {
8    size = n;
9    BIT = new Array(n + 1).fill(0);
10}
11
12// Update the Binary Indexed Tree at position x with value v
13function updateBIT(x: number, v: number): void {
14    while (x <= size) {
15        BIT[x] += v;
16        x += x & -x; // Traverse forward to parent elements
17    }
18}
19
20// Query the Binary Indexed Tree for the cumulative frequency up to position x
21function queryBIT(x: number): number {
22    let sum = 0;
23    while (x > 0) {
24        sum += BIT[x];
25        x -= x & -x; // Traverse backward to child elements
26    }
27    return sum;
28}
29
30// Global array for the MRUQueue
31let mruQueue: number[];
32// Global variable for the position of the counter to adjust indices in the MRUQueue
33let buffer: number;
34
35// Initialize the MRUQueue with a specified size
36function initMRUQueue(n: number): void {
37    mruQueue = new Array(n + 1);
38    for (let i = 1; i <= n; ++i) {
39        mruQueue[i] = i;
40    }
41    buffer = 2010; // Buffer value to adjust indices as elements are updated
42    initBIT(n + buffer);
43}
44
45// Fetch the k-th element and make it the most recently used
46function fetchMRUQueue(k: number): number {
47    let left = 1;
48    let right = mruQueue.length - 1; // -1 to account for 0-based index not used
49    let mid: number;
50
51    // Binary search to find the k-th element
52    while (left < right) {
53        mid = (left + right) >> 1; // Same as Math.floor((left + right) / 2)
54        if (mid - queryBIT(mid) >= k) {
55            right = mid;
56        } else {
57            left = mid + 1;
58        }
59    }
60
61    // Update the queue and the Binary Indexed Tree
62    const val = mruQueue[left];
63    mruQueue.push(val);
64    updateBIT(left, 1);
65
66    return val; // Return the value of the fetched element
67}
68
Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The Binary Indexed Tree (BIT) provides efficient methods for updating an element and querying the prefix sum. Both operations (update and query) have a time complexity of O(log n).

  • The update(x, v) function is executed at most O(log n) times for each update, since every time it updates the BIT, it jumps to the next value by adding the least significant bit (LSB).

  • The query(x) function also has a time complexity of O(log n) since it sums up the value of the elements by subtracting the LSB until it reaches zero.

The MRUQueue uses the BIT to manage the fetching:

  • The fetch(k) operation has a binary search which has a time complexity of O(log n) (where n is the current length of the queue), combined with querying the BIT O(log n), yielding a total of O((log n)^2). This is because every iteration of the binary search invokes a single tree.query(mid) call, and there are O(log n) iterations overall.

  • Every fetch(k) operation also appends an element to the queue and updates the BIT, both of which have a time complexity of O(log n).

Consequently, a single fetch(k) operation has an overall time complexity of O((log n)^2 + log n), which simplifies to O((log n)^2).

Space Complexity

  • The space complexity of the BinaryIndexedTree class is O(n), due to the array self.c which has a size n + 1.

  • The MRUQueue class maintains a queue self.q and an instance of BinaryIndexedTree. The queue would have a space complexity of O(n), where n is the number of fetch operations since every fetch would add an element to the queue.

  • The BinaryIndexedTree within MRUQueue initially has a size of n + 2010 for the array self.c, so the space complexity is O(n), assuming that the 2010 constant does not majorly impact the space complexity for large n.

The MRUQueue space complexity is dominated by the size of the queue and the BIT, so the overall space complexity is O(n), considering that n refers to the number of elements in the queue plus the modifications during the fetch operations.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫