DSA Problem Templates Cheatsheet

REFERENCE v1.0

DSA Problem Templates

Everything you need to solve algorithmic problems – patterns, code, and approach.

Problem‑Solving Framework

Step 1: Understand the Problem

Read the problem carefully (twice)
Identify input and output
Note constraints (n, time, space)
Clarify edge cases
Ask clarifying questions

Step 2: Explore Solutions

Think of brute force first
Identify patterns (sliding window, two pointers)
Consider data structures
Time vs space trade‑offs
Optimise step by step

Step 3: Implement

Write clean, readable code
Use meaningful variable names
Add comments for complex logic
Follow language conventions

Step 4: Test

Test with sample input
Test edge cases (empty, single, extreme)
Test with large input (mentally)
Dry run with examples

Common Problem Patterns

1. Two Pointers

Use: sorted arrays, palindrome, subarrays
Time: O(n)
Space: O(1)

// Opposite direction
function twoSum(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return [];
}

// Same direction (fast & slow)
function removeDuplicates(arr) {
    let slow = 0;
    for (let fast = 1; fast < arr.length; fast++) {
        if (arr[fast] !== arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;
}

2. Sliding Window

Use: subarrays, substrings with constraints
Time: O(n)
Space: O(1) or O(k)

// Fixed window
function maxSum(arr, k) {
    let sum = 0;
    for (let i = 0; i < k; i++) sum += arr[i];
    let maxSum = sum;
    for (let i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

// Variable window (longest substring)
function longestSubstring(s) {
    let set = new Set();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

3. Prefix Sum

Use: range queries, subarray sum
Time: O(n) build, O(1) query
Space: O(n)

// Build prefix sum
function prefixSum(arr) {
    let prefix = [0];
    for (let i = 0; i < arr.length; i++) {
        prefix.push(prefix[i] + arr[i]);
    }
    return prefix;
}

// Range sum
function rangeSum(prefix, i, j) {
    return prefix[j + 1] - prefix[i];
}

// Subarray sum equals k
function subarraySum(nums, k) {
    let map = new Map();
    map.set(0, 1);
    let sum = 0, count = 0;
    for (let num of nums) {
        sum += num;
        if (map.has(sum - k)) count += map.get(sum - k);
        map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
}

4. Binary Search

Use: sorted arrays, search
Time: O(log n)
Space: O(1)

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

// Lower bound (first occurrence)
function lowerBound(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

5. DFS (Depth‑First Search)

Use: trees, graphs, backtracking
Time: O(V + E) / O(2ⁿ)
Space: O(h) recursion stack

// Tree traversal
function dfs(root) {
    if (!root) return;
    console.log(root.val);    // pre‑order
    dfs(root.left);
    dfs(root.right);
}

// Graph DFS
function dfsGraph(node, visited) {
    if (visited.has(node)) return;
    visited.add(node);
    console.log(node);
    for (let neighbor of graph[node]) {
        dfsGraph(neighbor, visited);
    }
}

// Backtracking (Permutations)
function permute(nums) {
    let result = [];
    function backtrack(path, used) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true;
            backtrack(path, used);
            used[i] = false;
            path.pop();
        }
    }
    backtrack([], []);
    return result;
}

6. BFS (Breadth‑First Search)

Use: shortest path, level order
Time: O(V + E)
Space: O(V)

// Level order traversal
function bfs(root) {
    if (!root) return;
    let queue = [root];
    while (queue.length) {
        let node = queue.shift();
        console.log(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

// Shortest path (unweighted)
function shortestPath(graph, start, target) {
    let queue = [start];
    let visited = new Set([start]);
    let distance = 0;
    while (queue.length) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node === target) return distance;
            for (let neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        distance++;
    }
    return -1;
}

7. Dynamic Programming

Use: optimisation, counting
Time: O(n²) / O(n)
Space: O(n) / O(1)

// Top‑down (memoization)
function fib(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// Bottom‑up (tabulation)
function fibDP(n) {
    if (n <= 1) return n;
    let dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Knapsack (0/1)
function knapsack(wt, val, W) {
    let n = wt.length;
    let dp = Array(n + 1).fill(0).map(() => Array(W + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

8. Union‑Find (Disjoint Set)

Use: connected components
Time: O(α(n)) ≈ O(1)
Space: O(n)

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = Array(n).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(a, b) {
        let ra = this.find(a);
        let rb = this.find(b);
        if (ra === rb) return false;
        if (this.rank[ra] < this.rank[rb]) {
            this.parent[ra] = rb;
        } else if (this.rank[ra] > this.rank[rb]) {
            this.parent[rb] = ra;
        } else {
            this.parent[rb] = ra;
            this.rank[ra]++;
        }
        return true;
    }
}

9. Trie (Prefix Tree)

Use: word search, autocomplete
Time: O(L) where L = word length
Space: O(n * L)

class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEnd = true;
    }

    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return node.isEnd;
    }

    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return true;
    }
}

10. Topological Sort

Use: DAG ordering
Time: O(V + E)
Space: O(V)

// Kahn's Algorithm (BFS)
function topologicalSort(n, edges) {
    let graph = Array.from({ length: n }, () => []);
    let indegree = Array(n).fill(0);
    for (let [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }

    let queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let result = [];
    while (queue.length) {
        let u = queue.shift();
        result.push(u);
        for (let v of graph[u]) {
            indegree[v]--;
            if (indegree[v] === 0) queue.push(v);
        }
    }

    return result.length === n ? result : null; // null if cycle
}

Code Templates by Category

Array Problems

// Two Sum
function twoSum(nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map.has(complement)) return [map.get(complement), i];
        map.set(nums[i], i);
    }
    return [];
}

// Maximum Subarray (Kadane)
function maxSubarray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

// Merge Intervals
function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let result = [];
    for (let interval of intervals) {
        if (!result.length || result[result.length - 1][1] < interval[0]) {
            result.push(interval);
        } else {
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], interval[1]);
        }
    }
    return result;
}

String Problems

// Longest Palindrome
function longestPalindrome(s) {
    let count = 0;
    let set = new Set();
    for (let char of s) {
        if (set.has(char)) {
            count += 2;
            set.delete(char);
        } else {
            set.add(char);
        }
    }
    return count + (set.size > 0 ? 1 : 0);
}

// Anagram Check
function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    let map = {};
    for (let char of s) {
        map[char] = (map[char] || 0) + 1;
    }
    for (let char of t) {
        if (!map[char]) return false;
        map[char]--;
    }
    return true;
}

Tree Problems

// Max Depth
function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Validate BST
function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;
        if (node.val <= min || node.val >= max) return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
    return validate(root, -Infinity, Infinity);
}

Graph Problems

// Number of Islands
function numIslands(grid) {
    let count = 0;
    function dfs(i, j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') return;
        grid[i][j] = '0';
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

Complexity Reference

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Hash Table	O(1)	O(1)	O(1)	O(1)
BST (Balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Heap	O(1)	O(n)	O(log n)	O(log n)
Stack / Queue	O(1)	O(n)	O(1)	O(1)

📌 Quick Reference

Two Pointers: O(n) time, O(1) space – sorted arrays
Sliding Window: O(n) time – subarrays/substrings
Prefix Sum: O(1) range queries – subarray sum
Binary Search: O(log n) – sorted arrays
DFS: recursion stack – trees, graphs
BFS: queue – shortest path, level order
DP: memoization or tabulation – optimisation
Union‑Find: O(α(n)) – connected components

← Back to All Cheatsheets