Stacks, queues, heaps and linked lists

Stack (last in, first out)

Valid parentheses:

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]: return False
        else:
            stack.append(ch)
    return not stack

Monotonic stack for "next greater element" and daily temperatures: keep a stack of indices whose answer isn't known yet; pop them when a bigger value arrives. Each index is pushed and popped once, so O(n).

def daily_temperatures(t):
    ans, stack = [0] * len(t), []
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop(); ans[j] = i - j
        stack.append(i)
    return ans

Queue (first in, first out)

Used for BFS and scheduling. In Python use collections.deque (popleft is O(1); list.pop(0) is O(n)).

Heap / priority queue

Gives the min (or max) in O(1) and inserts/removes in O(log n).

import heapq
def k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k: heapq.heappop(heap)   # keep the k largest
    return sorted(heap, reverse=True)           # O(n log k)

Uses: top K, merge K sorted lists, running median (two heaps), Dijkstra, task scheduling.

Linked lists

Practise pointer manipulation slowly and draw it.

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev, head = head, nxt
    return prev

Fast and slow pointers: detect a cycle (they meet if there is one), find the middle (slow is at the middle when fast reaches the end), find the k-th from the end (move one pointer k steps ahead first).

A dummy head node simplifies merging and deleting by removing special cases for the first node.

Problems to practise

Valid Parentheses, Min Stack, Daily Temperatures, Largest Rectangle in Histogram, Kth Largest Element, Merge K Sorted Lists, Reverse Linked List, Linked List Cycle, Merge Two Sorted Lists, Remove Nth Node From End, LRU Cache (hash map + doubly linked list).