DSA Cheatsheet - Interactive Quick Reference

🤔 Why You Need This Cheatsheet

💼

Interview Prep

Quick review before technical interviews

🏃

Fast Lookup

Find complexity and syntax in seconds

🎯

Pattern Recognition

Identify the right approach quickly

🏗️

Data Structures

Arrays, Trees, Graphs...

⚡

Algorithms

Sorting, Searching, DP...

📊

Big O Analysis

Time & Space Complexity

🎨

Common Patterns

Two Pointers, Sliding Window...

🏗️ Data Structures Quick Reference

📊 Arrays & Lists

Time Complexity

Operation	Time	Plain English
Access by index	O(1)	⚡ Instant - like page number
Search	O(n)	🐌 Check every item
Insert at end	O(1)	⚡ Just add to end
Insert at beginning	O(n)	🐌 Shift everything
Delete	O(n)	🐌 Shift elements

# Python Array/List Operations
arr = [1, 2, 3, 4, 5]

# Access - O(1)
value = arr[2]  # Gets 3

# Insert - O(n) at beginning, O(1) at end
arr.append(6)     # Fast! Add to end
arr.insert(0, 0)  # Slow! Shift all

# Search - O(n)
if 3 in arr:
    index = arr.index(3)

🔗 Linked Lists

Time Complexity

Operation	Time	Plain English
Access by index	O(n)	🐌 Walk through list
Search	O(n)	🐌 Check each node
Insert at head	O(1)	⚡ Just update pointer
Insert at tail	O(n)	🐌 Find tail first
Delete	O(n)	🚶 Find then remove

# Simple Linked List Node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Insert at head - O(1)
new_node = Node(5)
new_node.next = head
head = new_node

📚 Stack (LIFO)

Time Complexity

Operation	Time	Plain English
Push (add)	O(1)	⚡ Add to top
Pop (remove)	O(1)	⚡ Remove from top
Peek (top)	O(1)	⚡ Look at top
Search	O(n)	🐌 Not meant for this

# Stack using Python list
stack = []

# Push - O(1)
stack.append(1)
stack.append(2)

# Pop - O(1)
top = stack.pop()  # Returns 2

# Peek - O(1)
if stack:
    top = stack[-1]

🎫 Queue (FIFO)

Time Complexity

Operation	Time	Plain English
Enqueue (add)	O(1)	⚡ Add to back
Dequeue (remove)	O(1)*	⚡ Remove from front
Front	O(1)	⚡ Look at front
Search	O(n)	🐌 Not meant for this

from collections import deque

# Efficient queue using deque
queue = deque()

# Enqueue - O(1)
queue.append(1)
queue.append(2)

# Dequeue - O(1)
front = queue.popleft()  # Returns 1

🌲 Binary Search Tree

Time Complexity

Operation	Average	Worst	Plain English
Search	O(log n)	O(n)	🏃 Cut in half each time
Insert	O(log n)	O(n)	🏃 Find spot & insert
Delete	O(log n)	O(n)	🏃 Find & reconnect
Min/Max	O(log n)	O(n)	🏃 Go all left/right

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

# BST Search - O(log n) average
def search(root, target):
    if not root:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)

#️⃣ Hash Table

Time Complexity

Operation	Average	Worst	Plain English
Insert	O(1)	O(n)	⚡ Direct placement
Delete	O(1)	O(n)	⚡ Direct removal
Search	O(1)	O(n)	⚡ Direct lookup
Space	O(n)		📦 Store all items

# Python dictionary (hash table)
hash_map = {}

# Insert - O(1) average
hash_map["key"] = "value"

# Search - O(1) average
if "key" in hash_map:
    value = hash_map["key"]

# Delete - O(1) average
del hash_map["key"]

⚡ Algorithms Quick Reference

🔄 Sorting Algorithms

Comparison

Algorithm	Best	Average	Worst	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)

# Quick Sort - O(n log n) average
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quicksort(left) + middle + quicksort(right)

🔍 Searching Algorithms

Comparison

Algorithm	Time	Requirement
Linear Search	O(n)	None
Binary Search	O(log n)	Sorted array
Jump Search	O(√n)	Sorted array
Hash Table	O(1)	Extra space

# Binary Search - O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Not found

🕸️ Graph Algorithms

Common Algorithms

Algorithm	Time	Space	Use Case
DFS	O(V + E)	O(V)	Path finding, cycles
BFS	O(V + E)	O(V)	Shortest path (unweighted)
Dijkstra	O(E log V)	O(V)	Shortest path (weighted)
Bellman-Ford	O(VE)	O(V)	Negative weights

# BFS - O(V + E)
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

💎 Dynamic Programming

Common Problems

Problem	Time	Space
Fibonacci	O(n)	O(1)
0/1 Knapsack	O(nW)	O(nW)
Longest Common Subsequence	O(mn)	O(mn)
Edit Distance	O(mn)	O(mn)

