Design Front Middle Back Queue

Medium
2069.

Design Front Middle Back Queue

MediumArrayLinked ListDesignQueue

Design Front Middle Back Queue is a medium coding problem on arrays and queue.

Design a queue that can add and remove elements at the front, the back and the middle.

Write the class FrontMiddleBackQueue:

  • FrontMiddleBackQueue() creates an empty queue.
  • void pushFront(int value), void pushMiddle(int value) and void pushBack(int value) insert value at the front, the middle and the back.
  • int popFront(), int popMiddle() and int popBack() remove the element at the front, the middle and the back and return it, or return -1 if the queue is empty.

When there are two middle positions, the operation uses the one nearer the front. For example, pushMiddle(6) on [1,2,3,4,5] gives [1,2,6,3,4,5], and popMiddle() on [1,2,6,3,4,5] removes and returns 6.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["FrontMiddleBackQueue","pushFront","pushBack","pushMiddle","pushMiddle","popFront","popMiddle","popMiddle","popBack","popFront"] [[],[1],[2],[3],[4],[],[],[],[],[]]
Output
[null,null,null,null,null,1,3,4,2,-1]
Explanation
The queue becomes [1], [1,2], [1,3,2], then [1,4,3,2]. popFront takes 1 leaving [4,3,2]; popMiddle takes the middle 3; on [4,2] the front middle is 4; popBack takes 2, and the empty queue gives -1.

Example 2

Input
["FrontMiddleBackQueue","pushBack","pushBack","pushBack","pushBack","pushBack","pushMiddle","popMiddle","popMiddle"] [[],[10],[20],[30],[40],[50],[60],[],[]]
Output
[null,null,null,null,null,null,null,60,30]
Explanation
[10,20,30,40,50] has one middle position for an insertion, before 30: [10,20,60,30,40,50]. popMiddle on six elements takes the front middle, 60, and on five elements the true middle, 30.

Constraints

  • 1 <= value <= 10^9
  • At most 1000 calls are made to the six methods in total
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var FrontMiddleBackQueue = function() {
    
};

