Data Structures and Algorithms Cheat Sheet

from collections import Counter, defaultdict, deque
import heapq
from bisect import bisect_left, bisect_right

Counter("banana").most_common(1)       # → [('a', 3)]

groups = defaultdict(list)
groups["even"].append(2)
dict(groups)                           # → {'even': [2]}

q = deque([1, 2, 3])
q.appendleft(0)
q.popleft()                            # → 0
q.pop()                                # → 3

h = [5, 1, 4]
heapq.heapify(h)
heapq.heappop(h)                       # → 1
heapq.nlargest(2, [7, 3, 9, 1])        # → [9, 7]

data = [1, 2, 2, 2, 5]
bisect_left(data, 2)                   # → 1
bisect_right(data, 2)                  # → 4

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

binary_search([3, 8, 15, 23, 42], 23)  # → 3

def pair_sum(sorted_nums, target):
    l, r = 0, len(sorted_nums) - 1
    while l < r:
        s = sorted_nums[l] + sorted_nums[r]
        if s == target:
            return l, r
        if s < target:
            l += 1
        else:
            r -= 1

pair_sum([1, 3, 4, 6, 8], 10)          # → (2, 3)

def longest_unique(s):
    seen, left, best = set(), 0, 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

longest_unique("abcabcbb")             # → 3

nums = [3, 1, 4, 1, 5]
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
prefix                                 # → [0, 3, 4, 8, 9, 14]
prefix[4] - prefix[1]                  # → 6

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

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

r = reverse(Node(1, Node(2, Node(3))))
[r.value, r.next.value, r.next.next.value]   # → [3, 2, 1]

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def inorder(n):
    return inorder(n.left) + [n.value] + inorder(n.right) if n else []

def height(n):
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

root = TreeNode(2, TreeNode(1), TreeNode(3, None, TreeNode(4)))
inorder(root)                          # → [1, 2, 3, 4]
height(root)                           # → 2

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}

def bfs(start):
    seen, order, queue = {start}, [], deque([start])
    while queue:
        v = queue.popleft()
        order.append(v)
        for n in graph[v]:
            if n not in seen:
                seen.add(n)
                queue.append(n)
    return order

def dfs(v, seen=None):
    seen = seen if seen is not None else []
    seen.append(v)
    for n in graph[v]:
        if n not in seen:
            dfs(n, seen)
    return seen

bfs("A")                               # → ['A', 'B', 'C', 'D']
dfs("A")                               # → ['A', 'B', 'D', 'C']

def dijkstra(g, start):
    dist = {v: float("inf") for v in g}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist

dijkstra({"A": [("B", 4), ("C", 1)], "C": [("B", 2)], "B": []}, "A")   # → {'A': 0, 'C': 1, 'B': 3}

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(50)                                # → 12586269025

def min_coins(coins, amount):
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]

min_coins([1, 3, 4], 6)                # → 2