Algorithmics

Arrays

Reverse an array in place. Reverse the order of an array's elements in place, without allocating a new array. Two pointers start at the ends and swap elements, moving towards the middle.
Implementation
```
def reverse_in_place(array):
    left, right = 0, len(array) - 1
    while left < right:
        array[left], array[right] = array[right], array[left]
        left += 1
        right -= 1
```

Matrix

Count ones in a binary matrix. Given a matrix filled with 0s and 1s, return the total number of 1s.
Implementation
```
def count_ones(matrix):
    return sum(map(sum, matrix))
```

Number of islands. Given an m × n grid which represents a map of 1 (land) and 0 (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Recursive

Mark visited land cells by setting them to "0", avoiding the need for a separate visited set.

def number_of_islands(grid):
    rows, cols, count = len(grid), len(grid[0]), 0

    def rec(x, y):
        if not (0 <= x < rows and 0 <= y < cols) or grid[x][y] == "0":
            return
        grid[x][y] = "0"
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            rec(x + dx, y + dy)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == "1":
                rec(i, j)
                count += 1
    return count

Iterative (DFS)

def number_of_islands(grid):
    rows, cols, count = len(grid), len(grid[0]), 0

    def dfs(x, y):
        stack = [(x, y)]
        grid[x][y] = "0"
        while stack:
            x, y = stack.pop()
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
                    grid[nx][ny] = "0"
                    stack.append((nx, ny))

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == "1":
                count += 1
                dfs(i, j)
    return count

Strings

Check if a string is a palindrome. Return True if the input string reads the same forwards and backwards, False otherwise.
Implementation
```
def is_palindrome(s):
    return s == s[::-1]
```
Count occurrences of a character. Given a string and a target character, return the number of times the target appears in the string.
Implementation
```
def count_char(s, target):
    return sum(char == target for char in s)
```

Hashing

Two Sum

Given an array of integers and a target integer, return the indices of the two numbers that add up to the target.

Implementation

def two_sum(array, target):
    seen = {}
    for index, value in enumerate(array):
        remaining = target - value
        if remaining in seen:
            return [index, seen[remaining]]
        seen[value] = index

Count occurrences of all characters

Given a string, return a dictionary mapping each character to the number of times it appears in the string.

Manual counting

def count_characters(s):
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    return count

With collections.Counter

from collections import Counter

def count_characters(s):
    return Counter(s)

Check if two strings are anagrams

Two strings are anagrams if one is a rearrangement of the other. Return True if and only if both strings have the same length and the same character counts.

Implementation

def are_anagrams(s1, s2):
    return len(s1) == len(s2) and Counter(s1) == Counter(s2)

Sorting and Searching

Binary Search

Given an array of integers sorted in ascending order and an integer target, return the index of the target or -1 if it does not exist.

Manual implementation

When computing the middle index, we generally use left + (right - left) // 2 instead of (left + right) // 2 to avoid integer overflow problems.
It is best not to use a strict inequality because:
- we exit the loop before the case left == right, so we need to check whether the middle index is the target after the loop.
- we have left = middle + 1 and right = middle.
It is better to use <= instead, where left = middle + 1 and right = middle - 1.

def search(array, target):
    left, right = 0, len(array) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if array[middle] < target:
            left = middle + 1
        elif array[middle] > target:
            right = middle - 1
        else:
            return middle
    return -1

With the bisect module

from bisect import bisect_left

index = bisect_left(array, target)

Recursion and Backtracking

Dynamic Programming

This section covers both bottom-up dynamic programming and top-down memoized recursion. The two are dual formulations of the same idea: a problem is decomposed into overlapping subproblems whose solutions are reused rather than recomputed. Bottom-up DP fills a table iteratively from the base cases up, while memoized recursion expresses the same recurrence directly and caches results as they are computed.

Count paths in a grid

Count all possible paths from the bottom-left to the top-right of an n × n grid, moving only right or up.

Bottom-up dynamic programming

def count_paths(n):
    dp = [[0 if i and j else 1 for i in range(n)] for j in range(n)]
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[n - 1][n - 1]

Top-down recursion with memoization

from functools import cache

def count_paths(n):
    @cache
    def rec(i, j):
        return 1 if not i or not j else rec(i - 1, j) + rec(i, j - 1)

    return rec(n - 1, n - 1)

Closed-form combinatorial solution

Any such path consists of n - 1 right moves and n - 1 up moves, so the count is the number of ways to choose which of the 2n - 2 steps are right moves, i.e. the binomial coefficient C(2n - 2, n - 1).

from math import comb

def count_paths(n):
    return comb(2 * n - 2, n - 1)

Greedy Algorithms

Trees

Definitions

Binary tree. A tree where each node has at most two children, referred to as the left and right child.

Class

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

Binary search tree. A binary tree where the key stored in each node is greater than every key in its left subtree, and less than or equal to every key in its right subtree.

N-ary tree. A tree where each node has an arbitrary number of children.

Class

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

Traversals

Pre-order. Visit the root, then the left subtree, then the right subtree.

Implementation

def pre_order(root):
    return [root.val] + pre_order(root.left) + pre_order(root.right) if root else []

In-order. Visit the left subtree, then the root, then the right subtree.

Implementation

def in_order(root):
    return in_order(root.left) + [root.val] + in_order(root.right) if root else []

Post-order. Visit the left subtree, then the right subtree, then the root.

Implementation

def post_order(root):
    return post_order(root.left) + post_order(root.right) + [root.val] if root else []

Depth

Maximum depth. Given the root of a binary tree, return its maximum depth.

Recursive

def maximum_depth(root):
    if not root:
        return 0
    return 1 + max(maximum_depth(root.left), maximum_depth(root.right))

Iterative (DFS)

def maximum_depth(root):
    stack, max_depth = [(root, 1)], 0
    while stack:
        node, depth = stack.pop()
        max_depth = max(max_depth, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return max_depth

Iterative (BFS)

from collections import deque

def maximum_depth(root):
    queue, depth = deque([root]), 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

Minimum depth. Given the root of a binary tree, return the number of nodes along the shortest path from the root down to the nearest leaf.

Recursive

The expression min(depths) or max(depths) returns the smaller of the two child depths, except when one child is missing (depth zero), in which case it returns the depth of the other child.

def min_depth(root):
    if not root:
        return 0
    depths = map(min_depth, (root.left, root.right))
    return 1 + (min(depths) or max(depths))

Iterative (BFS)

A FIFO queue visits nodes in order of depth, so the algorithm can return as soon as it reaches the first leaf.

from collections import deque

def min_depth(root):
    queue = deque([(root, 1)])
    while queue:
        node, level = queue.popleft()
        if not node:
            continue
        if not node.left and not node.right:
            return level
        queue += [(node.left, level + 1), (node.right, level + 1)]

Graphs

A graph is represented as a dictionary of nodes, where each node maps to its list of neighbors.

Traversals

Depth-first search. Explore each branch as deeply as possible before backtracking. Starting from a source node, use a stack to visit neighbors before siblings; return the set of all reachable nodes.

Implementation

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        stack.extend(graph[node])
    return visited

Breadth-first search. Visit a graph layer by layer, exploring all neighbors of a node before moving on to their neighbors. Using a queue ensures that nodes are explored in order of distance from the start; return the set of all reachable nodes.

Implementation

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        queue.extend(graph[node])
    return visited

Shortest Path

Dijkstra's algorithm. Compute the shortest distance from a source node to every other node in a graph with non-negative edge weights. A min-heap is used to repeatedly extract the closest unvisited node and relax the distances of its neighbors; return a dictionary mapping each reachable node to its shortest distance from the start.

Implementation

from heapq import heappop, heappush

def dijkstra(graph, start):
    stack, result = [(0, start)], {}
    while stack:
        dist, node = heappop(stack)
        if node in result:
            continue
        result[node] = dist
        for neighbor, weight in graph[node].items():
            heappush(stack, (dist + weight, neighbor))
    return result

Math

Basic Arithmetic

Check if an integer is odd. Return True if n is odd, False otherwise.
Implementation
```
def is_odd(n):
    return n % 2
```
FizzBuzz. Given an integer n, return "Fizz" if it is divisible by 3, "Buzz" if it is divisible by 5, "FizzBuzz" if it is divisible by both, and the number itself as a string otherwise.
Implementation
```
def fizz_buzz(n):
    result = ""
    if n % 3 == 0:
        result += "Fizz"
    if n % 5 == 0:
        result += "Buzz"
    if not result:
        result = str(n)
    return result
```
Fibonacci. The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2). Return the n-th term of the sequence.
Iterative

Only the two previous terms need to be kept in memory, giving constant space and linear time complexity.
```
def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
```
Recursive with memoization

A naive recursive implementation runs in exponential time because the same subproblems are recomputed; caching each result brings the complexity back down to linear time.
```
from functools import cache

@cache
def fibonacci(n):
    return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
```
Length of a Collatz sequence. The Collatz function is defined as f(n) = 3n + 1 if n is odd, and n // 2 otherwise. Starting from n, the function is iterated until the sequence reaches 1; return the number of steps required.
Implementation
```
def collatz(n):
    return 3 * n + 1 if n % 2 else n // 2


def collatz_sequence_length(n):
    count = 0
    while n > 1:
        n = collatz(n)
        count += 1
    return count
```

Bit Manipulation

Hamming weight. The Hamming weight of an integer is the number of 1s in its binary representation.

With the built-in bin

def hamming_weight(n):
    return bin(n)[2:].count("1")

With the bitwise right-shift operator

def hamming_weight(n):
    weight = 0
    while n > 0:
        weight += n & 1
        n >>= 1
    return weight

Exercises

Max area of an island. Given an m × n grid which represents a map of 1 (land) and 0 (water), return the maximum area of an island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Implementation

def maximum_area(grid):
    rows, cols = len(grid), len(grid[0])

    def rec(x, y):
        if not (0 <= x < rows and 0 <= y < cols) or not grid[x][y]:
            return 0
        grid[x][y] = 0
        return 1 + sum(rec(x + dx, y + dy) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)))

    return max(rec(i, j) for i in range(rows) for j in range(cols))