Part 2 of 6. Stacks, Queues, Linked Lists, and Hashing — the four data structures that appear in every interview. Master these and 40% of all interview problems become straightforward pattern recognition.
Pattern 1 — Matching/Nesting: Opening brackets, tags, function calls. Push opens, pop-and-check closes. Valid Parentheses is the archetype.
Pattern 2 — "Next Greater/Smaller" problems: Monotonic stack. Maintain a stack in increasing or decreasing order. When a new element breaks the monotone property, the elements it pops have found their answer.
Pattern 3 — Undo/History: Browser back button, undo in text editors, DFS traversal without recursion.
Pattern 4 — Expression evaluation: Infix to postfix, calculator problems. Two stacks for operators and operands.
Given a string with only ( ) { } [ ], determine if the brackets are valid. Opening brackets must be closed in correct order.
"()[]{}"true"([)]"false"{[]}"trueFor every opening bracket, push it. For every closing bracket, the top of the stack must be the matching opener. If it's not (or the stack is empty), the string is invalid. At the end, the stack must be empty (all openers got matched).
Design a stack that supports push, pop, top, and getMin() — all in O(1). getMin() returns the minimum element in the stack.
A plain stack loses the minimum when you pop. The trick: maintain a second stack (minSt) that always stores the current minimum at each level. When pushing x, push min(x, minSt.top()) to minSt. When popping, pop both stacks together. getMin() = minSt.top().
Given daily temperatures, return an array where each element is the number of days to wait for a warmer temperature. 0 if no warmer day exists.
[73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]Maintain a stack of indices in decreasing temperature order. When a new temperature is higher than the top, we've found the "next warmer day" for the top element — pop it and record the answer (current index − popped index). All remaining elements in the stack at the end get answer 0.
Part I: For each element in nums1, find the next greater element in nums2. nums1 is a subset of nums2.
Part II: Circular array — the next greater of the last element wraps around to the beginning.
nums1=[4,1,2]
nums2=[1,3,4,2][-1,3,-1][1,2,1][2,-1,2]For the circular version, iterate from i=0 to 2n-1 using a[i%n]. This simulates the wrap-around. Only push indices when i < n (first pass). Answers are filled during both passes.
Find the area of the largest rectangle that can be formed within a histogram (array of bar heights). Bars are adjacent and width = 1.
[2,1,5,6,2,3]10bars 5,6 → height=5
width=2 → area=10A bar of height h can extend left until it hits a shorter bar, and right until it hits a shorter bar. Monotonic increasing stack: when bar[i] < bar[stack.top()], the top bar's right boundary has been found. The left boundary is the new stack top after popping. Area = height × (right − left − 1). Append a sentinel 0 to flush all remaining bars.
Given a binary matrix, find the largest rectangle containing only 1s. Return its area.
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]6For each cell (i,j), compute the height = number of consecutive 1s above (including current row). This turns each row into a histogram. Apply the Largest Rectangle in Histogram algorithm to each row's histogram. The maximum across all rows is the answer.
Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Numbers are operands, then operator consumes the top two values.
["2","1","+","3","*"]9((2+1)*3) = 9Walk tokens left to right. If token is a number → push. If token is an operator → pop two values (b first, then a), compute (a op b), push result. Final answer is the single remaining element on the stack.
Implement a basic calculator to evaluate a string expression with +, -, *, / (integer division), no parentheses. Return the result.
"3+2*2"7" 3/2 "1Key insight: + and - have lower precedence so push the number (with sign) onto the stack and defer addition. * and / have higher precedence so apply them immediately to the stack top. Final answer = sum of all stack values.
Decode an encoded string where k[encoded_string] means repeat encoded_string k times. Encoding can be nested.
"3[a]2[bc]""aaabcbc""2[abc]3[cd]ef""abcabccdcdcdef"Two stacks: one for counts, one for strings built so far. On [: push current string and current count, reset both. On ]: pop count and previous string, repeat current string count times, prepend previous. On digit: build count. On letter: append to current string.
Array of asteroids. Positive = moving right, negative = moving left. Same direction: no collision. Opposite: smaller explodes (both if equal). Return the state after all collisions.
[5,10,-5][5,10][8,-8][]Use a stack. For each asteroid: if stack is empty, or current is positive, or stack top is negative → push (no collision). Otherwise: compare sizes. If current |size| wins → pop and re-check. If equal → pop both. If stack top wins → current is destroyed.
Cars on a single-lane road. Each car has position and speed. Cars in front can't be passed. Cars that meet form a fleet and travel at the slower car's speed. Return number of fleets reaching the target.
target=12
pos=[10,8,0,5,3]
speed=[2,4,1,1,3]3Sort cars by position (descending). Compute each car's time to reach target = (target - pos) / speed. A car forms a new fleet if its time > the fleet in front's time (it's slower, so it catches up). Use a stack: if current car's time ≤ stack top's time, it merges into the fleet ahead (don't push). If greater, it forms a new fleet (push). Stack size = number of fleets.
Remove k digits from number string to make it the smallest possible number. Return the result as a string (no leading zeros).
"1432219", k=3"1219""10200", k=1"200"Greedily remove digits from the left when they're larger than the next digit (a "peak"). Use a monotonic increasing stack. Pop when stack.top() > current digit AND k > 0. The resulting stack forms the answer.
For each day's stock price, compute the span — the number of consecutive days before (and including) today where the price was ≤ today's price.
[100,80,60,70,60,75,85][1,1,1,2,1,4,6]The span of day i = i − (index of the last day with price > today's price). Monotonic decreasing stack of (price, span) or indices. When popping, accumulate the spans of all popped elements (they were all ≤ current).
Score a balanced parentheses string. () = 1, AB = A+B, (A) = 2×A.
"(()(()))"6Solve Trapping Rain Water (seen in Part 1, Q007) using a monotonic stack — a completely different mental model that accumulates water in horizontal layers instead of vertical columns.
Maintain a monotonic decreasing stack of indices. When height[i] > height[stack.top()], a basin has formed: the bottom is the popped element, left wall is new stack top, right wall is current i. Compute the water for this horizontal layer. Repeat for all basins.
Queue (FIFO): BFS traversal, level-order processing, task scheduling. Always prefer queue over stack when you need to process in order of arrival.
Deque (Double-ended): When you need O(1) push/pop from both ends. Sliding window maximum (see Q020) uses a monotonic deque. Also used to implement stacks and queues with additional powers.
Priority Queue (Heap): When "next to process" = "most extreme value". Dijkstra, top-K, merge K sorted, median stream. See Part 3 for heap problems.
Implement a queue (FIFO) using only two stacks. Implement push, pop, peek, empty.
Input stack for push. Output stack for pop/peek. Transfer from input → output only when output is empty and you need to pop/peek. This amortises to O(1) per operation — each element crosses between stacks at most once.
Implement a stack using only two queues. push, pop, top, empty.
After pushing x to q2, move all of q1 into q2, then swap q1 and q2. Now q1.front() is always the most recently pushed element. pop/top just access q1.front(). Push is O(n), pop is O(1).
Design a circular queue of capacity k with enqueue, dequeue, front, rear, isEmpty, isFull — all O(1).
Use a fixed-size array. head points to front, tail points to next insertion spot. Both advance circularly using % k. Track size with a count. Full when count==k, empty when count==0.
Given tasks (array of characters) and cooldown n — same task must be at least n slots apart. Find minimum total slots to finish all tasks.
tasks=["A","A","A","B","B","B"]
n=28A B _ A B _ A BThe most frequent task (maxFreq) creates (maxFreq-1) "cooling slots". Each slot has (n+1) units (task + n idle). Total = (maxFreq-1)×(n+1) + (# tasks with maxFreq). But we need at least tasks.size() slots if tasks fill all the idle time. Answer = max(tasks.size(), formula).
Hit Counter: Design a hit counter which counts hits received in the past 5 minutes (300 seconds). hit(timestamp) records a hit. getHits(timestamp) returns hits in last 300 seconds.
Use a queue of timestamps. On hit: push timestamp. On getHits: pop from front while front is <= timestamp - 300 (stale). Return queue size.
Two factions Radiant (R) and Dire (D). Each senator can ban one senator from the other faction. Senators take turns in circular order. The faction with all surviving senators wins. Predict the winner.
"RDD""Dire"Maintain two queues: indices of all R senators and all D senators. At each step, the front of each queue is the next senator to act. Whichever has the smaller index goes first — it bans the other (pop that queue). The winner re-enters the queue with index += n (simulating next round).
Implement a class that counts recent requests within the last 3000 milliseconds. ping(t) adds a request at time t and returns the count of requests in [t-3000, t].
Given array, for each window size k (1 to n), find the maximum of all minimum values of all windows of size k. Return the result array.
[10,20,30,50,10,70,30][70,30,20,10,10,10,10]For each element a[i], find how far it spans as a window minimum: the longest window where it's the smallest. This is (nextSmaller[i] - prevSmaller[i] - 1). Use monotonic stack to find prevSmaller[] and nextSmaller[] arrays. Then fill the answer array: ans[span-1] = max(ans[span-1], a[i]). Finally fill right-to-left since ans[k-1] ≥ ans[k].
Pattern 1 — Dummy Node: Prepend a dummy head node to avoid edge cases (empty list, inserting at head). Return dummy.next at the end. Appears in merge, remove, insert.
Pattern 2 — Fast/Slow Pointers: Detect cycles (Floyd's), find middle, find nth from end. Fast moves 2x, slow 1x.
Pattern 3 — Reversal: Three-pointer walk (prev, cur, next). In-place O(1) space. The base of all reversal problems.
Pattern 4 — Two Passes: First pass counts length or finds target. Second pass makes changes. Efficient when you need position from end.
Reverse a singly linked list iteratively and recursively.
1→2→3→4→5→null5→4→3→2→1→nullThree pointers: prev (starts null), cur (starts head), nxt (temp). At each step: save nxt = cur.next, point cur.next = prev, advance prev = cur, advance cur = nxt. When cur is null, prev is the new head.
Merge two sorted linked lists. Return the head of the merged sorted list in-place (no extra nodes).
1→2→4 and 1→3→41→1→2→3→4→4Create a dummy node as the starting point. Walk both lists with pointer tail. At each step, pick the smaller front node, attach it to tail, advance that list. After one list exhausts, attach the rest of the other. Return dummy.next.
#141: Detect if a linked list has a cycle (O(1) space).
#142: Find the node where the cycle begins.
Fast (2 steps) and slow (1 step). If there's a cycle, fast laps slow inside it → they meet. For the cycle start: reset one pointer to head, advance both one step at a time → they meet at the cycle entry. This works due to a mathematical proof involving distances.
Remove the nth node from the end of the list in one pass.
1→2→3→4→5, n=21→2→3→5Two pointers starting at dummy head. Advance fast pointer n+1 steps. Then advance both until fast is null. slow is now the node BEFORE the one to delete. Relink: slow.next = slow.next.next. The dummy head handles the edge case where we delete the head.
Reorder list L0→L1→...→Ln to L0→Ln→L1→Ln-1→L2→Ln-2... in-place.
1→2→3→4→51→5→2→4→31) Find middle with fast/slow pointers. 2) Reverse the second half in-place. 3) Merge the two halves by alternating nodes. This is O(n) time and O(1) space.
Return the middle node of a linked list. If even length, return the second middle.
1→2→3→4→531→2→3→4→5→64Merge k sorted linked lists into one sorted linked list.
Push the head of each non-null list into a min-heap ordered by value. Pop the smallest, append to result, push that node's next (if exists). Repeat until heap is empty. Total nodes = n, each enters/exits heap once at O(log k). Overall: O(n log k).
Collect all values, sort, rebuild list. O(n log n) but loses the sorted structure.
Merge lists in pairs. Like merge sort. O(n log k) but more complex code.
Priority queue of (value, node*). Always extract global min cleanly.
Reverse the nodes of the list from position left to right (1-indexed) in one pass.
1→2→3→4→5, left=2, right=41→4→3→2→5Walk (left-1) steps to reach the node before reversal starts (call it prev). Then for (right-left) times: take the node after prev.next (call it nxt), and move it to the front of the reversed segment. This is the "insertion at front" reversal technique.
Deep copy a linked list where each node has a next and a random pointer (can point to any node or null). Return the head of the copied list.
Pass 1: Walk original list. For each node, create a new copy node and store it in a hash map: old → new. Pass 2: Walk again. Set new.next = map[old.next] and new.random = map[old.random]. Works because the map lets you look up any new node by its old counterpart.
Design an LRU (Least Recently Used) cache with O(1) get and put operations. Evict the least recently used item when capacity is exceeded.
Hash map: key → node pointer. Gives O(1) lookup. Doubly linked list: maintains recency order. Head = MRU (most recently used), tail = LRU. On get/put: move node to head. On eviction: remove tail. Two dummy sentinel nodes (head and tail) eliminate all edge cases. The combination is called a LinkedHashMap.
Swap every two adjacent nodes and return the head. Swap node links, not values.
1→2→3→42→1→4→3Use a dummy head. For each pair (first, second): prev.next = second, first.next = second.next, second.next = first, advance prev = first. Draw this on paper first — the 4 pointer assignments must happen in exactly this order.
Given a linked list, reverse every k nodes in groups. If remaining nodes < k, leave them as-is. Modify links — not values.
1→2→3→4→5, k=22→1→4→3→51→2→3→4→5, k=33→2→1→4→5Check if at least k nodes remain. If not → return head as-is. Count k nodes, keep pointer to kth node and the node after. Reverse the k-node group. The original head becomes the new tail. Connect it to the recursive result of the remaining list.