Find the middle element of a stack in O(1)
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]
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; }}