Patterns in Data Structures: A Comprehensive Guide

Introduction

Data Structures and Algorithms (DSA) problems may appear endless at first glance, but most of them are built on a small set of reusable patterns. Instead of memorizing thousands of problems, understanding these core patterns allows you to recognize problem structures and apply proven solutions efficiently. This article distills the most important, non-overlapping patterns across arrays, linked lists, trees, graphs, heaps, and dynamic programming.

1. Sliding Window

Sliding Window is used when working with contiguous subarrays or substrings. Instead of recalculating results for each window, the window slides forward by adding one element and removing another.

java

public class SlidingWindow {
    public static int maxSumSubarray(int k, int[] arr) {
        int windowSum = 0, maxSum = 0, start = 0;
        for (int end = 0; end < arr.length; end++) {
            windowSum += arr[end];
            if (end >= k - 1) {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= arr[start++];
            }
        }
        return maxSum;
    }
}

2. Two Pointers

The Two Pointers pattern uses two indices moving toward each other or in the same direction. It is especially effective for sorted arrays or linked lists.

java

public class TwoPointers {
    public static boolean hasPair(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int sum = arr[l] + arr[r];
            if (sum == target) return true;
            if (sum < target) l++; else r--;
        }
        return false;
    }
}

3. Fast & Slow Pointers

Fast & Slow pointers are commonly used in linked lists to detect cycles, find middle nodes, or check palindromes.

java

class ListNode { int val; ListNode next; }
 
public class CycleDetection {
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

4. Merge Intervals

Merge Intervals solves problems involving overlapping ranges by sorting intervals and merging when overlaps occur.

java

import java.util.*;
 
public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);
        List<int[]> res = new ArrayList<>();
        int[] cur = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= cur[1])
                cur[1] = Math.max(cur[1], intervals[i][1]);
            else { res.add(cur); cur = intervals[i]; }
        }
        res.add(cur);
        return res.toArray(new int[res.size()][]);
    }
}

5. In-place Linked List Reversal

Many linked list problems require reversing nodes without using extra memory.

java

public class ReverseList {
    public static ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

6. Tree BFS & DFS

Tree traversal problems are efficiently solved using BFS for level-order logic and DFS for depth-based logic.

java

import java.util.*;
 
class TreeNode { int val; TreeNode left, right; }
 
public class TreeTraversal {
    public static void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);
    }
 
    public static void bfs(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
}

7. Heap / Top-K

Heap-based patterns are ideal when problems require finding the top or bottom K elements efficiently.

java

import java.util.*;
 
public class TopK {
    public static int[] kLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int n : nums) {
            pq.add(n);
            if (pq.size() > k) pq.poll();
        }
        return pq.stream().mapToInt(i->i).toArray();
    }
}

8. Backtracking (Subsets & Permutations)

Backtracking systematically explores all valid configurations by making a choice, exploring, and undoing it.

java

import java.util.*;
 
public class Subsets {
    public static void backtrack(int idx, int[] nums, List<Integer> cur, List<List<Integer>> res) {
        res.add(new ArrayList<>(cur));
        for (int i = idx; i < nums.length; i++) {
            cur.add(nums[i]);
            backtrack(i + 1, nums, cur, res);
            cur.remove(cur.size() - 1);
        }
    }
}

9. Graph Traversal (BFS / DFS)

Graph traversal patterns form the foundation for connectivity, shortest path, and cycle detection problems.

java

import java.util.*;
 
public class GraphDFS {
    public static void dfs(int node, List<List<Integer>> g, boolean[] vis) {
        vis[node] = true;
        for (int nei : g.get(node))
            if (!vis[nei]) dfs(nei, g, vis);
    }
}

10. Topological Sort

Topological Sort applies to Directed Acyclic Graphs (DAGs) where ordering with dependencies is required.

java

import java.util.*;
 
public class TopoSort {
    public static List<Integer> sort(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
        List<Integer> res = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll(); res.add(u);
            for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return res;
    }
}

11. Dynamic Programming

Dynamic Programming solves problems by breaking them into overlapping subproblems and storing results. Common forms include linear DP, grid DP, and knapsack-style DP.

java

public class ClimbingStairs {
    public static int climb(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int c = a + b; a = b; b = c;
        }
        return b;
    }
}

Conclusion

These core patterns represent the majority of real-world and interview DSA problems. Mastering them reduces problem-solving complexity dramatically. Focus on recognizing the pattern first—implementation naturally follows.