🧠 Algorithm Code Patterns & Implementations

Status: Comprehensive technical interview preparation resource with 700+ implementations - actively maintained study guide for algorithm mastery.

A comprehensive repository to help you master algorithm patterns, build intuition, and ace technical interviews.
Includes pattern reference guide, Python implementations, tests, and study resources.

🚀 Quick Start

# Clone the repository
git clone https://github.com/yourusername/algos.git
cd algos

# Run setup script
chmod +x setup.sh
./setup.sh

# Or manually:
python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
pytest tests/

📁 Repository Structure

algos/
├── implementations/        # Algorithm implementations by pattern
│   ├── hash_map.py        # O(1) lookups, counting
│   ├── two_pointers.py    # Sorted arrays, palindromes
│   ├── sliding_window.py  # Substrings, subarrays
│   ├── binary_search.py   # Search, optimization
│   ├── dfs_backtracking.py # All possibilities
│   ├── bfs.py             # Level-order, shortest paths
│   ├── dynamic_programming.py # Optimal substructure
│   ├── graphs.py          # DFS, BFS, Union-Find, Dijkstra
│   └── heaps.py           # Priority queues, top-k
├── tests/                 # Comprehensive test suite
├── examples.py            # Runnable examples
├── README.md              # This file (pattern cheat sheet)
├── CONTRIBUTING.md        # Contribution guidelines
├── STUDY_GUIDE.md         # Structured study plan
└── requirements.txt       # Dependencies

🎯 Features

✅ 100+ Algorithm Implementations - Production-ready code with tests
✅ Comprehensive Documentation - Docstrings with complexity analysis
✅ Full Test Coverage - Pytest suite with edge cases
✅ Pattern-Based Organization - Learn by algorithm patterns
✅ Study Guide - 8-week structured learning plan
✅ Examples - Runnable demonstrations of each pattern

🧪 Running Tests

# All tests
pytest tests/

# Specific pattern
pytest tests/test_hash_map.py

# With coverage
pytest --cov=implementations tests/

# Verbose output
pytest -v tests/

# Run doctests
python -m doctest implementations/hash_map.py

💡 Usage Examples

from implementations.hash_map import two_sum
from implementations.sliding_window import length_of_longest_substring
from implementations.graphs import UnionFind

# Hash Map Pattern
result = two_sum([2, 7, 11, 15], 9)
print(result)  # [0, 1]

# Sliding Window Pattern
length = length_of_longest_substring("abcabcbb")
print(length)  # 3

# Graph Pattern
uf = UnionFind(5)
uf.union(0, 1)
print(uf.connected(0, 1))  # True

Or run all examples:

python examples.py

📚 Documentation

• Pattern Cheat Sheet - Quick reference (below)
• COMPLEXITY_CHART.md - Comprehensive complexity analysis for all algorithms
• QUICK_REFERENCE.md - Printable interview reference card
• CONTRIBUTING.md - How to contribute
• STUDY_GUIDE.md - 8-week study plan with tips

🎓 Learning Resources

For Interview Prep

1. Start with STUDY_GUIDE.md for structured plan
2. Review pattern cheat sheet below
3. Implement algorithms from implementations/
4. Practice with similar problems on LeetCode
5. Run python examples.py to see patterns in action

For Contributors

1. Read CONTRIBUTING.md
2. Choose a pattern to implement
3. Add tests to tests/
4. Submit a pull request

---

📋 Pattern Cheat Sheet

---

📋 Table of Contents

1. Hash Map / Dictionary
2. Two Pointers
3. Sliding Window
4. Prefix Sum / Cumulative Count
5. Binary Search
6. Depth-First Search (DFS) & Backtracking
7. Breadth-First Search (BFS)
8. Dynamic Programming (DP)
9. Greedy Algorithms
10. Sorting & Searching Patterns
11. Heap / Priority Queue
12. Graph Patterns
13. Common Complexities Reference
14. Interview Strategy

---

1. Hash Map / Dictionary

Pattern: Fast lookups, counting, and complements.
When to Use: When you need O(1) access to previously seen data.

Examples:

• Two Sum
• Valid Anagram
• Subarray Sum Equals K

# Two Sum
d = {}
for i, n in enumerate(nums):
    if target - n in d:
        return [d[target - n], i]
    d[n] = i

Common Variants:

• Count elements: Counter(nums)
• Track frequency or index
• Prefix-sum to detect subarrays

Complexity:

Operation	Time	Space
Insert / Lookup	O(1)	O(n)

---

2. Two Pointers

Pattern: Use two indices moving inward or outward. When to Use: Sorted arrays, linked lists, or string comparisons.

Examples:

• Sorted Two Sum
• Container With Most Water
• Palindrome Check
• Remove Duplicates

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

Variations:

• Fast/slow pointers for cycle detection
• Move both pointers conditionally

Complexity:

Operation	Time	Space
Traverse once	O(n)	O(1)

---

3. Sliding Window

Pattern: Dynamic window that expands/contracts. When to Use: Substrings, subarrays, or fixed-size segment problems.

Examples:

• Longest substring without repeating chars
• Max sum subarray of size k
• Minimum window substring

window, l, best = {}, 0, 0
for r, c in enumerate(s):
    window[c] = window.get(c, 0) + 1
    while window[c] > 1:
        window[s[l]] -= 1
        l += 1
    best = max(best, r - l + 1)

