Top 10 Python Interview Algorithms: BFS to DP

Updated Feb 14, 2026
Disclosure: As an Amazon Associate, I earn from qualifying purchases. Some links in this post are affiliate links — they cost you nothing extra.

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 O(V+E)O(V + E) Visit each vertex once and explore all edges
Space O(V)O(V) Queue can hold up to all vertices in worst case

Where VV = number of vertices, EE = 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 end is 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

Enjoying this article? Get more like it delivered to your inbox. Subscribe to the newsletter

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 O(V+E)O(V + E) Visit each vertex once and explore all edges
Space O(V)O(V) 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 of path.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:

  1. Top-down (Memoization): Recursive with caching
  2. 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 O(2n)O(2^n) O(n)O(n) Exponential due to redundant calls
Memoization O(n)O(n) O(n)O(n) Each subproblem solved once
Tabulation O(n)O(n) O(n)O(n) Iterative with table
Space-optimized O(n)O(n) O(1)O(1) 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 WW.

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:

<br/>dp[i][w]=max⁡(dp[i−1][w],  dp[i−1][w−weights[i−1]]+values[i−1])<br/><br /> dp[i][w] = max(dp[i-1][w], ; dp[i-1][w – weights[i-1]] + values[i-1])<br />

Where:
– dp[i][w]dp[i][w] = maximum value using first ii items with capacity ww
– dp[i−1][w]dp[i-1][w] = don’t take item i−1i-1
– dp[i−1][w−weights[i−1]]+values[i−1]dp[i-1][w – weights[i-1]] + values[i-1] = take item i−1i-1

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][*] and dp[*][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

Core Principle

Binary search efficiently finds a target in a sorted array by repeatedly dividing the search space in half. Time complexity: O(log⁡n)O(log n).

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 O(log⁡n)O(log n) Halve search space each iteration
Space O(1)O(1) 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 update mid ± 1
  • Overflow in mid calculation: Use left + (right - left) // 2 instead 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 O(n)O(n) time instead of O(n2)O(n^2).

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 O(n)O(n) Each pointer traverses array once
Space O(1)O(1) 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 O(n)O(n) Each element enters and exits window once
Space O(k)O(k) kk = 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 O(n)O(n) Fast pointer traverses at most 2n nodes
Space O(1)O(1) 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 μmu from head and has length λlambda, 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.next before 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 O(n!⋅n)O(n! cdot n) n!n! permutations, O(n)O(n) to copy each
Combinations O(2n⋅n)O(2^n cdot n) 2n2^n subsets, O(n)O(n) to copy each
N-Queens O(n!)O(n!) Pruning reduces from nnn^n

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 (232^3)

Common Mistakes & Edge Cases

  • Not copying current list: Use current[:] or list(current) when adding to result
  • Wrong loop range: Start from start parameter, 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 O(log⁡n)O(log n) Bubble up to maintain heap property
Extract min O(log⁡n)O(log n) Bubble down after removing root
Peek min O(1)O(1) Access root element
Heapify O(n)O(n) 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 O(α(n))O(alpha(n)) Inverse Ackermann (practically constant)
Union O(α(n))O(alpha(n)) With path compression + union by rank

Where α(n)alpha(n) is the inverse Ackermann function, which grows extremely slowly (< 5 for all practical nn).

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 O(n)O(n) instead of O(α(n))O(alpha(n))
  • Forgetting to update count: Decrement when merging sets
  • Single node graph: Returns n components
  • 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) O(V+E)O(V+E) O(V)O(V) “shortest path”, “level-order”
DFS All paths, cycle detection O(V+E)O(V+E) O(V)O(V) “all solutions”, “connected components”
DP Optimization, counting O(n⋅m)O(n cdot m) O(n⋅m)O(n cdot m) “maximum”, “minimum”, “count ways”
Binary Search Sorted data search O(log⁡n)O(log n) O(1)O(1) “sorted array”, “find target”
Two Pointers Pairs in sorted array O(n)O(n) O(1)O(1) “two sum (sorted)”, “remove duplicates”
Sliding Window Subarray/substring O(n)O(n) O(k)O(k) “longest substring”, “maximum subarray”
Fast & Slow Cycle detection O(n)O(n) O(1)O(1) “linked list cycle”, “find middle”
Backtracking All combinations O(2n)O(2^n) O(n)O(n) “all permutations”, “generate subsets”
Heap K-th element, priority O(nlog⁡k)O(n log k) O(k)O(k) “top k”, “merge k lists”
Union-Find Connected components O(α(n))O(alpha(n)) O(n)O(n) “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

  1. Brute force first: Understand the naive solution
  2. Identify inefficiencies: Where are redundant computations?
  3. Choose algorithm: Match pattern to algorithm
  4. 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)) or range(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 O(n2)O(n^2) to O(nlog⁡n)O(n log n)?
  • 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:

  1. BFS – Shortest paths in unweighted graphs
  2. DFS – Exploring all solutions and detecting cycles
  3. Dynamic Programming – Optimizing overlapping subproblems
  4. Binary Search – Efficiently searching sorted data
  5. Two Pointers – Optimizing pair-finding problems
  6. Sliding Window – Solving subarray/substring efficiently
  7. Fast & Slow Pointers – Cycle detection in linked lists
  8. Backtracking – Generating all combinations/permutations
  9. Heap – Managing priority and k-th element problems
  10. 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 coffee
TODAY 1,280 | TOTAL 141,115