Find the middle element of a stack in O(1)

Medium

Problem

Design a stack that supports push, pop, findMiddle and deleteMiddle, each in O(1) time.

Example 1

Input:  push 1, 2, 3, 4, 5 → findMiddle()
Output: 3

Also asked as: find the middle element of a stack

Test cases

Case 1

Input:    new MiddleStack()
.push(1)
.push(2)
.push(3)
.push(4)
.push(5)
.findMiddle()
Expected: [null,null,null,null,null,3]

Case 2

Input:    new MiddleStack()
.push(1)
.push(2)
.push(3)
.findMiddle()
.pop()
.pop()
.findMiddle()
Expected: [null,null,null,2,3,2,1]

Case 3

Input:    new MiddleStack()
.findMiddle()
.pop()
Expected: [null,null]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Doubly linked list + middle pointer

Time O(1) push / pop / findMiddleSpace O(n)

Back the stack with a DLL. Keep a pointer to the middle node and a count; on push/pop, move the middle pointer at most one step.

class MiddleStack {
constructor() { this.head = null; this.mid = null; this.count = 0; }
push(x) {
const node = { val: x, prev: null, next: this.head };
if (this.head) this.head.prev = node;
this.head = node;
this.count++;
if (this.count === 1) this.mid = node;
else if (this.count % 2 === 1) this.mid = this.mid.prev;
}
pop() {
if (!this.count) return undefined;
const x = this.head.val;
this.head = this.head.next;
if (this.head) this.head.prev = null;
this.count--;
if (this.count % 2 === 0) this.mid = this.mid ? this.mid.next : null;
return x;
}
findMiddle() { return this.mid ? this.mid.val : undefined; }
}