DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

How to Identify Patterns

Why Patterns Matter More Than Memorization

Most beginners approach DSA by solving problems one at a time, treating each as unique. They grind through 200 problems and still freeze in interviews when a problem is phrased differently.

The developers who interview well do not memorize solutions. They recognize patterns — the underlying algorithmic structure that connects hundreds of different-looking problems into a small number of families.

There are 15 core patterns that cover the overwhelming majority of interview questions at every major tech company. Once you can identify which pattern applies within the first two minutes of reading a problem, you already know where to start, what data structure to reach for, and what complexity to expect.

This topic teaches you all 15. For each pattern you will learn when to use it, what keywords signal it, and how to implement the core technique.

The 15 Patterns at a Glance

Pattern	Core Idea	Complexity Gain
Sliding Window	Maintain a moving window over contiguous elements	O(n²) to O(n)
Prefix Sum	Precompute cumulative sums for range queries	O(n) per query to O(1)
Two Pointers	Move two indices inward from opposite ends	O(n²) to O(n)
Fast and Slow Pointers	Two pointers at different speeds for cycle detection	O(n) space to O(1)
Linked List Reversal	Reverse pointers in-place without extra space	O(n) space to O(1)
Monotonic Stack	Maintain a stack with ordered elements	O(n²) to O(n)
Top K Elements	Use a heap of size K to track top elements	O(n log n) to O(n log k)
Overlapping Intervals	Sort by start, merge or count overlaps	O(n²) to O(n log n)
Modified Binary Search	Apply binary search to rotated or answer space	O(n) to O(log n)
Binary Tree Traversal	DFS and BFS traversal orderings	Foundation for all tree problems
Depth-First Search	Explore deep before backtracking	O(V+E)
Breadth-First Search	Explore level by level for shortest path	O(V+E)
Matrix Traversal	Treat grid cells as graph nodes	O(rows x cols)
Backtracking	Explore all paths, undo invalid choices	O(2^n) or O(n!)
Dynamic Programming	Cache overlapping subproblem results	Exponential to Polynomial

Pattern 1: Sliding Window

When to use it: You need to find or optimize something in a contiguous subarray or substring. The word "contiguous" is the strongest signal.

Core insight: A nested loop that checks every subarray is O(n²). A sliding window maintains a running result and slides right by adding one element and removing another — each element enters and exits at most once, giving O(n).

Keywords: subarray, substring, contiguous, longest, shortest, at most K distinct, window of size K.

Fixed window — window size stays constant. Slide by adding the new right element and removing the old left element.

Variable window — expand right until a condition is violated, then shrink left until the condition is restored.

Java

Try it out

public class SlidingWindow {

    // Fixed window: maximum sum of subarray of size k
    public static int maxSumFixed(int[] arr, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];

