Code Templates

Copy-paste ready templates for common DSA patterns

Binary Search

Standard Binary Search

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // Not found
}

Use when searching for exact value in sorted array.

Lower Bound (First Position)

// Find first position where condition is true
int lowerBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;  // First position where nums[i] >= target
}

Returns first index where element >= target. Use for finding insertion point.

Binary Search on Answer

// Find minimum value that satisfies condition
int binarySearchOnAnswer(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isValid(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

bool isValid(int val) {
    // Check if 'val' satisfies the condition
    return true;
}

Use for "minimum/maximum that satisfies X" problems (Koko Eating Bananas, Split Array).

Sliding Window

Variable Size Window

int slidingWindow(vector<int>& nums) {
    int left = 0, result = 0;
    // State variables (e.g., sum, map, count)
    
    for (int right = 0; right < nums.size(); right++) {
        // Add nums[right] to window state
        
        while (/* window is invalid */) {
            // Remove nums[left] from window state
            left++;
        }
        
        // Update result (window [left, right] is valid)
        result = max(result, right - left + 1);
    }
    return result;
}

For "longest/shortest subarray with property X" problems.

Fixed Size Window

int fixedWindow(vector<int>& nums, int k) {
    int result = 0, windowSum = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        windowSum += nums[i];
        
        if (i >= k - 1) {
            result = max(result, windowSum);
            windowSum -= nums[i - k + 1];
        }
    }
    return result;
}

For "k consecutive elements" problems.

Two Pointers

Opposite Direction

void twoPointers(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        // Process based on condition
        if (condition) {
            left++;
        } else {
            right--;
        }
    }
}

Use for sorted array pair finding, palindrome checking.

BFS (Breadth-First Search)

BFS Graph/Tree

void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        // Process node
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

BFS Grid (4 Directions)

int bfsGrid(vector<vector<int>>& grid, int sr, int sc) {
    int m = grid.size(), n = grid[0].size();
    int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    queue<pair<int,int>> q;
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    
    q.push({sr, sc});
    visited[sr][sc] = true;
    int level = 0;
    
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [r, c] = q.front();
            q.pop();
            
            // Process cell
            
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n 
                    && !visited[nr][nc] && grid[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
        level++;
    }
    return level;
}

Use for shortest path in unweighted grid. Level tracking gives distance.

DFS (Depth-First Search)

DFS Recursive

vector<bool> visited;

void dfs(vector<vector<int>>& graph, int node) {
    visited[node] = true;
    
    // Process node
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor);
        }
    }
}

DFS Grid (Flood Fill)

void dfsGrid(vector<vector<int>>& grid, int r, int c) {
    int m = grid.size(), n = grid[0].size();
    
    // Boundary and validity check
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) {
        return;
    }
    
    grid[r][c] = 0;  // Mark visited
    
    // Explore 4 directions
    dfsGrid(grid, r + 1, c);
    dfsGrid(grid, r - 1, c);
    dfsGrid(grid, r, c + 1);
    dfsGrid(grid, r, c - 1);
}

Use for Number of Islands, connected components. Modifies grid as visited marker.

Backtracking

Subsets / Combinations

vector<vector<int>> result;

void backtrack(vector<int>& nums, int start, vector<int>& path) {
    result.push_back(path);  // Add current subset
    
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);     // Choose
        backtrack(nums, i + 1, path); // Explore
        path.pop_back();              // Un-choose
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> path;
    backtrack(nums, 0, path);
    return result;
}

Permutations

vector<vector<int>> result;

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, path, used);
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<int> path;
    vector<bool> used(nums.size(), false);
    backtrack(nums, path, used);
    return result;
}

Dynamic Programming

1D DP (Fibonacci Pattern)

int dp1D(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// Space optimized version
int dp1DOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2D DP (LCS Pattern)

int lcs(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

Knapsack Pattern

// 0/1 Knapsack
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i-1][w];  // Don't take item
            if (w >= weights[i-1]) {
                dp[i][w] = max(dp[i][w], 
                    dp[i-1][w - weights[i-1]] + values[i-1]);
            }
        }
    }
    return dp[n][capacity];
}

// Unbounded Knapsack (Coin Change)
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Union Find (Disjoint Set)

Union Find with Rank

class UnionFind {
public:
    vector<int> parent, rank;
    int components;
    
    UnionFind(int n) : parent(n), rank(n, 0), components(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];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        
        components--;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

Use for connected components, cycle detection, Kruskal's MST.

Trie (Prefix Tree)

Trie Implementation

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie {
    TrieNode* root;
public:
    Trie() : root(new TrieNode()) {}
    
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    bool search(const string& word) {
        TrieNode* node = find(word);
        return node != nullptr && node->isEnd;
    }
    
    bool startsWith(const string& prefix) {
        return find(prefix) != nullptr;
    }
    
private:
    TrieNode* find(const string& s) {
        TrieNode* node = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

Use for word search, autocomplete, word dictionary problems.