422 companion flashcards · AI-assisted study content · Open the deck →
This deck is a hands-on review of the core algorithms and techniques that show up again and again in coding interviews and computer science coursework. It walks through classic sorting and searching methods like binary search, bubble sort, merge sort, and quick sort, then moves into graph algorithms such as BFS, DFS, Dijkstra's algorithm, topological sort, and union-find. You'll also practice important problem-solving patterns including the two pointers and sliding window techniques, dynamic programming with Fibonacci and 0/1 knapsack, and Kadane's algorithm for maximum subarray sums. Each card asks you to recall both the concept and a working Python implementation, so you're training understanding and code at the same time.
The deck is a great fit if you're preparing for technical interviews, studying for a data structures and algorithms course, or simply want to keep your Python sharp by revisiting fundamentals from scratch. Because every card combines a definition, a time complexity question, and a coding task, it works well for learners who already have some basic programming experience and want to deepen their problem-solving skills.
To get the most out of your study sessions, try to answer the conceptual question first and write out the code on paper or in an editor before flipping the card. Spacing your reviews over several short sessions beats cramming everything into one long sitting, especially for algorithms where patterns need time to sink in. If you get stuck on an implementation, take a moment to trace through a small example by hand before peeking at the answer. That's where the real learning happens.
This chapter covers the essential searching and sorting algorithms that form the backbone of algorithmic problem solving. Binary Search is the cornerstone searching technique on sorted arrays, achieving O(log n) time by repeatedly halving the search space. The technique extends beyond simple lookup to find insertion points (bisect_left and bisect_right), search in rotated sorted arrays, and even binary search on the answer space when the problem exhibits monotonic properties.
Sorting algorithms present a fascinating trade-off between time complexity, space usage, and stability. Comparison-based sorts like Bubble Sort, Insertion Sort, and Selection Sort run in O(n²) time but use O(1) space, making them useful for small or nearly-sorted data. More sophisticated O(n log n) algorithms like Merge Sort, Quick Sort, and Heap Sort divide and conquer the problem. Merge Sort is stable and predictable but requires O(n) extra space, while Quick Sort averages O(n log n) but can degrade to O(n²) in the worst case.
For specialized data, non-comparison-based sorts like Counting Sort and Radix Sort achieve O(n + k) and O(d × (n + k)) respectively by exploiting numerical properties. Shell Sort generalizes insertion sort with gap sequences. The choice of sorting algorithm often depends on the input characteristics: data size, distribution, stability requirements, and available memory all factor into the decision.
Several powerful techniques transform seemingly complex array problems into elegant linear-time solutions. The Two Pointers technique uses two indices moving toward each other or in the same direction, achieving O(n) time on sorted arrays. Classic applications include finding pairs summing to a target (two_sum_sorted), solving the 3Sum problem, and computing container areas with most water by moving the shorter pointer inward.
The Sliding Window technique maintains a contiguous subarray and slides it across the input, adding elements on one end while removing from the other. Fixed-size windows efficiently compute maximum sums of subarrays, while variable-size windows solve problems like minimum window substring and longest substring without repeating characters. The combination of sliding windows with monotonic queues enables solving sliding window maximum in O(n) amortized time.
Prefix Sum arrays enable O(1) range sum queries after O(n) preprocessing, with the technique extending naturally to 2D for sub-rectangle queries. Other specialized array techniques include Kadane's algorithm for maximum subarray sum in O(n), the Dutch National Flag algorithm for three-way partitioning in a single pass, and the Difference Array for efficient range updates. The trap rain water problem and product of array except self problem showcase how two-pointer techniques can replace extra space with elegant pointer manipulation.
Binary trees and Binary Search Trees (BSTs) form the foundation of hierarchical data structures. A BST maintains the invariant that left children are less than the parent and right children are greater, enabling O(log n) average-case search and insert. Tree traversals come in three primary flavors: inorder (Left-Root-Right) yields sorted order for BSTs, preorder (Root-Left-Right) is used for serialization, and postorder (Left-Right-Root) is ideal for deletion operations. Level-order traversal uses BFS to visit nodes level by level, with variants like zigzag traversal alternating direction.
Advanced tree operations include finding the Lowest Common Ancestor (LCA), validating BST property, computing tree diameter, and detecting balanced height. The LCA problem has an elegant recursive solution for general binary trees, while BSTs leverage their sorted property for an even simpler iterative approach. The Maximum Path Sum problem requires careful tracking because the optimal path may pass through or end at any node. Tree construction from traversals combines preorder and inorder arrays with hash maps for O(n) reconstruction.
Specialized tree structures extend these concepts in powerful ways. The Trie (Prefix Tree) stores strings character by character, enabling O(m) prefix operations used in autocomplete and spell check. The Segment Tree and Binary Indexed Tree (Fenwick Tree) support efficient range queries with O(log n) operations, with the segment tree's lazy propagation variant extending this to range updates. More exotic structures like AVL trees, red-black trees, and treaps maintain balance to guarantee O(log n) operations. Morris Traversal achieves O(1) space tree traversal by using threaded binary trees, temporarily linking rightmost nodes back to ancestors.
Graph traversal forms the basis of countless algorithms. Breadth-First Search (BFS) explores level by level using a queue, making it ideal for shortest path in unweighted graphs, level-order traversals, and bipartite checks. Depth-First Search (DFS) goes as deep as possible before backtracking, expressed elegantly either recursively or iteratively with a stack. DFS underlies cycle detection, topological sorting, strongly connected components, and solving maze problems. Both traversals run in O(V + E) time.
Shortest path algorithms address weighted graphs. Dijkstra's algorithm with a min-heap finds shortest paths from a source in O((V + E) log V) for graphs with non-negative weights. Bellman-Ford handles negative weights in O(V × E) and detects negative cycles. Floyd-Warshall computes all-pairs shortest paths in O(V³). A* search extends Dijkstra with a heuristic for faster goal-directed search, optimal when the heuristic is admissible. SPFA offers practical speedups over Bellman-Ford by only relaxing edges from recently updated nodes.
Minimum Spanning Trees (MST) connect all vertices with minimum total weight. Kruskal's algorithm sorts edges and greedily adds them if they don't form a cycle, using Union-Find for cycle detection. Prim's algorithm grows the MST from a starting vertex, adding the cheapest edge to an unvisited vertex via a min-heap. Advanced graph topics include finding articulation points and bridges (critical nodes/edges whose removal disconnects the graph) using DFS with discovery times and low-link values. Tarjan's and Kosaraju's algorithms find strongly connected components in O(V + E), while topological sort using Kahn's algorithm processes nodes with in-degree zero to detect cycles. Maximum flow algorithms like Edmonds-Karp and Dinic's solve network flow problems with applications in bipartite matching and scheduling.
Dynamic Programming solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation. The Fibonacci example illustrates both approaches: top-down memoization uses recursion with a cache, while bottom-up tabulation iteratively builds the solution. Bottom-up often achieves O(1) space when only the previous values are needed, as in House Robber and Climbing Stairs problems where the recurrence simplifies to Fibonacci-like formulas.
Classic DP problems include the 0/1 Knapsack (each item used at most once), Unbounded Knapsack (items reusable), Coin Change (minimum coins or count ways), and Longest Common Subsequence. These problems typically use 1D or 2D DP arrays with transitions based on include/exclude choices. The target sum and partition equal subset sum problems reduce cleverly to knapsack variants by transforming the problem formulation.
String-based DP problems form a substantial category. Edit Distance (Levenshtein) computes minimum insertions, deletions, and substitutions using a 2D table. The Longest Palindromic Subsequence equals the LCS of a string and its reverse. Regular Expression Matching and Wildcard Matching handle pattern matching with special characters. Interval DP applies to problems where decisions affect ranges, like Burst Balloons and Matrix Chain Multiplication. The Super Egg Drop problem inverts the DP direction, computing the maximum floors checkable with given moves and eggs. DP on DAGs and trees extends the technique to graph structures, with digit DP handling counting problems with positional constraints.
The heap (priority queue) is a complete binary tree maintaining the heap property. Min-heaps support O(log n) insert and extract-min, with O(1) peek. Python's heapq module implements min-heap efficiently, with max-heap simulated by negating values. Heaps power algorithms like Dijkstra's shortest path, top-k problems, Kth largest element, and median maintenance. Heap Sort builds a max-heap and repeatedly extracts the maximum for an in-place O(n log n) sort.
Union-Find (Disjoint Set Union) tracks elements partitioned into disjoint sets, supporting union and find operations in nearly O(1) amortized time using path compression and union by rank. It solves problems like finding connected components, detecting cycles in undirected graphs (Redundant Connection), merging accounts sharing emails, and implementing Kruskal's MST algorithm. The data structure elegantly reduces many graph problems to tracking component membership.
Specialized structures address specific query patterns. The Sparse Table precomputes answers for power-of-2 ranges, enabling O(1) idempotent queries like range minimum after O(n log n) preprocessing. Sqrt Decomposition divides arrays into √n-sized blocks, achieving O(√n) queries. The Line Sweep technique processes sorted events for problems like interval union length and platform counting. More exotic structures include the Bloom Filter (probabilistic set membership), Skip List (probabilistic balanced BST), Treap (randomized BST combining tree and heap properties), and Persistent Segment Tree (preserving historical versions with O(log n) new nodes per update).
String matching algorithms efficiently find patterns within text. The naive approach runs in O(n × m), but sophisticated algorithms achieve linear or near-linear time. KMP (Knuth-Morris-Pratt) precomputes a failure function (LPS array) to skip redundant comparisons, running in O(n + m). Rabin-Karp uses rolling hashes to compare windows in O(n + m) average time, excelling at multi-pattern search. The Z-Algorithm computes the Z-array storing longest prefix matches at each position, also running in O(n + m).
Backtracking systematically explores solution spaces by building candidates incrementally and pruning invalid branches. Classic applications include generating permutations and combinations, solving N-Queens and Sudoku, and finding all subsets. The Word Search problem combines backtracking with grid traversal. Branch-and-bound techniques like the minimum cost to cut a stick use interval DP with strategic pruning. Combination Sum variants handle items that can be used unlimited times versus once.
Bit manipulation unlocks elegant O(1) operations: checking powers of two with n & (n-1), counting set bits with Brian Kernighan's algorithm, and finding the unique element using XOR properties (since a^a = 0). The Boyer-Moore Voting algorithm finds the majority element in O(n) time and O(1) space. Misra-Gries generalizes this to find elements appearing more than n/k times. Other specialized techniques include Greedy algorithms with proof of optimality (activity selection, fractional knapsack, Huffman coding), Sweep Line for geometric problems, and Matrix Exponentiation for computing Fibonacci and linear recurrences in O(log n) time. Monotonic stacks and deques solve next-greater-element, daily temperatures, and sliding window extremes in linear time, while the Reservoir Sampling technique enables uniform random selection from streams of unknown size.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1def word_break(s, word_dict):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for word in word_dict:
wl = len(word)
if i >= wl and dp[i - wl] and s[i-wl:i] == word:
dp[i] = True
break
return dp[n]
# word_break("leetcode", {"leet", "code"}) → Trueclass MinStack:
def __init__(self):
self.stack = [] # (val, current_min)
def push(self, val):
curr_min = min(val, self.stack[-1][1] if self.stack else val)
self.stack.append((val, curr_min))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def getMin(self):
return self.stack[-1][1]def find_target_sum_ways(nums, target):
total = sum(nums)
if (total + target) % 2 or abs(target) > total:
return 0
subset_sum = (total + target) // 2
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for j in range(subset_sum, num - 1, -1):
dp[j] += dp[j - num]
return dp[subset_sum]
# find_target_sum_ways([1,1,1,1,1], 3) → 5from collections import deque, defaultdict
def spfa(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
in_queue = [False] * n
queue = deque([src])
in_queue[src] = True
while queue:
u = queue.popleft()
in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
return distdef min_window_subsequence(s, t):
n, m = len(s), len(t)
best = ""
best_len = float('inf')
i = 0
while i < n:
# Forward: find end of window
j = 0
k = i
while k < n and j < m:
if s[k] == t[j]:
j += 1
k += 1
if j < m: break
end = k - 1
# Backward: shrink window from end
j = m - 1
while j >= 0:
if s[end] == t[j]:
j -= 1
end -= 1
start = end + 1
if k - start < best_len:
best_len = k - start
best = s[start:start + best_len]
i = start + 1
return bestdef find_words(board, words):
trie = {}
for w in words:
node = trie
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w
m, n = len(board), len(board[0])
result = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node: return
nxt = node[ch]
if '#' in nxt:
result.append(nxt.pop('#'))
board[r][c] = '.'
for dr, dc in ((0,1),(0,-1),(1,0),(-1,0)):
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '.':
dfs(nr, nc, nxt)
board[r][c] = ch
if not nxt: del node[ch] # prune
for r in range(m):
for c in range(n):
dfs(r, c, trie)
return resultclass NestedIterator:
def __init__(self, nestedList):
self.stack = list(reversed(nestedList))
def next(self):
return self.stack.pop().getInteger()
def hasNext(self):
while self.stack:
top = self.stack[-1]
if top.isInteger():
return True
self.stack.pop()
self.stack.extend(reversed(top.getList()))
return False
# Usage:
# it = NestedIterator([[1,1],2,[1,1]])
# while it.hasNext(): print(it.next())
# → 1, 1, 2, 1, 1def kth_element(arr1, arr2, k):
if len(arr1) > len(arr2):
return kth_element(arr2, arr1, k)
n1, n2 = len(arr1), len(arr2)
lo = max(0, k - n2)
hi = min(k, n1)
while lo <= hi:
cut1 = (lo + hi) // 2
cut2 = k - cut1
l1 = arr1[cut1-1] if cut1 > 0 else float('-inf')
l2 = arr2[cut2-1] if cut2 > 0 else float('-inf')
r1 = arr1[cut1] if cut1 < n1 else float('inf')
r2 = arr2[cut2] if cut2 < n2 else float('inf')
if l1 <= r2 and l2 <= r1:
return max(l1, l2)
elif l1 > r2:
hi = cut1 - 1
else:
lo = cut1 + 1
# kth_element([2,3,6,7,9], [1,4,8,10], 5) → 6from functools import cmp_to_key
def largest_number(nums):
strs = [str(x) for x in nums]
strs.sort(key=cmp_to_key(
lambda a, b: -1 if a+b > b+a else (1 if a+b < b+a else 0)
))
result = ''.join(strs)
return '0' if result[0] == '0' else result
# largest_number([3, 30, 34, 5, 9]) → "9534330"
# largest_number([10, 2]) → "210"
# largest_number([0, 0]) → "0"Drill this topic
422 flashcards on Algorithms Code — free, no signup needed to start.
Study Algorithms Code flashcardsLearnWiki pages are generated with AI assistance from LearnCoachAssist's reviewed study catalog and may contain errors — verify anything critical against your course materials.