        int maxSum = windowSum;

        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i];        // Add incoming right element
            windowSum -= arr[i - k];   // Remove outgoing left element
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    // Variable window: longest subarray with sum <= target
    public static int longestSubarrayWithSum(int[] arr, int target) {
        int left = 0, windowSum = 0, maxLen = 0;

        for (int right = 0; right < arr.length; right++) {
            windowSum += arr[right];               // Expand window right

            while (windowSum > target) {           // Condition violated
                windowSum -= arr[left];            // Shrink from left
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        System.out.println("Max sum (k=3): " + maxSumFixed(arr, 3));

        int[] arr2 = {3, 1, 2, 7, 4, 2, 1, 1, 5};
        System.out.println("Longest subarray (sum<=8): " + longestSubarrayWithSum(arr2, 8));
    }
}

Output:
Max sum (k=3): 9
Longest subarray (sum<=8): 4

Practice problems: Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement, Fruit Into Baskets.

Pattern 2: Prefix Sum

When to use it: You need range sum queries, or you are counting subarrays whose sum equals a specific target. One O(n) precomputation makes every subsequent query O(1).

Core insight: prefix[i] stores the sum of all elements from index 0 to i. The sum from index l to r is prefix[r] - prefix[l-1]. Combined with a hash map, this solves "count subarrays with sum = k" in a single pass.

Keywords: range sum query, subarray sum equals k, cumulative, how many subarrays.

Java

Try it out

import java.util.HashMap;
import java.util.Map;

public class PrefixSum {

    // Count subarrays with sum equal to k using prefix sum + hash map
    public static int countSubarrays(int[] arr, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1); // Empty prefix

        int currentSum = 0, count = 0;

        for (int num : arr) {
            currentSum += num;
            int needed = currentSum - k;

            // If (currentSum - k) was seen before, subarrays ending here sum to k
            count += prefixCount.getOrDefault(needed, 0);
            prefixCount.put(currentSum, prefixCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, -1, 2};
        System.out.println("Subarrays with sum 3: " + countSubarrays(arr, 3));

        int[] arr2 = {1, 1, 1};
        System.out.println("Subarrays with sum 2: " + countSubarrays(arr2, 2));
    }
}

Output:
Subarrays with sum 3: 3
Subarrays with sum 2: 2

Practice problems: Subarray Sum Equals K, Contiguous Array, Range Sum Query, Product of Array Except Self, Find Pivot Index, Subarray Sums Divisible by K.

Pattern 3: Two Pointers

When to use it: The array is sorted (or can be sorted without losing necessary index information), and you need to find pairs, triplets, or validate a condition involving two positions.

Core insight: Instead of checking every pair with nested loops (O(n²)), place one pointer at the start and one at the end. The sum of the two elements tells you which pointer to move — too small means move left forward, too large means move right backward. Each pointer moves at most n times — O(n) total.

Keywords: sorted array, pair sum, three sum, palindrome, remove duplicates, partition, container with most water.

Java

Try it out

import java.util.Arrays;

public class TwoPointers {

    // Find all unique triplets that sum to zero
    public static void threeSum(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates

            int left = i + 1, right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    System.out.println("[" + nums[i] + ", " + nums[left] + ", " + nums[right] + "]");
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++; right--;
                } else if (sum < 0) {
                    left++;   // Need a larger sum
                } else {
                    right--;  // Need a smaller sum
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println("Triplets summing to 0:");
        threeSum(nums);
    }
}

Output:
Triplets summing to 0:
[-1, -1, 2]
[-1, 0, 1]

Practice problems: Two Sum II, 3Sum, Container With Most Water, Valid Palindrome, Remove Duplicates from Sorted Array, Trapping Rain Water, Sort Colors.

Pattern 4: Fast and Slow Pointers

When to use it: Cycle detection in linked lists, finding the middle of a linked list, or any problem where two pointers moving at different speeds reveal structural properties.

Core insight: Slow moves one step at a time. Fast moves two steps. If a cycle exists, fast will eventually lap slow and they will meet inside the cycle. If no cycle, fast reaches the end. When slow reaches the middle, fast is at the end.

Keywords: cycle in linked list, middle of linked list, cycle start point, happy number, find duplicate.

Java

Try it out

public class FastSlowPointers {

    static class ListNode {
        int val; ListNode next;
        ListNode(int val) { this.val = val; }
    }

    // Detect cycle — slow moves 1 step, fast moves 2 steps
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;           // Move 1 step
            fast = fast.next.next;      // Move 2 steps
            if (slow == fast) return true;
        }

        return false;
    }

    // Find middle — when fast reaches end, slow is at middle
    public static ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next; // Cycle: 4 -> 2

        System.out.println("Has cycle: " + hasCycle(head));

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);
        System.out.println("Middle value: " + findMiddle(head2).val);
    }
}

Output:
Has cycle: true
Middle value: 3

Practice problems: Linked List Cycle, Linked List Cycle II, Middle of the Linked List, Happy Number, Palindrome Linked List, Reorder List.

Pattern 5: Linked List In-Place Reversal

When to use it: Reversing an entire linked list, reversing a portion between two positions, or reversing in groups of K — all without allocating extra nodes.

Core insight: Three pointers — prev, curr, and next — reverse the direction of each link one node at a time. prev starts as null (the new tail points to nothing). After the loop, prev points to the new head.

Keywords: reverse linked list, reverse between positions, reverse in k-groups, reorder list, rotate list.

Java

Try it out

public class ListReversal {

    static class ListNode {
        int val; ListNode next;
        ListNode(int v) { val = v; }
    }

    // Reverse entire linked list in-place — O(n) time, O(1) space
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;  // Save next before overwriting
            curr.next = prev;           // Reverse the link
            prev = curr;                // Advance prev
            curr = next;                // Advance curr
        }

        return prev; // New head
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + (head.next != null ? " -> " : ""));
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.print("Original: "); printList(head);
        head = reverse(head);
        System.out.print("Reversed: "); printList(head);
    }
}

Output:
Original: 1 -> 2 -> 3 -> 4 -> 5
Reversed: 5 -> 4 -> 3 -> 2 -> 1

Dry Run: Reversing 1 -> 2 -> 3

Initial: prev=null, curr=1

Step 1: next=2, curr(1).next=null, prev=1, curr=2
        null <- 1    2 -> 3

Step 2: next=3, curr(2).next=1, prev=2, curr=3
        null <- 1 <- 2    3

Step 3: next=null, curr(3).next=2, prev=3, curr=null
        null <- 1 <- 2 <- 3

curr is null → loop ends → return prev=3
Result: 3 -> 2 -> 1

Practice problems: Reverse Linked List, Reverse Linked List II, Reverse Nodes in k-Group, Swap Nodes in Pairs, Rotate List.

Pattern 6: Monotonic Stack

When to use it: You need to find the next greater element, previous smaller element, or solve histogram and span problems. A brute force would scan left or right for each element — O(n²). A monotonic stack does it in O(n).

Core insight: Maintain a stack whose elements are always in increasing or decreasing order. When a new element violates the order, pop elements — each popped element has found its answer (the current element is its next greater or smaller neighbor).

Keywords: next greater element, previous smaller element, daily temperatures, stock span, largest rectangle in histogram, trapping rain water.

Java

Try it out

import java.util.Arrays;
import java.util.Stack;

public class MonotonicStack {

    // Next greater element for each position — O(n) using decreasing stack
    public static int[] nextGreaterElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        Stack<Integer> stack = new Stack<>(); // Stores indices

        for (int i = 0; i < n; i++) {
            // Pop all indices whose value is smaller than current
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                int idx = stack.pop();
                result[idx] = arr[i]; // Current element is the next greater
            }
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 3, 4};
        int[] result = nextGreaterElement(arr);

        System.out.print("Input:        ");
        for (int x : arr) System.out.print(x + " ");
        System.out.println();

        System.out.print("Next Greater: ");
        for (int x : result) System.out.print(x + " ");
        System.out.println();
    }
}

Output:
Input:        2 1 5 3 4
Next Greater: 5 5 -1 4 -1

Practice problems: Next Greater Element I and II, Daily Temperatures, Largest Rectangle in Histogram, Trapping Rain Water, Online Stock Span, Sum of Subarray Minimums.

Pattern 7: Top K Elements

When to use it: You need the K largest, K smallest, K most frequent, or K closest elements without sorting the entire array.

Core insight: Sorting to find top K costs O(n log n). A heap of size K costs O(n log k) — much better when K is small. For K largest, use a min-heap of size K. If a new element is larger than the heap's minimum, replace it. After processing all n elements, the heap contains exactly the K largest.

Keywords: K largest, K smallest, K most frequent, K closest, top K, Kth element, merge K sorted lists.

Java

Try it out

import java.util.PriorityQueue;

public class TopKElements {

    // K largest elements using a min-heap of size K
    public static int[] kLargest(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : arr) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Evict the smallest — keep only top K
            }
        }

        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll();
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 12, 2, 11, 7};
        int k = 3;
        int[] result = kLargest(arr, k);

        System.out.print("Top " + k + " largest: ");
        for (int x : result) System.out.print(x + " ");
        System.out.println();
    }
}

Output:
Top 3 largest: 12 11 7

Practice problems: Kth Largest Element in an Array, Top K Frequent Elements, K Closest Points to Origin, Find Median from Data Stream, Merge K Sorted Lists, Kth Smallest Element in a Sorted Matrix.

Pattern 8: Overlapping Intervals

When to use it: Problems involving scheduling, meetings, time ranges, or any collection of intervals where you need to merge overlaps, count conflicts, or insert a new interval.

Core insight: Sort intervals by start time. Two intervals overlap when the start of the second is less than or equal to the end of the first. After sorting, you only compare each interval with the most recently merged one — a single linear pass solves the problem.

Keywords: merge intervals, meeting rooms, insert interval, non-overlapping intervals, minimum arrows, scheduling conflict.

Java

Try it out

import java.util.Arrays;

public class MergeIntervals {

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return intervals;

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // Sort by start

        int[][] result = new int[intervals.length][2];
        int idx = 0;
        result[idx] = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= result[idx][1]) {
                // Overlap — extend the current merged interval's end
                result[idx][1] = Math.max(result[idx][1], intervals[i][1]);
            } else {
                // No overlap — start a new merged interval
                idx++;
                result[idx] = intervals[i];
            }
        }

        return Arrays.copyOf(result, idx + 1);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] merged = merge(intervals);

        System.out.print("Merged: ");
        for (int[] iv : merged)
            System.out.print("[" + iv[0] + "," + iv[1] + "] ");
        System.out.println();
    }
}

Output:
Merged: [1,6] [8,10] [15,18]

Practice problems: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms I and II, Minimum Number of Arrows to Burst Balloons, Car Pooling.

Pattern 9: Modified Binary Search

When to use it: The array is sorted, rotated, or you are searching for a threshold in an answer space where feasibility is monotonic. If "once possible for x, it stays possible for all larger x," binary search applies.

Core insight: On rotated arrays, one half is always sorted — check which half and decide where to search. On answer spaces, check feasibility of mid and eliminate half the range. The key is identifying what property makes the search space monotonic.

Keywords: rotated sorted array, find minimum in rotated, peak element, capacity within D days, Koko eating bananas, minimum or maximum such that condition holds.

Java

Try it out

public class ModifiedBinarySearch {

    // Search in rotated sorted array — one half is always sorted
    public static 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 is sorted
                if (target >= arr[left] && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (target > arr[mid] && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Search 0: index " + searchRotated(arr, 0));
        System.out.println("Search 5: index " + searchRotated(arr, 5));
        System.out.println("Search 3: index " + searchRotated(arr, 3));
    }
}

Output:
Search 0: index 4
Search 5: index 1
Search 3: index -1

Practice problems: Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Find Peak Element, Capacity to Ship Packages Within D Days, Koko Eating Bananas.

Pattern 10: Binary Tree Traversal

When to use it: Any problem that requires visiting tree nodes in a specific order. The order you visit nodes determines what information is available at each step.

Core insight: Inorder (left, root, right) on a BST gives sorted output. Preorder (root, left, right) is natural for copying or serializing. Postorder (left, right, root) processes children before parents — good for deletion or dependency resolution. Level-order uses a queue and is essential for shortest-path or level-wise problems.

Keywords: inorder, preorder, postorder, level order, BST sorted order, tree serialization, height by level, zigzag.

Java

Try it out

import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversal {

    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int v) { val = v; }
    }

    static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    static void preorder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    static void postorder(TreeNode root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }

    static void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2); root.right = new TreeNode(6);
        root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5); root.right.right = new TreeNode(7);

        System.out.print("Inorder:    "); inorder(root);    System.out.println();
        System.out.print("Preorder:   "); preorder(root);   System.out.println();
        System.out.print("Postorder:  "); postorder(root);  System.out.println();
        System.out.print("LevelOrder: "); levelOrder(root); System.out.println();
    }
}

Output:
Inorder:    1 2 3 4 5 6 7
Preorder:   4 2 1 3 6 5 7
Postorder:  1 3 2 5 7 6 4
LevelOrder: 4 2 6 1 3 5 7

Practice problems: Binary Tree Inorder Traversal, Binary Tree Level Order Traversal, Binary Tree Zigzag Level Order Traversal, Validate Binary Search Tree.

Pattern 11: Depth-First Search (DFS)

When to use it: Exploring all paths in a graph or tree, detecting cycles, finding connected components, computing topological order, or any problem requiring complete exploration before backtracking.

Core insight: DFS goes as deep as possible along one path before backtracking. A visited marker prevents revisiting nodes. Recursion naturally implements DFS — the call stack serves as the DFS stack.

Keywords: number of islands, path sum, connected components, cycle detection, topological sort, all paths, depth of tree, flood fill.

Java

Try it out

public class DFSPattern {

    // Count islands using DFS — sink each island as it is found
    public static int numIslands(char[][] grid) {
        int count = 0;

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    count++;
                }
            }
        }

        return count;
    }

    private static void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
        if (grid[r][c] != '1') return;

        grid[r][c] = '0'; // Mark visited by sinking
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println("Number of islands: " + numIslands(grid));
    }
}

Output:
Number of islands: 3

Practice problems: Number of Islands, Max Area of Island, Path Sum, Clone Graph, Course Schedule, Pacific Atlantic Water Flow, Longest Increasing Path in a Matrix.

Pattern 12: Breadth-First Search (BFS)

When to use it: Finding the shortest path in an unweighted graph, exploring nodes level by level, or any problem where you need the minimum number of steps to reach a target.

Core insight: BFS uses a queue. All nodes at distance 1 are visited before any node at distance 2. This level-by-level guarantee means the first time BFS reaches the target, it has found the shortest path. A visited set prevents processing the same node twice.

Keywords: shortest path, minimum steps, level order, nearest, rotting oranges, word ladder, 01 matrix, as far from land as possible.

Java

Try it out

import java.util.LinkedList;
import java.util.Queue;

public class BFSPattern {

    // Minimum steps to reach target in an unweighted grid
    public static int minSteps(int[][] grid, int[] start, int[] target) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], steps = curr[2];

            if (r == target[0] && c == target[1]) return steps;

            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && grid[nr][nc] == 0) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, steps + 1});
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{0,0,0},{1,1,0},{0,0,0}};
        System.out.println("Min steps: " + minSteps(grid, new int[]{0,0}, new int[]{2,2}));
    }
}

Output:
Min steps: 4

Practice problems: Binary Tree Level Order Traversal, Rotting Oranges, 01 Matrix, Word Ladder, Shortest Path in Binary Matrix, As Far from Land as Possible.

Pattern 13: Matrix Traversal

When to use it: Any problem involving a 2D grid where cells are connected to neighbors. Matrix problems are graph problems in disguise — each cell is a node and adjacent cells are edges.

Core insight: Treat the grid as a graph. Use DFS or BFS from each unvisited qualifying cell. Always check boundary conditions before moving to a neighbor. For "distance from nearest source" problems, use multi-source BFS — add all sources to the queue simultaneously before starting traversal.

Keywords: grid, island, flood fill, region, surrounded, matrix path, connected cells, area, distance from nearest zero.

Java

Try it out

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class MatrixTraversal {

    // Distance of each cell from nearest 0 — multi-source BFS
    public static int[][] updateMatrix(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        int[][] dist = new int[rows][cols];
        Queue<int[]> queue = new LinkedList<>();

        // Initialize: 0-cells have distance 0, 1-cells start as max
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (mat[r][c] == 0) {
                    dist[r][c] = 0;
                    queue.offer(new int[]{r, c});
                } else {
                    dist[r][c] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] dir : dirs) {
                int nr = curr[0]+dir[0], nc = curr[1]+dir[1];
                if (nr>=0 && nr<rows && nc>=0 && nc<cols
                        && dist[nr][nc] > dist[curr[0]][curr[1]] + 1) {
                    dist[nr][nc] = dist[curr[0]][curr[1]] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] result = updateMatrix(mat);
        System.out.println("Distance matrix:");
        for (int[] row : result) System.out.println(Arrays.toString(row));
    }
}

