DSA Patterns

Master these patterns to solve any coding problem

Two Pointers

Use two pointers moving towards each other or in the same direction

When to Use

Sorted array or linked list problems
Finding pairs with specific sum
Comparing elements from both ends
Removing duplicates in-place

How It Works

Start pointers at opposite ends (or both at start). Move them based on condition until they meet.

int left = 0, right = n - 1;
while (left < right) {
    if (condition_met) {
        // process and move both
        left++; right--;
    } else if (need_larger) {
        left++;
    } else {
        right--;
    }
}

Two Sum II 3Sum Container With Most Water Trapping Rain Water Valid Palindrome

Sliding Window

Maintain a window of elements and slide it across the data

When to Use

Contiguous subarray/substring problems
Finding longest/shortest with some property
Problems with "k consecutive elements"
String matching and anagram problems

How It Works

Expand window by moving right pointer. Shrink by moving left pointer when constraint violated.

int left = 0;
for (int right = 0; right < n; right++) {
    // Add element at right to window state
    
    while (window_invalid) {
        // Remove element at left from window state
        left++;
    }
    
    // Update result (window is valid here)
    result = max(result, right - left + 1);
}

Longest Substring Without Repeating Minimum Window Substring Max Consecutive Ones III Permutation in String Sliding Window Maximum

Fast and Slow Pointers

Two pointers moving at different speeds (Floyd's Tortoise and Hare)

When to Use

Detecting cycles in linked list
Finding middle of linked list
Finding cycle start point
Happy number problem

How It Works

Slow moves 1 step, fast moves 2 steps. If cycle exists, they will meet.

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true; // cycle found
}
return false;

Linked List Cycle Find Cycle Start Middle of Linked List Happy Number Palindrome Linked List

Binary Search

Divide search space in half each iteration

When to Use

Sorted array search
"Find minimum/maximum that satisfies condition"
Search space can be divided
Monotonic function problems

Key Insight

Use left + (right - left) / 2 to avoid overflow. Adjust boundaries carefully.

// Find first position where condition is true
int left = 0, right = n;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (condition(mid)) {
        right = mid;  // answer is mid or left of mid
    } else {
        left = mid + 1;  // answer is right of mid
    }
}
return left;

Binary Search First Bad Version Search in Rotated Array Koko Eating Bananas Median of Two Sorted Arrays

BFS / DFS

Traversal strategies for trees and graphs

When to Use Each

BFS: Shortest path (unweighted), level-order traversal
DFS: Path finding, cycle detection, connected components
BFS: When solution is near the root
DFS: When solution is deep or exploring all paths

// BFS Template
queue q;
q.push(start);
while (!q.empty()) {
    auto node = q.front(); q.pop();
    for (auto neighbor : node->neighbors) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            q.push(neighbor);
        }
    }
}

// DFS Template (Recursive)
void dfs(Node* node) {
    visited[node] = true;
    for (auto neighbor : node->neighbors) {
        if (!visited[neighbor]) dfs(neighbor);
    }
}

Number of Islands Clone Graph Word Ladder Course Schedule Binary Tree Level Order

Backtracking

Explore all possibilities by building solution incrementally

When to Use

Generate all permutations/combinations
Solving puzzles (N-Queens, Sudoku)
Subset/partition problems
When you need ALL solutions

Key Steps

1. Make a choice 2. Recurse 3. Undo the choice (backtrack)

void backtrack(vector& path, vector>& result) {
    if (is_solution(path)) {
        result.push_back(path);
        return;
    }
    for (auto& choice : get_choices()) {
        if (is_valid(choice)) {
            path.push_back(choice);       // Make choice
            backtrack(path, result);       // Explore
            path.pop_back();              // Undo choice
        }
    }
}

Subsets Permutations Combination Sum N-Queens Word Search

Dynamic Programming

Break problem into overlapping subproblems

DP Indicators

"Find minimum/maximum" with constraints
"Count number of ways"
"Can you achieve X?" (yes/no)
Optimal substructure + overlapping subproblems

Common DP Patterns

1D DP: Fibonacci, Climbing Stairs, House Robber
2D DP: Grid paths, LCS, Edit Distance
Knapsack: Subset Sum, Coin Change
Interval: Matrix Chain, Burst Balloons

// Bottom-up DP template
vector dp(n + 1, 0);
dp[0] = base_case;

for (int i = 1; i <= n; i++) {
    for (auto& choice : choices) {
        if (valid(i, choice)) {
            dp[i] = optimal(dp[i], dp[prev_state] + cost);
        }
    }
}
return dp[n];

Climbing Stairs Coin Change Longest Common Subsequence 0/1 Knapsack Longest Increasing Subsequence

Monotonic Stack

Stack maintaining increasing or decreasing order

When to Use

Next greater/smaller element
Previous greater/smaller element
Largest rectangle in histogram
Stock span problems

// Next Greater Element
vector nextGreater(vector& nums) {
    int n = nums.size();
    vector result(n, -1);
    stack st;  // store indices
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

Next Greater Element Daily Temperatures Largest Rectangle in Histogram Trapping Rain Water

Prefix Sum

Precompute cumulative sums for O(1) range queries

When to Use

Multiple range sum queries
Subarray sum equals K
Finding subarrays with specific properties
2D grid sum queries

// Build prefix sum
vector prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// Range sum [l, r] inclusive
int rangeSum = prefix[r + 1] - prefix[l];

// Subarray sum equals K (with hashmap)
unordered_map count;
count[0] = 1;
int sum = 0, result = 0;
for (int num : nums) {
    sum += num;
    if (count.count(sum - k)) result += count[sum - k];
    count[sum]++;
}

Range Sum Query Subarray Sum Equals K Continuous Subarray Sum Product of Array Except Self