/**
 * @param {number} value
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushFront = function(value) {
    
};

/**
 * @param {number} value
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushMiddle = function(value) {
    
};

/**
 * @param {number} value
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushBack = function(value) {
    
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popFront = function() {
    
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popMiddle = function() {
    
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popBack = function() {
    
};

Sign in to run your own test cases

Sign in

Design Front Middle Back Queue — Problem & Solution

Design Front Middle Back Queue solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Design Front Middle Back Queue is a medium coding problem on arrays and queue.

  • Difficulty: Medium
  • Topics: Arrays, Queue
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Design a queue that can add and remove elements at the front, the back and the middle.

Write the class FrontMiddleBackQueue:

  • FrontMiddleBackQueue() creates an empty queue.
  • void pushFront(int value), void pushMiddle(int value) and void pushBack(int value) insert value at the front, the middle and the back.
  • int popFront(), int popMiddle() and int popBack() remove the element at the front, the middle and the back and return it, or return -1 if the queue is empty.

When there are two middle positions, the operation uses the one nearer the front. For example, pushMiddle(6) on [1,2,3,4,5] gives [1,2,6,3,4,5], and popMiddle() on [1,2,6,3,4,5] removes and returns 6.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["FrontMiddleBackQueue","pushFront","pushBack","pushMiddle","pushMiddle","popFront","popMiddle","popMiddle","popBack","popFront"]
[[],[1],[2],[3],[4],[],[],[],[],[]]
Output: [null,null,null,null,null,1,3,4,2,-1]
Explanation: The queue becomes [1], [1,2], [1,3,2], then [1,4,3,2]. popFront takes 1 leaving [4,3,2]; popMiddle takes the middle 3; on [4,2] the front middle is 4; popBack takes 2, and the empty queue gives -1.

Example 2

Input: ["FrontMiddleBackQueue","pushBack","pushBack","pushBack","pushBack","pushBack","pushMiddle","popMiddle","popMiddle"]
[[],[10],[20],[30],[40],[50],[60],[],[]]
Output: [null,null,null,null,null,null,null,60,30]
Explanation: [10,20,30,40,50] has one middle position for an insertion, before 30: [10,20,60,30,40,50]. popMiddle on six elements takes the front middle, 60, and on five elements the true middle, 30.

Constraints

  • 1 <= value <= 10^9
  • At most 1000 calls are made to the six methods in total

Hints for Design Front Middle Back Queue

  1. Hint 1

    With one array the middle operations shift half the elements every time. Can you keep the middle at an end of something?

  2. Hint 2

    Split the queue into a front half and a back half, each a deque, and keep the back half equal in size to the front half or one larger.

  3. Hint 3

    Then the front middle for popping is the last of the front half when the halves are equal, and the first of the back half otherwise; inserting in the middle goes to the front of the back half when equal, the back of the front half otherwise. After any front/back operation, move one element across to restore the balance.

How to solve Design Front Middle Back Queue

Keep two deques, left and right, whose concatenation is the queue, with len(left) <= len(right) <= len(left) + 1. The middle is then always at the seam, so every operation touches only deque ends.

Approach

  1. rebalance(): if left is longer than right, move the last of left to the front of right; if right is two longer than left, move the first of right to the back of left.
  2. pushFront: add to the front of left, rebalance. pushBack: add to the back of right, rebalance.
  3. pushMiddle: if the halves are equal, add to the front of right; otherwise add to the back of left.
  4. Pops on an empty queue (right empty) return -1. popFront: take the front of left, or of right if left is empty, then rebalance. popBack: take the back of right, rebalance.
  5. popMiddle: if the halves are equal take the back of left, otherwise the front of right.

Why it works

For a queue of size n, insertion in the middle means position floor(n/2) and removal means index floor((n-1)/2). With the invariant, left holds exactly the first floor(n/2) elements, so position floor(n/2) is the seam: the front of right when n is even, the back of left when odd keeps the sizes legal. Index floor((n-1)/2) is the last of left when n is even and the first of right when it is odd. Each operation changes the sizes by one, and one move across restores the invariant.

Complexity

  • Time — O(1) per call
  • Space — O(n)

Pitfalls

  • Off by one in the middle rules: insertion goes to index n/2, removal takes index (n-1)/2, both rounded down.
  • With one element it sits in right; popFront must look there when left is empty.
  • A plain list with insert/remove at the middle also passes 1000 calls, at O(n) each.

Reference solution

Python

from collections import deque

class FrontMiddleBackQueue:

    def __init__(self):
        self.left = deque()   # invariant: len(left) <= len(right) <= len(left) + 1
        self.right = deque()

    def _balance(self):
        if len(self.left) > len(self.right):
            self.right.appendleft(self.left.pop())
        elif len(self.right) > len(self.left) + 1:
            self.left.append(self.right.popleft())

    def pushFront(self, value: int) -> None:
        self.left.appendleft(value)
        self._balance()

    def pushMiddle(self, value: int) -> None:
        if len(self.left) == len(self.right):
            self.right.appendleft(value)
        else:
            self.left.append(value)

    def pushBack(self, value: int) -> None:
        self.right.append(value)
        self._balance()

    def popFront(self) -> int:
        if not self.right:
            return -1
        x = self.left.popleft() if self.left else self.right.popleft()
        self._balance()
        return x

    def popMiddle(self) -> int:
        if not self.right:
            return -1
        if len(self.left) == len(self.right):
            return self.left.pop()
        return self.right.popleft()

    def popBack(self) -> int:
        if not self.right:
            return -1
        x = self.right.pop()
        self._balance()
        return x

Java

class FrontMiddleBackQueue {
    // invariant: left.size() <= right.size() <= left.size() + 1
    private Deque<Integer> left = new ArrayDeque<>(), right = new ArrayDeque<>();

    public FrontMiddleBackQueue() {
    }

    private void balance() {
        if (left.size() > right.size()) right.addFirst(left.pollLast());
        else if (right.size() > left.size() + 1) left.addLast(right.pollFirst());
    }

    public void pushFront(int value) {
        left.addFirst(value);
        balance();
    }

    public void pushMiddle(int value) {
        if (left.size() == right.size()) right.addFirst(value); else left.addLast(value);
    }

    public void pushBack(int value) {
        right.addLast(value);
        balance();
    }

    public int popFront() {
        if (right.isEmpty()) return -1;
        int x = left.isEmpty() ? right.pollFirst() : left.pollFirst();
        balance();
        return x;
    }

    public int popMiddle() {
        if (right.isEmpty()) return -1;
        return left.size() == right.size() ? left.pollLast() : right.pollFirst();
    }

    public int popBack() {
        if (right.isEmpty()) return -1;
        int x = right.pollLast();
        balance();
        return x;
    }
}

C++

class FrontMiddleBackQueue {
    deque<int> left, right; // invariant: left.size() <= right.size() <= left.size() + 1

    void balance() {
        if (left.size() > right.size()) { right.push_front(left.back()); left.pop_back(); }
        else if (right.size() > left.size() + 1) { left.push_back(right.front()); right.pop_front(); }
    }
public:
    FrontMiddleBackQueue() {}

    void pushFront(int value) {
        left.push_front(value);
        balance();
    }

    void pushMiddle(int value) {
        if (left.size() == right.size()) right.push_front(value); else left.push_back(value);
    }

    void pushBack(int value) {
        right.push_back(value);
        balance();
    }

    int popFront() {
        if (right.empty()) return -1;
        int x;
        if (left.empty()) { x = right.front(); right.pop_front(); }
        else { x = left.front(); left.pop_front(); }
        balance();
        return x;
    }

    int popMiddle() {
        if (right.empty()) return -1;
        int x;
        if (left.size() == right.size()) { x = left.back(); left.pop_back(); }
        else { x = right.front(); right.pop_front(); }
        return x;
    }

    int popBack() {
        if (right.empty()) return -1;
        int x = right.back();
        right.pop_back();
        balance();
        return x;
    }
};

JavaScript

var FrontMiddleBackQueue = function() {
    this.left = [];  // invariant: left.length <= right.length <= left.length + 1
    this.right = [];
};

FrontMiddleBackQueue.prototype.balance = function() {
    if (this.left.length > this.right.length) this.right.unshift(this.left.pop());
    else if (this.right.length > this.left.length + 1) this.left.push(this.right.shift());
};

FrontMiddleBackQueue.prototype.pushFront = function(value) {
    this.left.unshift(value);
    this.balance();
};

FrontMiddleBackQueue.prototype.pushMiddle = function(value) {
    if (this.left.length === this.right.length) this.right.unshift(value);
    else this.left.push(value);
};

FrontMiddleBackQueue.prototype.pushBack = function(value) {
    this.right.push(value);
    this.balance();
};

FrontMiddleBackQueue.prototype.popFront = function() {
    if (this.right.length === 0) return -1;
    var x = this.left.length ? this.left.shift() : this.right.shift();
    this.balance();
    return x;
};

FrontMiddleBackQueue.prototype.popMiddle = function() {
    if (this.right.length === 0) return -1;
    return this.left.length === this.right.length ? this.left.pop() : this.right.shift();
};

FrontMiddleBackQueue.prototype.popBack = function() {
    if (this.right.length === 0) return -1;
    var x = this.right.pop();
    this.balance();
    return x;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Queues and Deques