DSA Patterns Sheet in Java: 15 Patterns That Solve Most Coding Interview Problems

DSA patterns are the 15 or so reusable problem-solving shapes, such as two pointers, sliding window, BFS and dynamic programming, that sit underneath most coding interview questions. Once you can spot the pattern from the wording of a problem, you stop trying to memorize hundreds of solutions. You recognize the shape, write a template you already know, and adapt it.

This DSA sheet is for Java developers preparing for campus placements or product-company interviews, from freshers to engineers with a few years of experience. For each of the 15 patterns you get the signal words that give it away, a short Java template, its time and space complexity, and 4-6 classic LeetCode problems to practice it, easiest first. We compiled and ran every template on Java 25 and show the real results. The guide ends with an 8-week DSA roadmap for placements that teaches the patterns in an order where each week builds on the last.

The templates use plain java.util classes. Two of them call getLast() and removeLast() on a List, which arrived with sequenced collections in Java 21; on older Java, use list.get(list.size() - 1) and list.remove(list.size() - 1).

In this guide

• Why learn DSA patterns instead of grinding problems
• How to recognize the right pattern (the pattern picker)
• Array and string patterns: two pointers, sliding window, prefix sum, hashing, binary search
• Linked list, stack and heap patterns: fast and slow pointers, monotonic stack, top-K
• Interval and greedy patterns
• Graph patterns: BFS and DFS, topological sort, union-find
• Recursion patterns: backtracking and dynamic programming
• An 8-week DSA roadmap for placements
• How to practice so the patterns stick, plus an FAQ

Why learn DSA patterns instead of grinding problems?

Interviewers rarely ask a problem you have seen word for word. They ask a variation: a different story wrapped around a familiar structure. Number of Islands, Rotting Oranges and Word Ladder look nothing alike on the page, yet all three are a breadth-first or depth-first search over a graph. If you only memorized the solution to Number of Islands, the other two feel new. If you learned the BFS pattern, they are the same problem with a different neighbor function.

That mapping step, from story to structure, is exactly what an interviewer watches in the first five minutes. A candidate who says "the input is sorted and we need a pair, so two pointers gives O(n) with O(1) space" has already shown more than one who writes a correct but unexplained nested loop. Patterns give you that opening sentence, a known-good skeleton to code from, and a complexity you can state with confidence.

Patterns are not a replacement for practice. You still need 150-200 well-chosen problems to make them automatic. The difference is that each problem now reinforces a pattern instead of being a one-off fact.

How to recognize the right pattern

Read the problem once for the story and a second time for signals: the shape of the input (sorted array, string, grid, list of edges), the shape of the question (longest, minimum, count, all, K-th), and the constraints. The chart below maps the most common signals to the pattern that usually solves them.

The same mapping as a list:

• Sorted array, find a pair or triplet → two pointers
• Longest or shortest contiguous subarray or substring with a rule → sliding window
• Subarray sum equals K, range sums, negatives allowed → prefix sum with a hash map
• Sorted data, or "smallest X that works" where a bigger X always works too → binary search (on the answer)
• K largest, K most frequent, K closest, running median → heap (top-K)
• Next greater or smaller element, spans, histograms → monotonic stack
• Linked list cycle, middle node, repeating sequence → fast and slow pointers
• Meetings, bookings, overlapping ranges → intervals (sort, then sweep)
• "Have I seen this before?", counting, grouping → hashing
• Grid cells, regions, minimum moves → BFS or DFS
• Prerequisites, build order, dependencies → topological sort
• Connected groups, merging sets, redundant edges → union-find
• Generate all combinations, permutations or placements → backtracking
• Count ways, minimum cost, overlapping subproblems → dynamic programming
• A locally best choice is always safe → greedy

Constraints are the second clue. With n up to about 20, an exponential backtracking solution is usually acceptable. With n up to 10⁵ or 10⁶ you need O(n log n) or better, which rules out nested loops and points to sorting, two pointers, a window, a heap or a hash map. The Big-O cheat sheet has a table of how each complexity grows, so you can do this check in seconds.

Array and string patterns

Most first-round questions are about arrays and strings, and five patterns cover nearly all of them.

1. Two pointers

Recognize it: the array or string is sorted (or you can sort it), and you need a pair or triplet that meets a target, a palindrome check, or an in-place rearrangement such as removing duplicates.

Put one pointer at each end. If the sum is too small, the left value is too small for every remaining partner, so move left forward. If the sum is too big, the right value is too big for every remaining partner, so move right back. Each step throws away one candidate for good, which is why the whole scan is linear.

static int[] twoSumSorted(int[] a, int target) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) return new int[] {left, right};
        if (sum < target) left++;   // need a bigger sum
        else right--;               // need a smaller sum
    }
    return new int[] {-1, -1};
}
// twoSumSorted([1, 3, 4, 6, 8, 11], 10) -> [2, 3]

Complexity: O(n) time, O(1) extra space. If the input is unsorted, sorting first makes it O(n log n). 3Sum fixes one element and runs two pointers on the rest, giving O(n²). A second flavor moves both pointers in the same direction: a slow "write" index and a fast "read" index, used to remove duplicates or move zeros in place.

Practice:

1. Valid Palindrome
2. Two Sum II - Input Array Is Sorted
3. Remove Duplicates from Sorted Array
4. 3Sum
5. Container With Most Water
6. Trapping Rain Water

2. Sliding window

Recognize it: the question is about a contiguous subarray or substring and asks for the longest, shortest, maximum or a count, under a rule such as "no repeated characters", "at most K distinct" or "sum at least S".

The window is the range between two indexes. Grow it by moving right one step at a time. When the window breaks the rule, shrink it from the left until it is valid again. Record the best answer after each step. Every index enters the window once and leaves at most once, so the work is linear even though there are two loops' worth of movement.

// Variable-size window: longest substring without repeating characters
static int longestUniqueSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer prev = lastSeen.put(c, right);
        if (prev != null && prev >= left) left = prev + 1; // shrink past the duplicate
        best = Math.max(best, right - left + 1);
    }
    return best;
}
// longestUniqueSubstring("abcabcbb") -> 3

// Fixed-size window: maximum sum of k consecutive elements
static int maxSumOfK(int[] a, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) window += a[i];
    int best = window;
    for (int right = k; right < a.length; right++) {
        window += a[right] - a[right - k]; // add the new element, drop the oldest
        best = Math.max(best, window);
    }
    return best;
}
// maxSumOfK([2, 1, 5, 1, 3, 2], 3) -> 9

Complexity: O(n) time. Space is O(1) for sums, or O(k) / O(alphabet size) for the map of what is inside the window.

Common mistake: using a sum-based window when the array has negative numbers. Shrinking the window no longer reliably lowers the sum, so the logic breaks. That is the moment to switch to a prefix sum.

Practice:

1. Maximum Average Subarray I (fixed window)
2. Longest Substring Without Repeating Characters
3. Minimum Size Subarray Sum
4. Longest Repeating Character Replacement
5. Permutation in String
6. Minimum Window Substring

3. Prefix sum

Recognize it: many range-sum queries on a fixed array, "count subarrays whose sum equals K", "longest subarray with equal 0s and 1s", or any subarray-sum question where values can be negative.

The sum of a[i..j] equals prefix[j + 1] - prefix[i]. For counting questions, walk the array once with a running sum and a hash map of how many times each earlier prefix sum has appeared. A subarray ending here sums to K exactly when an earlier prefix equals prefix - k.

static int countSubarraysWithSum(int[] a, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);                       // empty prefix
    int prefix = 0, count = 0;
    for (int x : a) {
        prefix += x;
        count += seen.getOrDefault(prefix - k, 0);
        seen.merge(prefix, 1, Integer::sum);
    }
    return count;
}
// countSubarraysWithSum([1, 2, 3, -2, 2], 3) -> 4
// ([1, 2], [3], [2, 3, -2] and [3, -2, 2])

Complexity: O(n) time and O(n) space. Forgetting the seen.put(0, 1) seed is the classic bug: it misses every subarray that starts at index 0. For large values, keep the running sum in a long.

Practice:

1. Range Sum Query - Immutable
2. Product of Array Except Self (prefix and suffix products)
3. Subarray Sum Equals K
4. Contiguous Array
5. Subarray Sums Divisible by K

4. Hashing

Recognize it: "have we seen this value before?", counting frequencies, grouping items that share a key (anagrams), or finding a complement in an unsorted array. Hashing is also the standard fix whenever your brute force has an inner loop that only searches for something.

static int longestConsecutive(int[] a) {
    Set<Integer> set = new HashSet<>();
    for (int x : a) set.add(x);
    int best = 0;
    for (int x : set) {
        if (set.contains(x - 1)) continue;  // only start counting at the start of a run
        int len = 1;
        while (set.contains(x + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}
// longestConsecutive([100, 4, 200, 1, 3, 2]) -> 4   (1, 2, 3, 4)

The trick that makes this linear: only start counting from a number whose predecessor is missing. Each value is then visited by at most one inner run.

Complexity: O(n) average time, O(n) space. Hash operations are O(1) on average; the HashMap internals guide explains collisions, resizing and the tree bins that limit the damage when many keys collide.

Practice:

1. Two Sum
2. Valid Anagram
3. Group Anagrams
4. Longest Consecutive Sequence

5. Binary search (including binary search on the answer)

Recognize it: sorted input, "first or last position of", a rotated sorted array, or the phrasing "minimum X such that..." / "maximum X such that...". The second family is binary search on the answer: you cannot search the input, but you can test a candidate answer cheaply, and once a candidate works, every bigger one works too.

Take Koko Eating Bananas: piles [3, 6, 7, 11], 8 hours. Speeds 1 to 3 are too slow and 4 to 11 all finish in time. The yes/no answers form a single step, and binary search finds the first "yes".

static int minEatingSpeed(int[] piles, int hours) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;          // avoids int overflow
        if (hoursNeeded(piles, mid) <= hours) hi = mid; // mid works: try smaller
        else lo = mid + 1;                             // too slow: go bigger
    }
    return lo;
}

static long hoursNeeded(int[] piles, int speed) {
    long h = 0;
    for (int p : piles) h += (p + speed - 1) / speed; // ceil(p / speed)
    return h;
}
// minEatingSpeed([3, 6, 7, 11], 8) -> 4

Complexity: O(log n) for a classic search. On the answer it is O(n log M), where M is the size of the answer range and each check costs O(n).

Common mistakes: (lo + hi) / 2 can overflow an int; mixing up lo < hi with lo <= hi; and writing lo = mid, which loops forever when hi = lo + 1. Pick one template (the "find the first true" version above works for nearly everything) and use it every time.

Practice:

1. Binary Search
2. Find First and Last Position of Element in Sorted Array
3. Search in Rotated Sorted Array
4. Find Minimum in Rotated Sorted Array
5. Capacity To Ship Packages Within D Days
6. Split Array Largest Sum

Linked list, stack and heap patterns

6. Fast and slow pointers

Recognize it: detect a cycle in a linked list, find its middle, check whether a number sequence repeats (Happy Number), or find a duplicate in an array whose values point to indexes.

Move slow one step and fast two steps. If there is a cycle, fast laps slow and they meet inside it. If there is no cycle, fast reaches the end, and at that moment slow is at the middle.

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

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

static Node middle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
// middle(1 -> 2 -> 3 -> 4 -> 5) -> 3
// hasCycle(1 -> 2 -> 3 -> 4 -> 5) -> false; after linking 5 back to 2 -> true

Complexity: O(n) time and O(1) space. The O(1) space is the point: a HashSet of visited nodes also detects a cycle, but costs O(n) memory, and interviewers usually ask for the follow-up without it.

Practice:

1. Middle of the Linked List
2. Linked List Cycle
3. Happy Number
4. Palindrome Linked List
5. Linked List Cycle II
6. Find the Duplicate Number

7. Monotonic stack

Recognize it: "next greater element", "how many days until a warmer temperature", stock spans, or the largest rectangle in a histogram. Anything where each element waits for the first later element that beats it.

Keep a stack of indexes whose answer is still unknown, with their values in non-increasing order from bottom to top. When a bigger value arrives, it is the answer for every smaller value on top of the stack, so pop them and fill in their answers.

static int[] dailyTemperatures(int[] t) {
    int[] answer = new int[t.length];
    Deque<Integer> stack = new ArrayDeque<>(); // indexes; temperatures never increase toward the top
    for (int i = 0; i < t.length; i++) {
        while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
            int j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    return answer;
}
// dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) -> [1, 1, 4, 2, 1, 1, 0, 0]

Complexity: O(n) time even with the inner while, because each index is pushed once and popped at most once. O(n) space. In Java, use ArrayDeque as the stack; the legacy Stack class extends Vector and synchronizes every call.

Practice:

1. Valid Parentheses (plain stack warm-up)
2. Next Greater Element I
3. Daily Temperatures
4. Online Stock Span
5. Largest Rectangle in Histogram
6. Sliding Window Maximum (the monotonic deque variant)

8. Heap and top-K

Recognize it: the K largest, smallest, most frequent or closest items; the K-th element; merging K sorted lists; a running median; always processing the most urgent item next.

For the K largest, keep a min-heap of size K. Push each element and, when the heap grows past K, pop the smallest. What survives is the K largest, and the root is the K-th largest.

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int x : a) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll(); // throw away the smallest
    }
    return minHeap.peek();
}
// kthLargest([3, 2, 1, 5, 6, 4], 2) -> 5

Complexity: O(n log k) time and O(k) space, better than sorting (O(n log n)) when K is small. Java's PriorityQueue is a min-heap by default. For a max-heap use new PriorityQueue<>(Comparator.reverseOrder()), and in custom comparators prefer Integer.compare(a, b) over a - b, which can overflow.

Practice:

1. Kth Largest Element in an Array
2. Top K Frequent Elements
3. K Closest Points to Origin
4. Task Scheduler
5. Merge k Sorted Lists
6. Find Median from Data Stream (two heaps)

Interval and greedy patterns

9. Intervals: sort, then sweep

Recognize it: meetings, bookings, time ranges, "merge overlapping", "insert into a list of ranges", "minimum number of rooms or arrows".

Sort by start time. Then walk once: if the next interval starts after the last merged one ends, it is a new block; otherwise it overlaps, so extend the end.

static int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] iv : intervals) {
        if (merged.isEmpty() || merged.getLast()[1] < iv[0]) merged.add(iv);
        else merged.getLast()[1] = Math.max(merged.getLast()[1], iv[1]);
    }
    return merged.toArray(new int[0][]);
}
// mergeIntervals([[1,3], [8,10], [2,6], [15,18]]) -> [[1, 6], [8, 10], [15, 18]]

Complexity: O(n log n) for the sort plus O(n) for the sweep; O(n) for the output. When the goal is to keep the most non-overlapping intervals, sort by end time instead. That is the greedy activity-selection rule.

Practice:

1. Merge Intervals
2. Insert Interval
3. Non-overlapping Intervals
4. Minimum Number of Arrows to Burst Balloons
5. Interval List Intersections

10. Greedy

Recognize it: "minimum number of steps", "maximum number of items", where taking the best-looking option right now can never hurt you later. Greedy solutions often start with a sort.

static boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;        // stuck before index i
        reach = Math.max(reach, i + nums[i]);
    }
    return true;
}
// canJump([2, 3, 1, 1, 4]) -> true, canJump([3, 2, 1, 0, 4]) -> false

Complexity: usually O(n), or O(n log n) with a sort.

The trap: greedy needs a reason to be right. "Take the biggest coin first" works for coins 1, 2 and 5, but with coins 1, 3 and 4 and amount 6 it picks 4 + 1 + 1 (three coins) while 3 + 3 (two coins) is optimal. When you cannot argue why the local choice is safe, reach for dynamic programming.

Practice:

1. Best Time to Buy and Sell Stock
2. Maximum Subarray (Kadane's algorithm)
3. Jump Game
4. Jump Game II
5. Gas Station
6. Partition Labels

Graph patterns

11. BFS and DFS on grids and graphs

Recognize it: a grid of cells, islands or regions, "connected", tree traversals, and above all "minimum number of steps or moves" in an unweighted graph, which is always BFS.

DFS goes deep first and is the shortest code for "visit everything reachable" (count islands, flood fill). BFS explores level by level, so the first time it reaches a cell is along a shortest path.

// DFS: count islands of '1' cells
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') { count++; sink(grid, r, c); }
    return count;
}

static void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';                          // mark visited
    sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}

// BFS: fewest steps from top-left to bottom-right (0 = open, 1 = wall)
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

static int shortestPath(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    if (grid[0][0] == 1) return -1;
    boolean[][] seen = new boolean[rows][cols];
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[] {0, 0});
    seen[0][0] = true;
    for (int steps = 0; !queue.isEmpty(); steps++) {
        for (int size = queue.size(); size > 0; size--) { // one BFS level = one step
            int[] cell = queue.poll();
            if (cell[0] == rows - 1 && cell[1] == cols - 1) return steps;
            for (int[] d : DIRS) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && c >= 0 && r < rows && c < cols && !seen[r][c] && grid[r][c] == 0) {
                    seen[r][c] = true;
                    queue.offer(new int[] {r, c});
                }
            }
        }
    }
    return -1;
}
// numIslands on the 4 x 5 grid 11000 / 11000 / 00100 / 00011 -> 3
// shortestPath on {{0,0,0},{1,1,0},{0,0,0}} -> 4

Complexity: O(V + E) time and O(V) space; for a grid that is O(rows × cols). Two bugs to avoid: mark a cell as seen when you enqueue it, not when you dequeue it, or the same cell enters the queue many times; and recursive DFS on a very large grid can throw StackOverflowError, so switch to an explicit stack if the grid can be huge.

Practice:

1. Number of Islands
2. Rotting Oranges (multi-source BFS)
3. Shortest Path in Binary Matrix (8 directions instead of 4)
4. Clone Graph
5. Pacific Atlantic Water Flow
6. Word Ladder

12. Topological sort

Recognize it: prerequisites, dependencies, build or install order, "can all tasks be finished?". The graph is directed, and a valid order exists only if it has no cycle.

Kahn's algorithm: count incoming edges for each node, start a queue with every node that has none, and repeatedly remove a node and decrement its neighbors. If fewer than n nodes come out, the leftovers form a cycle.

static List<Integer> courseOrder(int n, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] p : prerequisites) {         // p = [course, prerequisite]
        graph.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : graph.get(u)) if (--indegree[v] == 0) queue.offer(v);
    }
    return order.size() == n ? order : List.of(); // empty list = cycle
}
// courseOrder(4, [[1,0], [2,0], [3,1], [3,2]]) -> [0, 1, 2, 3]
// courseOrder(2, [[0,1], [1,0]]) -> []   (cycle)

Complexity: O(V + E) time and space. A DFS with three node colors (unvisited, in progress, done) also works and detects cycles when it meets an in-progress node.

Practice:

1. Course Schedule
2. Course Schedule II
3. Find Eventual Safe States
4. Minimum Height Trees (leaf trimming, the same idea on an undirected tree)
5. Longest Increasing Path in a Matrix

13. Union-find (disjoint set union)

Recognize it: group things that become connected over time, answer "are these two connected?", find the edge that creates a cycle, merge accounts that share an email, or build a minimum spanning tree with Kruskal's algorithm.

static final class UnionFind {
    private final int[] parent, size;
    int components;

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];  // path halving
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;          // already connected: this edge makes a cycle
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                     // attach the smaller tree under the bigger
        size[ra] += size[rb];
        components--;
        return true;
    }
}
// 5 nodes, union(0,1), union(1,2), union(3,4) -> components = 2
// union(0,2) again -> false (0 and 2 were already connected)

Complexity: with path compression (here, path halving) and union by size, each operation costs O(α(n)) amortized, where α is the inverse Ackermann function. It is below 5 for any input you will ever see, so treat it as constant. Space is O(n).

Practice:

1. Number of Provinces
2. Redundant Connection
3. Number of Operations to Make Network Connected
4. Accounts Merge
5. Min Cost to Connect All Points (Kruskal)

Recursion patterns: backtracking and dynamic programming

14. Backtracking

Recognize it: the words "all", "every" or "generate": all subsets, permutations, combinations that sum to a target, ways to place N queens, words in a grid. Small limits (n up to about 15-20) are a strong hint that an exponential search is expected.

Every backtracking solution has the same three moves: choose an option, explore everything that follows from it, then un-choose it before trying the next option.

static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));       // record a copy, not the live list
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                   // choose
        backtrack(nums, i + 1, path, result); // explore
        path.removeLast();                   // un-choose
    }
}
// subsets([1, 2, 3]) -> [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Complexity: subsets are O(n · 2ⁿ) and permutations O(n · n!), because that is how much output there is. Speed comes from pruning: stop a branch as soon as it cannot lead to a valid answer. The most common bug is adding path itself instead of a copy, which leaves you with a list of empty lists.

Practice:

1. Subsets
2. Permutations
3. Combination Sum
4. Palindrome Partitioning
5. Word Search
6. N-Queens

15. Dynamic programming (1D and 2D)

Recognize it: count the ways, find the minimum cost or the maximum value, or decide whether something is possible, where each step is a choice and a plain recursive solution would solve the same smaller problem many times.

Use the same five-step recipe every time: define the state (what dp[i] or dp[i][j] means in words), write the recurrence, set the base cases, choose the fill order, and say where the answer lives.

// 1D: fewest coins that make the amount
static int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];          // dp[x] = fewest coins that make x
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int coin : coins)
            if (coin <= x && dp[x - coin] != Integer.MAX_VALUE)
                dp[x] = Math.min(dp[x], dp[x - coin] + 1);
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// coinChange([1, 2, 5], 11) -> 3   (5 + 5 + 1)

// 2D: longest common subsequence
static int lcs(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++)
        for (int j = 1; j <= b.length(); j++)
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[a.length()][b.length()];
}
// lcs("abcde", "ace") -> 3

Complexity: number of states × work per state. Coin Change is O(amount × coins) time and O(amount) space; LCS is O(m × n) time and space, and the space drops to O(n) if you keep only the previous row. If the bottom-up table feels unnatural, write the recursive solution first and add a memo map. That top-down version has the same complexity and is perfectly acceptable in an interview.

Practice:

1. Climbing Stairs
2. House Robber
3. Coin Change
4. Unique Paths (2D)
5. Longest Increasing Subsequence
6. Longest Common Subsequence (2D), then Edit Distance (2D)

What about tries, Dijkstra and bit manipulation?

They matter, but they come up less often than the 15 above, so learn them after the core set:

• Trie: prefix search and autocomplete; start with Implement Trie (Prefix Tree).
• Dijkstra: shortest path when edges have weights. It is BFS with a PriorityQueue instead of a plain queue; try Network Delay Time.
• Bit manipulation: XOR tricks (find the single number), subsets as bitmasks, counting set bits with Integer.bitCount.
• Two heaps, cyclic sort, segment and Fenwick trees: useful for specific problem families; add them once the core patterns feel automatic.

DSA roadmap for placements: an 8-week study plan

This order puts every pattern after the ideas it depends on: hashing before prefix sums, BFS before topological sort, recursion before dynamic programming. Plan for about 2 hours a day and 2-3 problems, more on weekends.

1. Week 1: arrays, strings and hashing. Get fluent with HashMap, HashSet, Arrays.sort and StringBuilder. Patterns: hashing, two pointers. Learn to state the time and space complexity of everything you write.
2. Week 2: sliding window and prefix sum. Fixed windows first, then variable windows, then prefix sums for the cases a window cannot handle.
3. Week 3: binary search, sorting and intervals. One binary search template for sorted arrays, rotated arrays and search on the answer. Merge, insert and count intervals.
4. Week 4: linked lists and stacks. Reversal, merging, fast and slow pointers; stack basics, then the monotonic stack.
5. Week 5: trees and heaps. Recursive and level-order traversals, height, lowest common ancestor and BST checks. Then PriorityQueue problems: top-K, merge K lists, the running median.
6. Week 6: graphs. Adjacency lists, BFS and DFS on grids, topological sort, union-find. Dijkstra if time allows.
7. Week 7: backtracking and greedy. Subsets, permutations, combination sum; then greedy problems, checking each time why the greedy choice is safe.
8. Week 8: dynamic programming and mock interviews. 1D problems first, then 2D grids and strings. Finish with timed mock rounds that mix every pattern.

