LeetCode 1670: Design Front Middle Back Queue Solution

Master LeetCode problem 1670 (Design Front Middle Back Queue), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1670. Design Front Middle Back Queue

Medium

Array Linked List Design Queue Data Stream

Problem Explanation

Explanation

To implement the FrontMiddleBack class, we can use two deques to maintain the front and back halves of the queue. We need to handle the case where the size difference between the two halves is at most 1. When pushing elements, we first check if the size of the front deque is equal to or one more than the size of the back deque. If so, we rebalance the queues. When popping elements, we maintain the balance of the two deques as well.

Algorithm

Initialize two deques frontDeque and backDeque.
Implement pushFront, pushMiddle, and pushBack functions to add elements to the appropriate deque.
Implement popFront, popMiddle, and popBack functions to remove elements from the appropriate deque.
When pushing elements, check the size difference between frontDeque and backDeque and rebalance if necessary.
When popping elements, maintain the balance of the two deques.

Time Complexity

Push operations: O(1)
Pop operations: O(1)
Overall: O(1)

Space Complexity

O(n), where n is the number of elements in the queue.

Solution Code

import java.util.ArrayDeque;
import java.util.Deque;

class FrontMiddleBackQueue {
    Deque<Integer> frontDeque;
    Deque<Integer> backDeque;

    public FrontMiddleBackQueue() {
        frontDeque = new ArrayDeque<>();
        backDeque = new ArrayDeque<>();
    }

    public void pushFront(int val) {
        frontDeque.offerFirst(val);
        balance();
    }

    public void pushMiddle(int val) {
        if (frontDeque.size() > backDeque.size()) {
            backDeque.offerFirst(frontDeque.pollLast());
        }
        frontDeque.offerLast(val);
    }

    public void pushBack(int val) {
        backDeque.offerLast(val);
        balance();
    }

    public int popFront() {
        if (frontDeque.isEmpty() && backDeque.isEmpty()) return -1;

        int val = frontDeque.isEmpty() ? backDeque.pollFirst() : frontDeque.pollFirst();
        balance();
        return val;
    }

    public int popMiddle() {
        if (frontDeque.isEmpty()) return -1;

        int val = frontDeque.size() == backDeque.size() ? backDeque.pollFirst() : frontDeque.pollLast();
        balance();
        return val;
    }

    public int popBack() {
        if (frontDeque.isEmpty() && backDeque.isEmpty()) return -1;

        int val = backDeque.isEmpty() ? frontDeque.pollLast() : backDeque.pollLast();
        balance();
        return val;
    }

    private void balance() {
        if (frontDeque.size() > backDeque.size() + 1) {
            backDeque.offerFirst(frontDeque.pollLast());
        } else if (backDeque.size() > frontDeque.size()) {
            frontDeque.offerLast(backDeque.pollFirst());
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1670 (Design Front Middle Back Queue)?

This page provides optimized solutions for LeetCode problem 1670 (Design Front Middle Back Queue) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1670 (Design Front Middle Back Queue)?

The time complexity for LeetCode 1670 (Design Front Middle Back Queue) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1670 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1670 in Java, C++, or Python.

Back to LeetCode Solutions