DSAPROB11 - Editorial

editorial
, ,
1

Problem link - Queue Operation

Problem statement

Design a queue data structure that supports the following operations in O(1) time:

  • Enqueue an element.

  • Dequeue an element.

  • Get the minimum element.

You need to implement the following functions:

  • Void enqueue(int x): Adds an element x to the end of the queue.

  • int dequeue(): Removes the element from the front of the queue.

  • int getMin(): Returns the minimum element in the queue.

Approach:

To efficiently implement these operations, especially the getMin operation, you can use two data structures:

  • Queue (q) : Holds all the elements of the MinQueue.

  • Deque (minDeque) : Helps keep track of the minimum values.

Key Idea:

Use the minDeque to maintain potential minimum values in such a way that the minimum value of the queue is always available at the front of the minDeque. By ensuring that minDeque always has the minimum value at its front, you can efficiently retrieve the minimum value with constant time complexity.

Detailed Explanation:

  1. Enqueue Operation (enqueue(x)):

    • Add to Queue: Insert x into the main queue (q).

    • Maintain MinDeque:

      • Remove elements from the back of minDeque as long as they are greater than x. This ensures that only potential minimum values remain in minDeque.

      • Add x to the back of minDeque. This keeps minDeque updated with the current minimum values.

  2. Dequeue Operation (dequeue()):

    • Remove from Queue: Remove the element from the front of the main queue (q).

    • Update MinDeque:

      • If the removed element matches the front of minDeque, also remove it from minDeque. This keeps minDeque synchronized with the main queue, ensuring it still reflects the minimum of the remaining elements.

  3. GetMin Operation (getMin()):

    • Retrieve Minimum: Return the element at the front of minDeque. If minDeque is empty, it indicates that the queue is empty, so handle this case appropriately.

Time Complexity:

  • enqueue(x): O(n), Since up to n elements may be removed from minDeque, the amortized time complexity remains O(1) as each element is added and removed at most once.

  • dequeue() : O(1), as removing from q and potentially from minDeque both take constant time.

  • getMin() : O(1), as it only involves accessing the front of minDeque.

Space Complexity:

  • O(n): Space used by both q and minDeque is proportional to the number of elements.