Only have four weeks? Pair the weeks up (1+2, 3+4, 5+6, 7+8), keep the two or three easiest problems per pattern, and skip the bonus topics. Not preparing for placements but for an experienced role? The same order works; spend less time on week 1 and more on graphs and DP, and expect system design rounds alongside.

How to practice DSA patterns so they stick

• Practice by pattern, then mix. Do one pattern's problems back to back until the template feels obvious, then shuffle problems from several patterns so you practice the recognition step, not just the coding.
• Time-box each attempt. Give a new problem 25-40 minutes. If you are stuck, read the approach (not the code), close it, and write the solution yourself. Re-solve it from scratch three days later.
• Write the template from memory. The next morning, write yesterday's template on paper without looking. If you cannot, you have not learned it yet.
• Keep a mistake log. One line per bug: "forgot seen.put(0, 1)", "marked visited on dequeue". Revise the log before every interview. Our guide on DSA handwritten notes shows a format that works.
• Talk while you code. Say the pattern, the complexity and the edge cases (empty input, one element, duplicates, negative numbers, overflow) out loud. That is what the interviewer is scoring.

A few Java details trip people up in coding rounds, so keep them in mind:

• Compare Integer values from a map with equals, not ==. Boxed values outside the small cached range (-128 to 127 by default) are separate objects, so == can return false for equal numbers.
• Use ArrayDeque for both stacks and queues; avoid Stack and avoid LinkedList unless you need nulls.
• Use Integer.compare or Comparator.comparingInt in comparators instead of subtraction.
• Use c - 'a' to index a 26-slot int[] counter; it is faster and simpler than a map of characters.
• Watch for int overflow in sums and products; switch to long early.

Practice with the full question bank

If you want the patterns in a format you can revise from, two TechTriber resources go with this sheet:

• Master Data Structures & Algorithms with Our Handwritten Notes: concise handwritten DSA notes with flowcharts and diagrams, built for product-company interview prep and quick revision.
• Top 100 Java Coding Interview Programs with Solutions: the 100 coding problems asked most in Java interviews, each with the optimal approach, complexity, edge cases and verified Java code.

Related reading

• Big-O cheat sheet: time and space complexity of data structures and algorithms
• Common data structures and algorithms interview questions
• DSA handwritten notes: how to make notes you actually revise

FAQ

How many DSA patterns are there?

There is no official number. Popular lists range from about a dozen to 25 or more, depending on how finely they split things (for example, whether "two heaps" counts separately from "top-K"). The 15 in this sheet cover the large majority of interview questions; tries, Dijkstra and bit manipulation are the next layer.

Which DSA patterns are most important for placements?

For campus placements and service-company coding rounds: hashing, two pointers, sliding window, prefix sum, binary search and basic recursion. Product companies add BFS and DFS, heaps, topological sort and dynamic programming. Learn them in the order of the 8-week plan above.

Is Java a good language for DSA and coding interviews?

Yes. Java's collections (HashMap, ArrayDeque, PriorityQueue, TreeMap) cover every pattern here, and its explicit types make your solution easy for an interviewer to follow. It is a little more verbose than Python, so practice typing the common templates until they are quick.

How long does it take to learn DSA patterns?

With about 2 hours a day, 8 weeks is enough to learn all 15 and solve 150-200 problems. If you already know the basic data structures, 4-6 weeks of focused practice is realistic. Keep revising after that, because recognition fades without use.

Are LeetCode patterns enough to crack product company interviews?

They are enough for the coding rounds if you can apply them under time pressure and explain your complexity. Experienced roles also have system design, low-level design and Java or Spring Boot rounds, so patterns are necessary but not sufficient.

Should I learn dynamic programming before graphs?

Learn recursion and backtracking first, then graphs, then dynamic programming. DP is easiest once you are comfortable thinking recursively, and graph problems give you plenty of recursion practice along the way.