Output:
Distance matrix:
[0, 0, 0]
[0, 1, 0]
[1, 2, 1]

Practice problems: Number of Islands, Max Area of Island, Surrounded Regions, Pacific Atlantic Water Flow, Word Search, Shortest Path in Binary Matrix, Number of Closed Islands.

Pattern 14: Backtracking

When to use it: You need to generate all valid combinations, permutations, subsets, or placements. You explore choices one at a time, recurse to explore their consequences, then undo the choice and try the next one.

Core insight: Make a choice, recurse with that choice, then undo the choice (backtrack) and try the next option. This explores the entire decision tree systematically. Pruning — stopping early when a partial solution cannot possibly be completed — is what makes backtracking efficient.

Keywords: all permutations, all subsets, combination sum, generate parentheses, sudoku, N-queens, word search, palindrome partitioning.

Java

Try it out

import java.util.ArrayList;
import java.util.List;

public class Backtracking {

    // Generate all subsets of an array — 2^n subsets total
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int start,
                                   List<Integer> current,
                                   List<List<Integer>> result) {
        result.add(new ArrayList<>(current)); // Every state is a valid subset

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                    // Make choice
            backtrack(nums, i + 1, current, result); // Explore
            current.remove(current.size() - 1);      // Undo choice
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = subsets(nums);
        System.out.println("All subsets (" + result.size() + " total):");
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

Output:
All subsets (8 total):
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

Dry Run: Backtracking Decision Tree for [1, 2, 3]

backtrack(start=0, current=[])
  add [] to result

  i=0: push 1 → current=[1]
    backtrack(start=1, current=[1])
      add [1] to result
      i=1: push 2 → current=[1,2]
        backtrack(start=2, current=[1,2])
          add [1,2] to result
          i=2: push 3 → current=[1,2,3]
            backtrack(start=3) → add [1,2,3], no more choices
          pop 3 → current=[1,2]
        pop 2 → current=[1]
      i=2: push 3 → current=[1,3]
        backtrack(start=3) → add [1,3]
      pop 3 → current=[1]
    pop 1 → current=[]

  i=1: push 2 → generates [2], [2,3]
  i=2: push 3 → generates [3]

Total subsets: 2^3 = 8

Practice problems: Subsets, Permutations, Combination Sum, Generate Parentheses, Letter Combinations of a Phone Number, Palindrome Partitioning, N-Queens, Sudoku Solver, Word Search.

Pattern 15: Dynamic Programming

When to use it: The problem asks for an optimal value (maximum, minimum, longest, shortest) or a count of ways, and breaking it into subproblems reveals overlapping computations. The same subproblem appears multiple times — caching its result avoids recomputing it.

Core insight: Identify the state (what uniquely defines a subproblem), write the recurrence relation (how the current state depends on smaller states), determine base cases, then fill a table bottom-up. Bottom-up tabulation avoids recursion stack overhead and is generally preferred in interviews.

Keywords: maximum, minimum, longest, count ways, partition, can we achieve, optimal, overlapping subproblems, decision at each step.

Java

Try it out

public class DynamicProgramming {

    // Climbing stairs — how many ways to reach step n using 1 or 2 steps
    // Recurrence: dp[i] = dp[i-1] + dp[i-2]
    public static int climbStairs(int n) {
        if (n <= 2) return n;

        int prev2 = 1; // dp[1]
        int prev1 = 2; // dp[2]

        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2; // Reach step i from i-1 or i-2
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }

    // House Robber — maximum sum of non-adjacent elements
    // Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("Ways to climb 5 stairs: " + climbStairs(5));
        System.out.println("Ways to climb 8 stairs: " + climbStairs(8));

        int[] houses = {2, 7, 9, 3, 1};
        System.out.println("Max rob: " + rob(houses));
    }
}

Output:
Ways to climb 5 stairs: 8
Ways to climb 8 stairs: 34
Max rob: 12

Dry Run: House Robber on [2, 7, 9, 3, 1]

