๐๏ธ Stacks, Queues & Heaps
๐ 31. How do you implement a stack with a max-stack (O(1) max query)?
A Max Stack supports:
โข Push
โข Pop
โข Get Maximum Element in O(1)
๐น Idea
Maintain:
1. Main stack
2. Max stack
Max stack stores current maximums.
๐น Python Solution
class MaxStack:
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, value):
self.stack.append(value)
if not self.max_stack or value >= self.max_stack[-1]:
self.max_stack.append(value)
def pop(self):
if self.stack[-1] == self.max_stack[-1]:
self.max_stack.pop()
return self.stack.pop()
def get_max(self):
return self.max_stack[-1]
๐น Complexity
Operation - Complexity
Push - O(1)
Pop - O(1)
Get Max - O(1)
๐น Interview Tip
Very common design-based stack question.
๐ 32. How do you implement a queue using two stacks?
Queues are FIFO. Stacks are LIFO.
We can combine two stacks.
๐น Idea
Stack1 โ enqueue
Stack2 โ dequeue
๐น Python Solution
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
def enqueue(self, value):
self.s1.append(value)
def dequeue(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
๐น Complexity
Operation - Complexity
Enqueue - O(1)
Dequeue - Amortized O(1)
๐น Interview Tip
Interviewers love this because it tests understanding of stack behavior.
๐ 33. How do you design a stack that supports getMin() in O(1)?
Very similar to Max Stack.
๐น Idea
Maintain:
โข Main stack
โข Min stack
๐น Python Solution
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, value):
self.stack.append(value)
if not self.min_stack or value <= self.min_stack[-1]:
self.min_stack.append(value)
def pop(self):
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
return self.stack.pop()
def get_min(self):
return self.min_stack[-1]
๐น Complexity
Operation - Complexity
Push - O(1)
Pop - O(1)
Get Min - O(1)
๐น Interview Tip
This is one of the highest-frequency interview problems.
๐ 34. What is a monotonic stack and when is it useful?
A monotonic stack maintains elements in:
โข Increasing order OR
โข Decreasing order
๐น Uses
โ Next Greater Element
โ Largest Rectangle in Histogram
โ Stock Span Problem
โ Daily Temperatures
๐น Example
arr = [2, 1, 3]
stack = []
for num in arr:
while stack and stack[-1] > num:
stack.pop()
stack.append(num)
๐น Complexity
Most monotonic stack problems:
O(n)
because every element is pushed and popped once.
๐น Interview Tip
Extremely important pattern for medium/hard problems.
๐ 35. How do you implement a priority queue / heap?
A heap is a complete binary tree.
Types:
โข Min Heap
โข Max Heap
๐น Python Min Heap
import heapq
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
print(heapq.heappop(heap))
๐น Output
5
๐น Complexity
Operation - Complexity
Insert - O(log n)
Delete - O(log n)
Peek - O(1)
๐น Uses
โ Task scheduling
โ Dijkstraโs algorithm
โ Top K problems
โ Priority processing
๐ 36. How do you find the top K frequent elements?
๐น Approach
1. Count frequency using hashmap
2. Use heap
๐น Python Solution
from collections import Counter
import heapq
def top_k(nums, k):
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=freq.get)
print(top_k([1, 1, 1, 2, 2, 3], 2))
๐น Output
[1, 2]
๐น Complexity
Complexity - Value
Time - O(n log k)
Space - O(n)
๐น Interview Tip
Heap + hashmap combination is frequently tested.