DSA Cheat Sheet: Quick Reference for Data Structures & Algorithms

Arrays & Strings

Time Complexities

*Amortized O(1) for ArrayList/dynamic arrays due to occasional resizing.

Essential Patterns

Two Pointers (Sorted Array):

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return new int[]{left, right};
    else if (sum < target) left++;
    else right--;
}

Sliding Window (Fixed Size):

int windowSum = 0, maxSum = 0;
for (int i = 0; i < n; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
}

Sliding Window (Variable Size):

int left = 0, windowSum = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    windowSum += arr[right];
    while (windowSum > target) {
        windowSum -= arr[left];
        left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
}

Fast & Slow Pointers (Cycle Detection):

int slow = 0, fast = 0;
do {
    slow = arr[slow];          // move 1 step
    fast = arr[arr[fast]];     // move 2 steps
} while (slow != fast);
// Cycle exists; find entry point
slow = 0;
while (slow != fast) {
    slow = arr[slow];
    fast = arr[fast];
}
return slow; // cycle entry

Prefix Sum:

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// Range sum [l, r] = prefix[r+1] - prefix[l]

Hash Maps

Operations

Pattern: Two Sum

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) {
        return new int[]{map.get(complement), i};
    }
    map.put(nums[i], i);
}

Pattern: Frequency Count

Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
    freq.merge(num, 1, Integer::sum);
}
// Find elements appearing more than n/2 times
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    if (e.getValue() > nums.length / 2) return e.getKey();
}

Trees

Traversals

// Inorder: Left -> Root -> Right (sorted for BST)
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.println(node.val);
    inorder(node.right);
}

// Preorder: Root -> Left -> Right (clone tree)
// Postorder: Left -> Right -> Root (delete tree)
// Level Order: BFS with Queue (level-by-level)

BST Operations

Tree Height & Depth

// Max depth (recursive)
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Min depth (BFS stops at first leaf)
int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 1;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) return depth;
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        depth++;
    }
    return depth;
}

Graphs

BFS Template

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // process node
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

DFS Template

void dfs(TreeNode node) {
    if (node == null) return;
    // process node
    dfs(node.left);
    dfs(node.right);
}

Graph BFS (Adjacency List)

void bfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Topological Sort (Kahn's Algorithm)

List<Integer> topologicalSort(List<List<Integer>> adj, int n) {
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++)
        for (int j : adj.get(i)) inDegree[j]++;
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) queue.offer(i);
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : adj.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return result.size() == n ? result : new ArrayList<>(); // empty if cycle
}

Union-Find (Disjoint Set)

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
    }
}

Graph Complexity Summary

Sorting Algorithms

When to Use Which

• Quick Sort: Default choice, fastest in practice, cache-friendly.
• Merge Sort: When stable sort is needed or data is linked/external.
• Heap Sort: When O(1) space and O(n log n) guarantee is needed.
• Counting Sort: When range of values k is small relative to n.
• Radix Sort: When sorting integers with known digit count.
• Insertion Sort: When n is very small (< 20) or data is nearly sorted.
• Tim Sort (Java's Arrays.sort for objects): Hybrid of merge and insertion, stable.

Dynamic Programming

Memoization Template (Top-Down)

Map<Integer, Integer> memo = new HashMap<>();
int solve(int n) {
    if (n == 0) return baseCase;
    if (memo.containsKey(n)) return memo.get(n);
    int result = // recurrence using solve(n-1), solve(n-2), etc.
    memo.put(n, result);
    return result;
}

Tabulation Template (Bottom-Up)

int[] dp = new int[n + 1];
dp[0] = baseCase;
for (int i = 1; i <= n; i++) {
    dp[i] = // recurrence using dp[i-1], dp[i-2], etc.
}
return dp[n];

2D DP Template

int[][] dp = new int[m + 1][n + 1];
dp[0][0] = baseCase;
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        dp[i][j] = // recurrence using dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
    }
}
return dp[m][n];

Classic Problems

DP Pattern Recognition Guide

• Linear DP: Problem depends on previous 1-2 states (Fibonacci, climbing stairs, house robber).
• 2D Grid DP: Navigate grid, choose paths (unique paths, min path sum).
• Knapsack variants: 0/1 (each item once), unbounded (repeat), multiple (limited copies).
• Interval DP: Optimal way to merge/parenthesize (matrix chain, burst balloons).
• String DP: Subsequence/substring problems (LCS, edit distance, palindrome).
• Bitmask DP: Small n (<= 20), subset enumeration (TSP, assignment).

Binary Search

Standard Template

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Leftmost (First Occurrence)

int leftBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            if (arr[mid] == target) result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

Rightmost (Last Occurrence)

int rightBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            if (arr[mid] == target) result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Search in Rotated Sorted Array

int searchRotated(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[left] <= arr[mid]) { // left half sorted
            if (target >= arr[left] && target < arr[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // right half sorted
            if (target > arr[mid] && target <= arr[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Binary Search on Answer

// Find minimum value that satisfies condition
int lo = minVal, hi = maxVal;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (isSatisfied(mid)) hi = mid;
    else lo = mid + 1;
}
return lo;

Binary Search Complexity Summary

Quick Reference

Data Structure Comparison

Stack & Queue Templates

// Monotonic Stack (Next Greater Element)
int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = arr.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= arr[i]) stack.pop();
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return result;
}

// LRU Cache using LinkedHashMap
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>(capacity, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
};

Heap / Priority Queue

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Custom comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

String Operations

Common Interview Shortcuts

Resources

• DSA Roadmap - Complete learning path
• Practice Problems - Practice problems
• Topic Deep Dives - Detailed explanations
• Coding Patterns - 15 essential patterns
• DSA Guide - Full reference