Editorial for Teque

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Maintain the teque as two deques:

left stores the first half,
right stores the second half.

Keep this invariant after each operation:

$|left| = |right|$ ~|left| = |right|~ or $|left| = |right| + 1$ ~|left| = |right| + 1~.

So the conceptual sequence is left followed by right.

Using this invariant:

push_front x: left.appendleft(x).
push_back x: right.append(x).
push_middle x: if left has one extra element, place x at the front of right; otherwise place it at the back of left.
pop_front: remove from front of left.
pop_back: remove from back of right when possible, otherwise from back of left.
pop_middle: remove from back of left (this is index $\left\lfloor\frac{n-1}{2}\right\rfloor$ ).

After each operation, rebalance by moving one value across halves if needed.

Each operation is $O(1)$ ~O(1)~ amortized.

Solution (Python)

import sys
from collections import deque


def rebalance(left: deque[int], right: deque[int]) -> None:
    if len(left) > len(right) + 1:
        right.appendleft(left.pop())
    elif len(left) < len(right):
        left.append(right.popleft())


def main() -> None:
    input_data = sys.stdin.buffer.readline
    q = int(input_data())

    left: deque[int] = deque()
    right: deque[int] = deque()
    out: list[str] = []

    for _ in range(q):
        parts = input_data().split()
        op = parts[0]

        if op == b"push_front":
            left.appendleft(int(parts[1]))
            rebalance(left, right)
        elif op == b"push_back":
            right.append(int(parts[1]))
            rebalance(left, right)
        elif op == b"push_middle":
            value = int(parts[1])
            if len(left) > len(right):
                right.appendleft(value)
            else:
                left.append(value)
        elif op == b"pop_front":
            out.append(str(left.popleft()))
            rebalance(left, right)
        elif op == b"pop_back":
            if right:
                out.append(str(right.pop()))
            else:
                out.append(str(left.pop()))
            rebalance(left, right)
        else:  # pop_middle
            out.append(str(left.pop()))
            rebalance(left, right)

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.