Introduction
Coding interviews can be daunting, especially when you’re faced with algorithmic problems under time pressure. However, the good news is that most coding interview questions fall into predictable patterns that can be solved using a core set of algorithms and data structures.
In this comprehensive guide, we’ll explore the top 10 algorithms that frequently appear in Python coding interviews, from tech giants like Google and Meta to startups. Each algorithm is explained with:
- Core principles and intuition
- Time and space complexity analysis
- Complete Python implementations with detailed comments
- Step-by-step execution examples
- Common pitfalls and edge cases
- Problem variations and practical tips
Whether you’re preparing for your first technical interview or brushing up on fundamentals, this guide will help you build a solid algorithmic foundation.
For a comprehensive guide that covers these algorithms with real interview questions, Cracking the Coding Interview is the industry standard and pairs perfectly with hands-on practice.
1. Breadth-First Search (BFS)
To deepen your Python implementation skills beyond basic algorithms, Python Cookbook provides practical patterns and idioms used by experienced developers.
Core Principle
BFS explores a graph level by level, visiting all neighbors of a node before moving to the next level. It uses a queue (FIFO) data structure to maintain the order of exploration.
When to use BFS:
– Finding the shortest path in unweighted graphs
– Level-order traversal in trees
– Finding connected components
– Solving maze/grid problems
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Visit each vertex once and explore all edges | |
| Space | Queue can hold up to all vertices in worst case |
Where = number of vertices, = number of edges.
Python Implementation
from collections import deque
def bfs_shortest_path(graph, start, end):
"""
Find shortest path in unweighted graph using BFS.
Args:
graph: dict mapping node -> list of neighbors
start: starting node
end: target node
Returns:
list: shortest path from start to end, or None if no path exists
"""
# Queue stores tuples of (current_node, path_to_current_node)
queue = deque([(start, [start])])
visited = {start} # Track visited nodes to avoid cycles
while queue:
current, path = queue.popleft() # FIFO: process earliest added node
# Check if we reached the target
if current == end:
return path
# Explore all neighbors
for neighbor in graph.get(current, []):
if neighbor not in visited:
visited.add(neighbor)
# Add neighbor to queue with updated path
queue.append((neighbor, path + [neighbor]))
return None # No path found
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
result = bfs_shortest_path(graph, 'A', 'F')
print(f"Shortest path: {result}") # Output: ['A', 'C', 'F']
Step-by-Step Execution
Input: graph (as above), start='A', end='F'
| Step | Queue | Current | Path | Visited | Action |
|---|---|---|---|---|---|
| 0 | [(‘A’, [‘A’])] | – | – | {‘A’} | Initialize |
| 1 | [(‘B’, [‘A’,’B’]), (‘C’, [‘A’,’C’])] | A | [‘A’] | {‘A’,’B’,’C’} | Process A, add neighbors |
| 2 | [(‘C’, [‘A’,’C’]), (‘D’, [‘A’,’B’,’D’]), (‘E’, [‘A’,’B’,’E’])] | B | [‘A’,’B’] | {‘A’,’B’,’C’,’D’,’E’} | Process B |
| 3 | [(‘D’, [‘A’,’B’,’D’]), (‘E’, [‘A’,’B’,’E’]), (‘F’, [‘A’,’C’,’F’])] | C | [‘A’,’C’] | {‘A’,’B’,’C’,’D’,’E’,’F’} | Process C, add F |
| 4 | – | F | [‘A’,’C’,’F’] | – | Found target! Return path |
Output: ['A', 'C', 'F'] (shortest path with 2 edges)
Common Mistakes & Edge Cases
- Forgetting to mark nodes as visited: Leads to infinite loops in graphs with cycles
- Using a stack instead of queue: This becomes DFS, not BFS
- Not handling disconnected graphs: Check if
endis reachable - Empty graph or invalid start/end nodes: Add input validation
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Binary tree level-order traversal | LeetCode 102 |
| Medium | Shortest path in grid with obstacles | LeetCode 1293 |
| Hard | Word Ladder (shortest transformation) | LeetCode 127 |
2. Depth-First Search (DFS)
Core Principle
DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (LIFO) – either explicitly or via recursion.
When to use DFS:
– Finding all paths or solutions
– Detecting cycles in graphs
– Topological sorting
– Solving puzzles (N-Queens, Sudoku)
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Visit each vertex once and explore all edges | |
| Space | Recursion stack depth (or explicit stack) |
Python Implementation (Recursive)
def dfs_all_paths(graph, start, end, path=None, all_paths=None):
"""
Find all paths from start to end using DFS (recursive).
Args:
graph: dict mapping node -> list of neighbors
start: current node
end: target node
path: current path (used in recursion)
all_paths: accumulator for all found paths
Returns:
list: all possible paths from start to end
"""
if path is None:
path = []
if all_paths is None:
all_paths = []
# Add current node to path
path = path + [start]
# Base case: reached target
if start == end:
all_paths.append(path)
return all_paths
# Recursive case: explore neighbors
for neighbor in graph.get(start, []):
if neighbor not in path: # Avoid cycles
# Recursively explore neighbor
dfs_all_paths(graph, neighbor, end, path, all_paths)
return all_paths
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': ['E'],
'E': ['F'],
'F': []
}
result = dfs_all_paths(graph, 'A', 'F')
print(f"All paths: {result}")
# Output: [['A', 'B', 'D', 'E', 'F'], ['A', 'B', 'E', 'F'], ['A', 'C', 'F']]
Step-by-Step Execution
Input: graph (as above), start='A', end='F'
Recursion tree visualization:
A
├── B
│ ├── D
│ │ └── E → F ✓ (path 1: A→B→D→E→F)
│ └── E → F ✓ (path 2: A→B→E→F)
└── C → F ✓ (path 3: A→C→F)
Output: 3 paths found
Common Mistakes & Edge Cases
- Modifying shared path variable: Use
path + [start]instead ofpath.append(start)to avoid side effects - Not checking for cycles: Infinite recursion in cyclic graphs
- Stack overflow on deep graphs: Consider iterative DFS with explicit stack
- Forgetting base case: Causes unnecessary exploration
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Path exists in binary tree | LeetCode 112 |
| Medium | Number of islands | LeetCode 200 |
| Hard | Word Search II (Trie + DFS) | LeetCode 212 |
3. Dynamic Programming (DP)
Core Principle
DP solves complex problems by breaking them into overlapping subproblems and storing solutions to avoid redundant computation. Two approaches:
- Top-down (Memoization): Recursive with caching
- Bottom-up (Tabulation): Iterative with table
When to use DP:
– Optimal substructure: Optimal solution contains optimal solutions to subproblems
– Overlapping subproblems: Same subproblems solved multiple times
– Problems asking for “maximum/minimum”, “count ways”, “longest/shortest”
Complexity Analysis (Fibonacci Example)
| Approach | Time | Space | Explanation |
|---|---|---|---|
| Naive recursion | Exponential due to redundant calls | ||
| Memoization | Each subproblem solved once | ||
| Tabulation | Iterative with table | ||
| Space-optimized | Store only last 2 values |
Python Implementation: 0/1 Knapsack Problem
Problem: Given weights and values of items, find maximum value that fits in knapsack of capacity .
def knapsack_dp(weights, values, capacity):
"""
Solve 0/1 knapsack using bottom-up DP.
Args:
weights: list of item weights
values: list of item values
capacity: knapsack capacity
Returns:
int: maximum value achievable
"""
n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# Fill table bottom-up
for i in range(1, n + 1):
for w in range(capacity + 1):
# Option 1: Don't take item i-1
dp[i][w] = dp[i-1][w]
# Option 2: Take item i-1 (if it fits)
if weights[i-1] <= w:
# Take max of (don't take, take)
dp[i][w] = max(
dp[i][w], # Don't take
dp[i-1][w - weights[i-1]] + values[i-1] # Take
)
return dp[n][capacity]
# Example usage
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
result = knapsack_dp(weights, values, capacity)
print(f"Maximum value: {result}") # Output: 9 (items 2 and 3)
Step-by-Step Execution
Input: weights=[1,3,4,5], values=[1,4,5,7], capacity=7
DP table construction:
| i w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
| 3 | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
| 4 | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
Recurrence relation:
Where:
– = maximum value using first items with capacity
– = don’t take item
– = take item
Output: 9 (take items at indices 1 and 2: weights 3+4=7, values 4+5=9)
Common Mistakes & Edge Cases
- Off-by-one errors: Carefully handle 0-indexing vs 1-indexing in DP table
- Not initializing base cases: Set
dp[0][*]anddp[*][0]correctly - Using 1D array incorrectly: Must iterate backwards when space-optimizing
- Integer overflow: Use appropriate data types for large values
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Climbing stairs (Fibonacci variant) | LeetCode 70 |
| Medium | Longest Increasing Subsequence | LeetCode 300 |
| Hard | Edit Distance (Levenshtein) | LeetCode 72 |
4. Binary Search
Core Principle
Binary search efficiently finds a target in a sorted array by repeatedly dividing the search space in half. Time complexity: .
When to use binary search:
– Searching in sorted arrays
– Finding boundaries (first/last occurrence)
– Optimization problems (“minimize maximum” or “maximize minimum”)
– Problems with monotonic decision functions
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Halve search space each iteration | |
| Space | Iterative uses constant space |
Python Implementation: Find Insert Position
def binary_search_insert(nums, target):
"""
Find the index to insert target in sorted array.
Args:
nums: sorted list of integers
target: value to search/insert
Returns:
int: index where target is found or should be inserted
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if nums[mid] == target:
return mid # Found exact match
elif nums[mid] < target:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
# If not found, left is the insert position
return left
# Example usage
nums = [1, 3, 5, 6]
print(binary_search_insert(nums, 5)) # Output: 2 (found at index 2)
print(binary_search_insert(nums, 2)) # Output: 1 (insert at index 1)
print(binary_search_insert(nums, 7)) # Output: 4 (insert at end)
Step-by-Step Execution
Input: nums=[1, 3, 5, 6], target=2
| Iteration | left | right | mid | nums[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 3 | 3 > 2, search left |
| 2 | 0 | 0 | 0 | 1 | 1 < 2, search right |
| 3 | 1 | 0 | – | – | left > right, exit |
Output: 1 (insert position between 1 and 3)
Common Mistakes & Edge Cases
- Infinite loop: Use
left <= right(not<) and updatemid ± 1 - Overflow in mid calculation: Use
left + (right - left) // 2instead of(left + right) // 2 - Empty array: Handle
len(nums) == 0 - Duplicate elements: Decide whether to find first or last occurrence
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Search in sorted array | LeetCode 704 |
| Medium | Find peak element | LeetCode 162 |
| Hard | Median of two sorted arrays | LeetCode 4 |
5. Two Pointers
Core Principle
Use two pointers moving towards each other or in the same direction to solve problems in time instead of .
When to use two pointers:
– Finding pairs in sorted arrays
– Removing duplicates in-place
– Reversing arrays/strings
– Sliding window problems
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Each pointer traverses array once | |
| Space | No extra space needed |
Python Implementation: Container With Most Water
Problem: Find two lines that form a container holding the most water.
def max_area(height):
"""
Find maximum water area between two lines.
Args:
height: list of line heights
Returns:
int: maximum area
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# Calculate current area
width = right - left
current_height = min(height[left], height[right])
current_area = width * current_height
# Update maximum
max_water = max(max_water, current_area)
# Move pointer with smaller height (greedy)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
# Example usage
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(height)) # Output: 49 (between indices 1 and 8)
Step-by-Step Execution
Input: height=[1, 8, 6, 2, 5, 4, 8, 3, 7]
| Iteration | left | right | height[left] | height[right] | width | area | max_water | Move |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 1 | 7 | 8 | 8 | 8 | left++ |
| 2 | 1 | 8 | 8 | 7 | 7 | 49 | 49 | right– |
| 3 | 1 | 7 | 8 | 3 | 6 | 18 | 49 | right– |
| … | … | … | … | … | … | … | … | … |
Output: 49 (width=7, height=min(8,7)=7)
Common Mistakes & Edge Cases
- Moving both pointers: Only move one pointer per iteration
- Wrong movement logic: Move the pointer with smaller value to potentially find larger area
- Array with < 2 elements: Handle edge case
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Valid palindrome | LeetCode 125 |
| Medium | 3Sum | LeetCode 15 |
| Hard | Trapping rain water | LeetCode 42 |
6. Sliding Window
Core Principle
Maintain a window that slides through the array/string to solve subarray/substring problems efficiently.
When to use sliding window:
– Finding subarrays with specific properties
– Longest/shortest substring problems
– Problems with contiguous elements
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Each element enters and exits window once | |
| Space | = size of character set (for hash maps) |
Python Implementation: Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
"""
Find length of longest substring without repeating characters.
Args:
s: input string
Returns:
int: length of longest substring
"""
char_index = {} # Map character -> last seen index
max_length = 0
start = 0 # Window start pointer
for end in range(len(s)):
char = s[end]
# If character seen before and within current window
if char in char_index and char_index[char] >= start:
# Move start to right of previous occurrence
start = char_index[char] + 1
# Update character's last seen index
char_index[char] = end
# Update max length
current_length = end - start + 1
max_length = max(max_length, current_length)
return max_length
# Example usage
print(length_of_longest_substring("abcabcbb")) # Output: 3 ("abc")
print(length_of_longest_substring("bbbbb")) # Output: 1 ("b")
print(length_of_longest_substring("pwwkew")) # Output: 3 ("wke")
Step-by-Step Execution
Input: s="abcabcbb"
| end | char | char_index | start | Window | current_length | max_length |
|---|---|---|---|---|---|---|
| 0 | a | {a:0} | 0 | “a” | 1 | 1 |
| 1 | b | {a:0,b:1} | 0 | “ab” | 2 | 2 |
| 2 | c | {a:0,b:1,c:2} | 0 | “abc” | 3 | 3 |
| 3 | a | {a:3,b:1,c:2} | 1 | “bca” | 3 | 3 |
| 4 | b | {a:3,b:4,c:2} | 2 | “cab” | 3 | 3 |
| 5 | c | {a:3,b:4,c:5} | 3 | “abc” | 3 | 3 |
| 6 | b | {a:3,b:6,c:5} | 5 | “cb” | 2 | 3 |
| 7 | b | {a:3,b:7,c:5} | 7 | “b” | 1 | 3 |
Output: 3
Common Mistakes & Edge Cases
- Not updating window correctly: Ensure start pointer moves forward only
- Forgetting to update max: Check max_length every iteration
- Empty string: Return 0
- All unique characters: Max length = string length
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Maximum average subarray | LeetCode 643 |
| Medium | Longest repeating character replacement | LeetCode 424 |
| Hard | Minimum window substring | LeetCode 76 |
7. Fast & Slow Pointers (Floyd’s Algorithm)
Core Principle
Use two pointers moving at different speeds to detect cycles or find middle elements in linked lists.
When to use fast & slow pointers:
– Cycle detection in linked lists
– Finding middle of linked list
– Finding cycle start point
– Happy number problem
Complexity Analysis
| Metric | Complexity | Explanation |
|---|---|---|
| Time | Fast pointer traverses at most 2n nodes | |
| Space | No extra space needed |
Python Implementation: Linked List Cycle Detection
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
"""
Detect if linked list has a cycle using Floyd's algorithm.
Args:
head: head of linked list
Returns:
bool: True if cycle exists, False otherwise
"""
if not head or not head.next:
return False
slow = head # Moves 1 step per iteration
fast = head # Moves 2 steps per iteration
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# If pointers meet, cycle exists
if slow == fast:
return True
return False # Fast pointer reached end, no cycle
# Example usage
# Create cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 # Creates cycle
print(has_cycle(node1)) # Output: True
Step-by-Step Execution
Input: 1 -> 2 -> 3 -> 4 -> 2 (cycle at node 2)
| Iteration | slow | fast | Meet? |
|---|---|---|---|
| 0 | 1 | 1 | No |
| 1 | 2 | 3 | No |
| 2 | 3 | 2 | No |
| 3 | 4 | 4 | No |
| 4 | 2 | 3 | No |
| 5 | 3 | 2 | No |
| 6 | 4 | 4 | Yes |
Output: True (cycle detected)
Finding Cycle Start Point
def detect_cycle_start(head):
"""
Find the node where cycle begins.
Returns:
ListNode: start of cycle, or None if no cycle
"""
# Phase 1: Detect cycle
slow = fast = head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
if not has_cycle:
return None
# Phase 2: Find cycle start
# Reset slow to head, keep fast at meeting point
slow = head
while slow != fast:
slow = slow.next
fast = fast.next # Both move 1 step
return slow # This is the cycle start
Mathematical proof: If cycle starts at distance from head and has length , when pointers meet, moving both pointers 1 step at a time from (head, meeting point) will cause them to meet at cycle start.
Common Mistakes & Edge Cases
- Null pointer errors: Check
fast and fast.nextbefore moving - Empty or single node list: Handle edge cases
- Moving both pointers same speed: Won’t detect cycle
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Middle of linked list | LeetCode 876 |
| Medium | Find duplicate number | LeetCode 287 |
| Hard | Happy number (cycle in sequence) | LeetCode 202 |
8. Backtracking
Core Principle
Explore all possible solutions by incrementally building candidates and abandoning candidates (“backtrack”) as soon as they fail constraints.
When to use backtracking:
– Generating all permutations/combinations
– Sudoku, N-Queens solvers
– Path finding with constraints
– Subset generation
Complexity Analysis
| Problem | Time Complexity | Explanation |
|---|---|---|
| Permutations | permutations, to copy each | |
| Combinations | subsets, to copy each | |
| N-Queens | Pruning reduces from |
Python Implementation: Generate All Subsets
def subsets(nums):
"""
Generate all possible subsets (power set).
Args:
nums: list of unique integers
Returns:
list: all subsets
"""
result = []
def backtrack(start, current):
# Add current subset to result
result.append(current[:])
# Explore further elements
for i in range(start, len(nums)):
# Include nums[i] in current subset
current.append(nums[i])
# Recursively build subsets starting from i+1
backtrack(i + 1, current)
# Backtrack: remove nums[i] to explore other branches
current.pop()
backtrack(0, [])
return result
# Example usage
nums = [1, 2, 3]
print(subsets(nums))
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Step-by-Step Execution Tree
Input: nums=[1,2,3]
[]
/ |
[1] [2] [3]
/ |
[1,2] [1,3] [2,3]
|
[1,2,3]
Backtracking trace:
| Step | current | Action | result |
|---|---|---|---|
| 1 | [] | Add to result | [[]] |
| 2 | [1] | Add 1, recurse | [[],[1]] |
| 3 | [1,2] | Add 2, recurse | [[],[1],[1,2]] |
| 4 | [1,2,3] | Add 3, recurse | [[],[1],[1,2],[1,2,3]] |
| 5 | [1,2] | Backtrack (remove 3) | – |
| 6 | [1] | Backtrack (remove 2) | – |
| 7 | [1,3] | Add 3, recurse | [[],[1],[1,2],[1,2,3],[1,3]] |
| … | … | … | … |
Output: 8 subsets ()
Common Mistakes & Edge Cases
- Not copying current list: Use
current[:]orlist(current)when adding to result - Wrong loop range: Start from
startparameter, not 0 - Forgetting to backtrack: Must remove element after recursion
- Empty input: Returns
[[]]
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Medium | Permutations | LeetCode 46 |
| Medium | Combination Sum | LeetCode 39 |
| Hard | N-Queens | LeetCode 51 |
9. Heap (Priority Queue)
Core Principle
A heap is a binary tree where parent nodes have higher (max-heap) or lower (min-heap) priority than children. Python’s heapq implements min-heap.
When to use heap:
– Finding k-th largest/smallest element
– Merging k sorted lists
– Scheduling problems
– Dijkstra’s shortest path
Complexity Analysis
| Operation | Time Complexity | Explanation |
|---|---|---|
| Insert | Bubble up to maintain heap property | |
| Extract min | Bubble down after removing root | |
| Peek min | Access root element | |
| Heapify | Build heap from array |
Python Implementation: K Closest Points to Origin
import heapq
import math
def k_closest(points, k):
"""
Find k closest points to origin (0, 0).
Args:
points: list of [x, y] coordinates
k: number of closest points to return
Returns:
list: k closest points
"""
# Use max-heap of size k (negate distances for max-heap)
max_heap = []
for x, y in points:
# Calculate squared distance (avoid sqrt for efficiency)
dist = -(x*x + y*y) # Negate for max-heap behavior
if len(max_heap) < k:
# Heap not full, add point
heapq.heappush(max_heap, (dist, [x, y]))
elif dist > max_heap[0][0]:
# Current point closer than farthest in heap
heapq.heapreplace(max_heap, (dist, [x, y]))
# Extract points (discard distances)
return [point for _, point in max_heap]
# Example usage
points = [[1,3], [-2,2], [5,8], [0,1]]
k = 2
result = k_closest(points, k)
print(result) # Output: [[0,1], [-2,2]] or [[-2,2], [0,1]]
Step-by-Step Execution
Input: points=[[1,3], [-2,2], [5,8], [0,1]], k=2
| Step | Point | dist² | max_heap (as max-heap) | Action |
|---|---|---|---|---|
| 1 | [1,3] | 10 | [(-10, [1,3])] | Add (heap size < k) |
| 2 | [-2,2] | 8 | [(-10,[1,3]), (-8,[-2,2])] | Add (heap size < k) |
| 3 | [5,8] | 89 | [(-10,[1,3]), (-8,[-2,2])] | Skip (89 > 10) |
| 4 | [0,1] | 1 | [(-8,[-2,2]), (-1,[0,1])] | Replace max (-10) |
Output: [[0,1], [-2,2]] (closest points with distances 1 and 8)
Common Mistakes & Edge Cases
- Max-heap in Python: Use negative values or custom comparator
- Tie-breaking: Define secondary sort criteria if needed
- K > array length: Handle edge case
- Forgetting to heapify: Use
heapq.heapify(list)for bulk initialization
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Easy | Kth largest element | LeetCode 703 |
| Medium | Top K frequent elements | LeetCode 347 |
| Hard | Merge k sorted lists | LeetCode 23 |
10. Union-Find (Disjoint Set)
Core Principle
Union-Find efficiently manages disjoint sets with two operations:
– Find: Determine which set an element belongs to
– Union: Merge two sets
Optimizations:
– Path compression: Flatten tree during Find
– Union by rank: Attach smaller tree under larger tree
When to use Union-Find:
– Detecting connected components
– Cycle detection in undirected graphs
– Kruskal’s MST algorithm
– Network connectivity
Complexity Analysis
| Operation | Time Complexity | Explanation |
|---|---|---|
| Find | Inverse Ackermann (practically constant) | |
| Union | With path compression + union by rank |
Where is the inverse Ackermann function, which grows extremely slowly (< 5 for all practical ).
Python Implementation: Number of Connected Components
class UnionFind:
def __init__(self, n):
"""
Initialize n disjoint sets.
Args:
n: number of elements (0 to n-1)
"""
self.parent = list(range(n)) # Each node is its own parent initially
self.rank = [0] * n # Tree height for union by rank
self.count = n # Number of disjoint sets
def find(self, x):
"""
Find root of x with path compression.
Args:
x: element to find
Returns:
int: root of x's set
"""
if self.parent[x] != x:
# Path compression: point directly to root
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
Merge sets containing x and y.
Args:
x, y: elements to merge
Returns:
bool: True if sets were merged, False if already in same set
"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Union by rank: attach smaller tree under larger tree
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1 # Decrease number of disjoint sets
return True
def count_components(n, edges):
"""
Count number of connected components in undirected graph.
Args:
n: number of nodes (0 to n-1)
edges: list of [u, v] edges
Returns:
int: number of connected components
"""
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.count
# Example usage
n = 5
edges = [[0,1], [1,2], [3,4]]
result = count_components(n, edges)
print(result) # Output: 2 (components: {0,1,2} and {3,4})
Step-by-Step Execution
Input: n=5, edges=[[0,1], [1,2], [3,4]]
Initial state:
parent: [0, 1, 2, 3, 4]
rank: [0, 0, 0, 0, 0]
count: 5
| Step | Edge | Action | parent | rank | count |
|---|---|---|---|---|---|
| 1 | [0,1] | Union 0 and 1 | [1,1,2,3,4] | [0,1,0,0,0] | 4 |
| 2 | [1,2] | Union 1 and 2 | [1,1,1,3,4] | [0,1,0,0,0] | 3 |
| 3 | [3,4] | Union 3 and 4 | [1,1,1,4,4] | [0,1,0,0,1] | 2 |
Final components:
– Component 1: {0, 1, 2} (root = 1)
– Component 2: {3, 4} (root = 4)
Output: 2
Common Mistakes & Edge Cases
- Not compressing path: Leads to instead of
- Forgetting to update count: Decrement when merging sets
- Single node graph: Returns
ncomponents - Using array index directly: Can cause index errors with non-contiguous node IDs
Problem Variations
| Difficulty | Problem Type | Example |
|---|---|---|
| Medium | Number of provinces | LeetCode 547 |
| Medium | Redundant connection | LeetCode 684 |
| Hard | Accounts merge | LeetCode 721 |
Comparison Summary: When to Use Each Algorithm
| Algorithm | Best For | Time | Space | Key Indicator |
|---|---|---|---|---|
| BFS | Shortest path (unweighted) | “shortest path”, “level-order” | ||
| DFS | All paths, cycle detection | “all solutions”, “connected components” | ||
| DP | Optimization, counting | “maximum”, “minimum”, “count ways” | ||
| Binary Search | Sorted data search | “sorted array”, “find target” | ||
| Two Pointers | Pairs in sorted array | “two sum (sorted)”, “remove duplicates” | ||
| Sliding Window | Subarray/substring | “longest substring”, “maximum subarray” | ||
| Fast & Slow | Cycle detection | “linked list cycle”, “find middle” | ||
| Backtracking | All combinations | “all permutations”, “generate subsets” | ||
| Heap | K-th element, priority | “top k”, “merge k lists” | ||
| Union-Find | Connected components | “connected components”, “network” |
General Problem-Solving Strategy
Step 1: Understand the Problem
- Read carefully and identify inputs, outputs, constraints
- Clarify ambiguities with examples
- Consider edge cases (empty input, single element, duplicates)
Step 2: Pattern Recognition
Look for these keywords:
| Keywords | Likely Algorithm |
|---|---|
| “shortest path”, “minimum steps” | BFS, Dijkstra |
| “all paths”, “all solutions” | DFS, Backtracking |
| “maximum”, “minimum”, “optimize” | DP, Greedy |
| “sorted array” | Binary Search |
| “subarray”, “substring” | Sliding Window, Two Pointers |
| “top k”, “k-th largest” | Heap |
| “connected components” | Union-Find, DFS |
| “all permutations” | Backtracking |
Step 3: Plan Your Approach
- Brute force first: Understand the naive solution
- Identify inefficiencies: Where are redundant computations?
- Choose algorithm: Match pattern to algorithm
- Optimize: Can you reduce time/space complexity?
Step 4: Implement & Test
- Write clean, commented code
- Test with examples (include edge cases)
- Analyze complexity
- Debug systematically
Step 5: Practice by Difficulty
Easy (Foundation building):
– Focus on understanding core concepts
– Implement algorithms from scratch
– Solve 2-3 problems per algorithm
Medium (Pattern recognition):
– Identify which algorithm to use
– Handle multiple edge cases
– Optimize initial solutions
Hard (Combining techniques):
– Combine multiple algorithms (e.g., BFS + DP)
– Handle complex constraints
– Optimize for both time and space
Common Pitfalls Across All Algorithms
1. Off-by-One Errors
- Array indexing: Remember Python uses 0-based indexing
- Loop ranges: Use
range(len(arr))orrange(start, end+1)carefully - Boundary conditions: Test first and last elements
2. Integer Overflow (Less common in Python)
- Python handles arbitrary precision, but be aware in other languages
- Use modulo for large number problems
3. Edge Cases Checklist
- Empty input (
[],"",None) - Single element
- All elements identical
- Negative numbers (if applicable)
- Maximum/minimum constraints
4. Time Limit Exceeded (TLE)
- Analyze complexity: Is your solution efficient enough?
- Optimize: Can you reduce from to ?
- Avoid redundant work: Use memoization, early termination
5. Space Optimization
- In-place algorithms: Modify input array instead of creating new one
- Rolling arrays: DP with only last row/column
- Constant space: Two pointers instead of hash map
Practice Resources
Online Judges
- LeetCode: Most popular, great for interviews
- HackerRank: Structured learning paths
- CodeForces: Competitive programming
- AtCoder: Beginner-friendly contests
Study Plans
Week 1-2: Foundations
– Arrays, strings, hash maps
– Two pointers, sliding window
– Binary search
Week 3-4: Trees & Graphs
– BFS, DFS
– Binary trees (traversal, BST)
– Graph basics
Week 5-6: Advanced
– Dynamic programming (1D, 2D)
– Backtracking
– Heap, Union-Find
Week 7-8: Practice & Mock Interviews
– Solve 2-3 problems daily
– Simulate interview conditions (45 min per problem)
– Review solutions and alternatives
Conclusion
Mastering these 10 algorithms will prepare you for 80% of coding interview questions:
- BFS – Shortest paths in unweighted graphs
- DFS – Exploring all solutions and detecting cycles
- Dynamic Programming – Optimizing overlapping subproblems
- Binary Search – Efficiently searching sorted data
- Two Pointers – Optimizing pair-finding problems
- Sliding Window – Solving subarray/substring efficiently
- Fast & Slow Pointers – Cycle detection in linked lists
- Backtracking – Generating all combinations/permutations
- Heap – Managing priority and k-th element problems
- Union-Find – Tracking connected components
Key Takeaways:
– Understand principles before memorizing code
– Analyze complexity for every solution
– Practice pattern recognition to identify which algorithm to use
– Master edge cases to write robust code
– Optimize iteratively: Brute force → Optimized → Space-optimized
Consistent practice is the key to success. Start with easy problems to build confidence, then progressively tackle medium and hard problems. Focus on understanding why an algorithm works, not just how to implement it.
Good luck with your coding interviews! Remember, every expert was once a beginner – keep practicing, and you’ll get there.
Did you find this helpful?
Your support keeps this blog running and ad-free content coming.
☕ Buy me a coffeeMost Popular Posts
- Custom Metaclass in Python: 43% Faster Validation (12,923 views)
- Python match-case: 7 Patterns That Beat if-elif Chains (974 views)
- yfinance Alternatives 2026: 7 Free APIs Compared (973 views)
- YOLOv8 INT8 Quantization: 4x Faster on Jetson Orin (863 views)
- PaddleOCR vs EasyOCR vs Tesseract: Why PaddleOCR Is Slower (671 views)