Types:

• Fixed-size window
• Variable-size window (expand & shrink)

Complexity:

Operation	Time	Space
Move window	O(n)	O(k)

---

4. Prefix Sum / Cumulative Count

Pattern: Store cumulative results to answer range queries fast. When to Use: Subarray sums, range differences, balance tracking.

Examples:

• Subarray sum equals K
• Range sum queries
• Balance parentheses

prefix = {0: 1}
s = res = 0
for n in nums:
    s += n
    res += prefix.get(s - k, 0)
    prefix[s] = prefix.get(s, 0) + 1

Complexity:

Operation	Time	Space
Build prefix	O(n)	O(n)

---

5. Binary Search

Pattern: Divide and conquer to find an element or condition boundary. When to Use: Sorted data, search conditions, or monotonic functions.

Examples:

• Search in Rotated Array
• Find minimum in rotated array
• Square root, Peak element

l, r = 0, len(nums) - 1
while l <= r:
    m = (l + r) // 2
    if nums[m] == target: return m
    if nums[m] < target: l = m + 1
    else: r = m - 1

Binary Search on Answer: Used for optimization problems (“minimum X such that…”).

Complexity:

Operation	Time	Space
Search	O(log n)	O(1)

---

6. Depth-First Search (DFS) & Backtracking

Pattern: Explore all possibilities (tree, grid, graph, recursion). When to Use: All subsets, permutations, paths, or decision trees.

Examples:

• Subsets / Permutations
• N-Queens
• Word Search

def dfs(i, path):
    if i == len(nums):
        res.append(path[:])
        return
    dfs(i + 1, path + [nums[i]])
    dfs(i + 1, path)

Backtracking Tip: Undo changes before returning from recursion.

Complexity:

Operation	Time	Space
Explore all	O(2ⁿ)	O(n)

---

7. Breadth-First Search (BFS)

Pattern: Level-by-level traversal using a queue. When to Use: Shortest path, level order, connected components.

Examples:

• Binary Tree Level Order
• Word Ladder
• Shortest Path in Grid

from collections import deque
q = deque([start])
seen = {start}
while q:
    node = q.popleft()
    for nei in graph[node]:
        if nei not in seen:
            seen.add(nei)
            q.append(nei)

Complexity:

Operation	Time	Space
Visit all	O(V + E)	O(V)

---

8. Dynamic Programming (DP)

Pattern: Break problem into overlapping subproblems. When to Use: Optimal decisions, counting, or sequences.

Examples:

• Fibonacci, Climbing Stairs
• Knapsack, Coin Change
• Longest Increasing Subsequence

dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]

Tips:

• Top-down: Memoization (recursive)
• Bottom-up: Tabulation (iterative)

Complexity:

Operation	Time	Space
DP solution	O(n)	O(n) (→ O(1) optimized)

---

9. Greedy Algorithms

Pattern: Always choose best local decision hoping for global optimum. When to Use: Scheduling, intervals, simple optimization.

Examples:

• Activity selection
• Jump Game
• Minimum coins

intervals.sort(key=lambda x: x[1])
end, count = float('-inf'), 0
for s, e in intervals:
    if s >= end:
        count += 1
        end = e

Complexity:

Operation	Time	Space
Sort + Iterate	O(n log n)	O(1)

---

10. Sorting & Searching Patterns

Common Uses:

• Preprocess data for two-pointer or greedy
• Merge intervals
• Binary search usage

nums.sort()

Algorithm	Average	Worst	Space	Stable
QuickSort	O(n log n)	O(n²)	O(log n)	❌
MergeSort	O(n log n)	O(n log n)	O(n)	✅
HeapSort	O(n log n)	O(n log n)	O(1)	❌
TimSort (Python sort())	O(n log n)	O(n log n)	O(n)	✅

---

11. Heap / Priority Queue

Pattern: Extract min/max efficiently. When to Use: Top-k problems, running median, Dijkstra’s.

Examples:

• Kth largest element
• Merge k sorted lists
• Task scheduling

import heapq
heap = []
for x in nums:
    heapq.heappush(heap, x)
    if len(heap) > k: heapq.heappop(heap)

Complexity:

Operation	Time	Space
Push/Pop	O(log n)	O(n)

---

12. Graph Patterns

Representation:

graph = {u: [] for u in range(n)}
for u, v in edges:
    graph[u].append(v)

Traversals:

• DFS (recursive or stack)
• BFS (queue)
• Topological sort (Kahn’s algorithm)
• Union-Find (for connected components)

Complexity:

Operation	Time	Space
DFS/BFS	O(V + E)	O(V + E)
Union-Find	O(α(n)) per op	O(n)

---

13. Common Complexities Reference

Quick Complexity Overview

Operation / Pattern	Time Complexity	Space
Single Loop	O(n)	O(1)
Nested Loops	O(n²)	O(1)
Sorting	O(n log n)	O(1)
Binary Search	O(log n)	O(1)
DFS / BFS	O(V + E)	O(V)
Dynamic Programming	O(n) – O(n²)	O(n)
Backtracking	O(2ⁿ)	O(n)
Matrix Traversal	O(m × n)	O(1)

Complexity Growth Visualization

Operations as input size (n) grows:

O(