# Fibonacci with DP - O(n) time, O(1) space
def fibonacci(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

🎨 Common Algorithm Patterns

👥 Two Pointers

When to Use

Sorted arrays Find pairs with target sum
Palindromes Check from both ends
Remove duplicates In-place operations
Container problems Max water, areas

# Two Sum in Sorted Array - O(n)
def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need bigger sum
        else:
            right -= 1  # Need smaller sum
    
    return []

🪟 Sliding Window

When to Use

Subarray/Substring Contiguous elements
Fixed size window K elements
Variable size Min/max conditions
String patterns Anagrams, permutations

# Max Sum Subarray of Size K - O(n)
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        # Slide window: remove left, add right
        window_sum = window_sum - arr[i-k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

🐢🐇 Fast & Slow Pointers

When to Use

Cycle detection Linked list cycles
Middle element Find middle of list
Happy number Cycle problems
Palindrome List palindrome

# Detect Cycle in Linked List - O(n)
def has_cycle(head):
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next        # Move 1 step
        fast = fast.next.next    # Move 2 steps
        
        if slow == fast:
            return True  # Cycle found!
    
    return False

🌲 Tree Traversal Patterns

Types

DFS Preorder Root → Left → Right
DFS Inorder Left → Root → Right
DFS Postorder Left → Right → Root
BFS Level Order Level by level

# Inorder Traversal (Recursive) - O(n)
def inorder(root):
    result = []
    
    def traverse(node):
        if not node:
            return
        
        traverse(node.left)     # Left
        result.append(node.val)  # Root
        traverse(node.right)     # Right
    
    traverse(root)
    return result

⏪ Backtracking

When to Use

Permutations All arrangements
Combinations All selections
Subsets Power set
N-Queens Constraint problems

# Generate All Subsets - O(2^n)
def subsets(nums):
    result = []
    
    def backtrack(start, path):
        result.append(path[:])  # Add current subset
        
        for i in range(start, len(nums)):
            path.append(nums[i])      # Choose
            backtrack(i + 1, path)    # Explore
            path.pop()                # Un-choose
    
    backtrack(0, [])
    return result

🎯 Binary Search Variations

Common Variations

First occurrence Leftmost position
Last occurrence Rightmost position
Search in rotated Modified binary search
Search insert position Where to insert

# Find First Occurrence - O(log n)
def first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

📊 Big O Complexity Guide

🎮 Complexity Calculator

Enter input size to see how different complexities scale:

📈 Common Time Complexities

Complexity	Name	Example	Plain English
O(1)	Constant	Array access	⚡ Always same time
O(log n)	Logarithmic	Binary search	🏃 Cut in half each time
O(n)	Linear	Loop through array	🚶 Check each item once
O(n log n)	Linearithmic	Merge sort	🏃 Divide & process
O(n²)	Quadratic	Nested loops	🐌 Compare all pairs
O(2ⁿ)	Exponential	All subsets	💀 Doubles each time

🧮 How to Calculate Big O

Rules

Drop Constants O(2n) → O(n)
Drop Lower Terms O(n² + n) → O(n²)
Different Inputs O(a + b) not O(n)
Nested Loops Multiply complexities

# Example: O(n²)
for i in range(n):        # O(n)
    for j in range(n):    # O(n)
        print(i, j)         # O(1)
# Total: O(n) × O(n) × O(1) = O(n²)

# Example: O(n)
for i in range(n):        # O(n)
    print(i)                # O(1)
for j in range(n):        # O(n)
    print(j)                # O(1)
# Total: O(n) + O(n) = O(2n) = O(n)

💾 Space Complexity

Data Structure	Space	Example
Variables	O(1)	int, float, bool
Array/List	O(n)	Store n elements
2D Array	O(n×m)	Matrix storage
Recursion	O(depth)	Call stack

⚠️ Common Mistake

Forgetting recursion stack space! Each recursive call uses O(1) stack space.

💪 Practice Problems

🎮 Try It: Two Sum Problem

Find two numbers that add up to the target!

🎯 Top Interview Questions

Arrays & Strings

Two Sum Hash table approach
Valid Palindrome Two pointers
Best Time to Buy Stock Track min/max
Merge Intervals Sort and merge

Trees & Graphs

Max Depth DFS/BFS
Valid BST Inorder traversal
Number of Islands DFS/BFS
Clone Graph HashMap + DFS

💡 Interview Tips

Problem Solving Steps

1. Understand Ask clarifying questions
2. Examples Work through examples
3. Approach Explain your solution
4. Code Write clean code
5. Test Check edge cases
6. Optimize Improve if possible

✅ Always Remember

Think out loud
Start with brute force
Consider edge cases
Analyze complexity