Heap, Stack and Queue Problems — Complete Interview Guide
In this tutorial, you'll learn about Heap, Stack and Queue Problems. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Heap, stack, and queue problems test your understanding of fundamental data structures beyond arrays and linked lists. Each structure excels at specific access patterns: stacks for LIFO, queues for FIFO, and heaps for priority-based retrieval.
Learning Path
flowchart LR A["Recursion & Backtracking"] --> B["Heap, Stack & Queue
You are here"] B --> C["System Design Prep"] C --> D["FAANG Interview Guide"] style B fill:#f90,color:#fff,stroke-width:2px
Top K Frequent Elements (Heap)
A min-heap of size k efficiently tracks the k largest or most frequent elements.
import heapq
def top_k_frequent(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for count, num in heap]
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
print(top_k_frequent([4, 4, 4, 4, 5, 5, 5, 6, 6, 7], 3))
[2, 1]
[6, 5, 4]
import java.util.*;
public class TopKFrequent {
public static List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
(a, b) -> a.getValue() - b.getValue()
);
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
heap.offer(entry);
if (heap.size() > k) heap.poll();
}
List<Integer> result = new ArrayList<>();
while (!heap.isEmpty()) result.add(heap.poll().getKey());
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
System.out.println(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2));
}
}
[2, 1]
#include <vector>
#include <unordered_map>
#include <queue>
#include <iostream>
using namespace std;
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
for (auto& [num, count] : freq) {
heap.push({count, num});
if (heap.size() > k) heap.pop();
}
vector<int> result;
while (!heap.empty()) {
result.push_back(heap.top().second);
heap.pop();
}
return result;
}
int main() {
vector<int> nums = {1, 1, 1, 2, 2, 3};
auto res = topKFrequent(nums, 2);
for (int v : res) cout << v << " ";
return 0;
}
2 1
Valid Parentheses (Stack)
Stack is ideal for matching problems: parentheses, brackets, and tags.
def is_valid(s):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
print(is_valid("()[]{}"))
print(is_valid("([)]"))
print(is_valid("{[]}"))
True
False
True
import java.util.*;
public class ValidParentheses {
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char ch : s.toCharArray()) {
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.pop() != pairs.get(ch)) return false;
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("()[]{}"));
System.out.println(isValid("([)]"));
}
}
True
False
#include <stack>
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
for (char ch : s) {
if (pairs.count(ch)) {
if (st.empty() || st.top() != pairs[ch]) return false;
st.pop();
} else {
st.push(ch);
}
}
return st.empty();
}
int main() {
cout << isValid("()[]{}") << endl;
cout << isValid("([)]") << endl;
return 0;
}
1
0
Monotonic Stack
A monotonic stack maintains elements in increasing or decreasing order, enabling O(n) solutions for next greater element problems.
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = []
for i, temp in enumerate(temperatures):
while stack and temp > temperatures[stack[-1]]:
idx = stack.pop()
result[idx] = i - idx
stack.append(i)
return result
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
[1, 1, 4, 2, 1, 1, 0, 0]
LRU Cache (Hash Map + Doubly Linked List)
Design a Least Recently Used cache that supports get and put in O(1) time.
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.value
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._add_to_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
1
-1
Common Mistakes
- Heap direction confusion -- Use a min-heap for k largest elements (keep k largest by popping smallest) and a max-heap for k smallest. Python's heapq is a min-heap.
- Stack underflow -- Always check
if stackor!stack.isEmpty()before peeking or popping. Empty stack operations throw exceptions. - Queue vs deque confusion -- Standard queues are FIFO. Deques support both ends. Choose the right structure: BFS uses queue, monotonic problems may use deque.
- Heap with custom objects -- Without a custom comparator, heaps sort by the first tuple element. Use
(priority, item)tuples or provide a comparator function. - Forgetting hash map for O(1) lookup -- LRU cache requires both a doubly Linked List (for order) and a hash map (for O(1) key lookup). One without the other is incomplete.
- Monotonic stack equality handling -- Decide whether equal elements should be popped. For strictly increasing, pop on
<; for non-decreasing, pop on<=. - BFS without visited set -- A standard BFS queue without tracking visited nodes can revisit nodes infinitely in cyclic graphs. Always initialize a visited set.
Practice Questions
1. Design a Min Stack that supports push, pop, top, and getMin in O(1) time.
Maintain two stacks: one for values and one for the current minimum. On push, compare the new value with the current minimum and push the smaller.
2. Find the median of a stream of numbers.
Use two heaps: a max-heap for the left half and a min-heap for the right half. Rebalance after each insertion to keep sizes within 1.
3. Challenge: Sliding Window Maximum (Leetcode 239)
Given an array and a window size k, return the maximum in each Sliding Window. Use a deque that stores indices in decreasing order of values.
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro