DSA Cheatsheet - Interactive Quick Reference

Why You Need This Cheatsheet

Your go-to quick reference for DSA

Whether you're prepping for interviews, doing a fast lookup, or trying to identify the right pattern, this cheatsheet has you covered.

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

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

array_operations.py

# 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

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

linked_list.py

# 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)

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.py

# 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)

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

queue.py

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

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

bst.py

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

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

hash_table.py

# 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

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)

quicksort.py

# 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

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.py

# 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

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.py

# 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

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_dp.py

# 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_pointers.py

# 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

sliding_window.py

# 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

cycle_detection.py

# 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

tree_traversal.py

# 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

backtracking.py

# 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

first_occurrence.py

# 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

big_o_examples.py

# 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) x O(n) x 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!

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

Why You Need This Cheatsheet

Your go-to quick reference for DSA

Interview Prep

Fast Lookup

Pattern Recognition

Data Structures

Algorithms

Big O Analysis

Common Patterns

Data Structures Quick Reference

Arrays & Lists

Linked Lists

Stack (LIFO)

Queue (FIFO)

Binary Search Tree

Hash Table

Algorithms Quick Reference

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Dynamic Programming

Common Algorithm Patterns

Two Pointers

Sliding Window

Fast & Slow Pointers

Tree Traversal Patterns

Backtracking

Binary Search Variations

Big O Complexity Guide

Complexity Calculator

Common Time Complexities

How to Calculate Big O

Space Complexity

Common Mistake

Practice Problems

Try It: Two Sum Problem

Top Interview Questions

Arrays & Strings

Trees & Graphs

Interview Tips

Problem Solving Steps

Always Remember

Related Topics