nums = [2, 7, 9, 3, 1]

Base cases:
  prev2 = 2          (best robbing only house 0)
  prev1 = max(2,7) = 7  (best robbing houses 0-1)

i=2: curr = max(7, 2+9) = max(7,11) = 11
     prev2=7, prev1=11

i=3: curr = max(11, 7+3) = max(11,10) = 11
     prev2=11, prev1=11

i=4: curr = max(11, 11+1) = max(11,12) = 12
     prev2=11, prev1=12

Result: 12  (rob houses 0,2,4 → 2+9+1=12 ✓)

Practice problems: Climbing Stairs, House Robber, Longest Increasing Subsequence, Longest Common Subsequence, Coin Change, Edit Distance, Partition Equal Subset Sum, Unique Paths, Word Break.

Pattern Decision Guide

Problem Clue	Pattern to Try
Contiguous subarray or substring	Sliding Window
Range sum, count subarrays with sum k	Prefix Sum
Sorted array, pair or triplet sum	Two Pointers
Cycle in linked list, find middle	Fast and Slow Pointers
Reverse linked list in-place	Linked List Reversal
Next greater or smaller element	Monotonic Stack
K largest, K smallest, K frequent	Top K Elements (Heap)
Merging or counting time intervals	Overlapping Intervals
Sorted/rotated array, answer threshold	Modified Binary Search
Tree node ordering (in/pre/post/level)	Binary Tree Traversal
All paths, connectivity, cycle, depth	DFS
Shortest path, minimum steps, nearest	BFS
Grid cells, islands, flood fill	Matrix Traversal
All combinations, subsets, placements	Backtracking
Optimal value, count ways, overlapping	Dynamic Programming

Common Mistakes Beginners Make

Reaching for DP on every optimization problem. If a greedy local choice always leads to the global optimum, DP is unnecessary. Activity selection is greedy, not DP. Ask: does the best choice at one step depend on future choices? If no — greedy. If yes — DP.

Using Two Pointers on unsorted data. Two Pointers requires sorted order to know which pointer to move. On unsorted arrays use hashing instead.

Forgetting to mark cells visited before adding to BFS queue. If you mark visited only when dequeuing, the same cell can be added multiple times — causing incorrect distances and bloated queue size.

Confusing Sliding Window with Two Pointers. Both use two indices but solve different problems. Two Pointers works from both ends toward the center on sorted data. Sliding Window moves left to right maintaining a window property on unsorted data.

Not pruning in backtracking. Without pruning, backtracking degenerates to brute force. Add constraint checks before recursing — if the current partial path already violates the condition, stop and backtrack immediately.

Interview Questions

Q: How do you decide between sliding window and prefix sum for subarray problems?

Sliding window is best for finding the longest or shortest subarray satisfying a condition — you dynamically grow and shrink the window. Prefix sum combined with a hash map is best for counting how many subarrays satisfy a condition (sum equals k) or answering multiple range queries. Both are O(n) but solve structurally different problem shapes.

Q: When should you use BFS instead of DFS?

Use BFS when the problem requires shortest path or minimum steps in an unweighted graph — BFS explores level by level, guaranteeing the first path found is shortest. Use DFS when you need all paths, cycle detection, connected components, or topological order. For tree problems without shortest-path requirements, DFS is simpler.

Q: How do you recognize DP versus backtracking?

Both involve exploring choices. Backtracking enumerates all valid results — it does not combine subproblem results. DP occurs when the recursive tree has overlapping subproblems — the same state is solved multiple times — and you need only one optimal result rather than all results. If the recursion tree repeats states, cache them: that is DP.

Q: What is the difference between top K using a heap versus sorting?

Sorting costs O(n log n) regardless of K. A min-heap of size K costs O(n log k). When K is much smaller than n, the heap approach is dramatically faster. When K approaches n, the difference shrinks. Always ask whether K is small relative to n before choosing.

FAQs

Do I need all 15 patterns before applying for jobs?

No. Hashing, Two Pointers, Sliding Window, Binary Search, DFS, and BFS cover the majority of easy and medium problems at most companies. Master these six first. Then add Prefix Sum, Monotonic Stack, and DP. Top K, Intervals, and the linked list patterns complete your preparation for harder problems.

What is the fastest way to build pattern recognition?

After every problem — even ones you solved correctly — write one sentence: "This used Pattern X because the clue was Y." Do this for 30 to 40 problems. Deliberate labeling builds an indexed mental model that activates automatically on future problems.

Can one problem require multiple patterns?

Yes, frequently. Prefix Sum plus Hashing for counting subarray sums. BFS plus a visited set. Binary Search on the answer with a greedy feasibility check inside. Identify which pattern handles the outer structure and which handles the inner sub-operation.

What if I recognize the pattern but still get stuck?

Pattern identification narrows you to the right family. Within each pattern, the specific invariant differs per problem. When stuck, ask: what does my data structure represent at each step? What must stay true at every iteration? These are answerable questions once you know your pattern.

Quick Quiz

Question 1: A problem asks for the longest substring without repeating characters. Which pattern applies?

›A) Two Pointers
›B) Sliding Window
›C) Prefix Sum
›D) Binary Search

Answer: B) Sliding Window. "Longest substring" with a validity condition (no repeating characters) is the defining variable sliding window signal. Expand right until a repeat appears, shrink left until the window is valid again.

Question 2: You need the Kth largest element in an unsorted array without full sorting. Which pattern applies?

›A) Backtracking
›B) Modified Binary Search
›C) Top K Elements using a Min-Heap
›D) Sliding Window

Answer: C) Top K Elements using a Min-Heap. Maintain a min-heap of size K. After processing all n elements, the heap root is the Kth largest. Cost is O(n log k) versus O(n log n) for full sorting.

Question 3: A problem asks you to generate all valid parenthesis combinations of length 2n. Which pattern applies?

›A) Dynamic Programming
›B) Sliding Window
›C) Backtracking
›D) BFS

Answer: C) Backtracking. Generating all valid combinations requires exploring a decision tree — at each step choose open or close, recurse, then undo. The constraint (open and close counts must stay valid) prunes invalid branches early.

Question 4: You have a sorted array of prices and need the minimum price such that at least K items are affordable. Which pattern applies?

›A) Prefix Sum
›B) Two Pointers
›C) Modified Binary Search on the Answer Space
›D) Top K Elements

Answer: C) Modified Binary Search on the Answer Space. Feasibility is monotonic — if price P makes K items affordable, all prices above P also do. Binary search on the price range, checking feasibility at each midpoint, finds the minimum threshold in O(n log(max price)).

Summary

These 15 patterns are the vocabulary of algorithmic problem-solving. Learning to recognize which pattern applies from the problem's input shape, output requirement, keywords, and constraints is the skill that makes interviews manageable.

The 15 patterns and their strongest signals:

›Sliding Window — contiguous subarray or substring, longest or shortest
›Prefix Sum — range sum query, count subarrays with target sum
›Two Pointers — sorted array, pairs or triplets, palindrome
›Fast and Slow Pointers — cycle detection, middle of linked list
›Linked List Reversal — reverse in-place, k-group reversal
›Monotonic Stack — next greater or smaller element, histogram
›Top K Elements — K largest, smallest, or most frequent using heap
›Overlapping Intervals — merge, count conflicts, scheduling
›Modified Binary Search — rotated sorted array, monotonic answer space
›Binary Tree Traversal — inorder, preorder, postorder, level-order
›DFS — all paths, connectivity, cycles, topological sort
›BFS — shortest path, minimum steps, level-by-level exploration
›Matrix Traversal — grid as graph, islands, flood fill, distances
›Backtracking — all combinations, subsets, placements with constraints
›Dynamic Programming — optimal value or count with overlapping subproblems

In the next topic, you will learn Brute Force to Optimization — the systematic method for improving any working solution into an efficient one by identifying and eliminating bottlenecks.

←

PreviousHow to Approach Problems

NextBrute Force to Optimal

→