10 Common DSA Patterns - Java Templates

1. DFS (Depth-First Search) - Grid/Graph Traversal

void dfs(char[][] grid, int r, int c) {

if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0')
return;
grid[r][c] = '0'; // mark visited
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

2. BFS (Breadth-First Search) - Level-Order / Shortest Path

public void bfs(int[][] grid, int r, int c) {

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{r, c});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] dir : directions) {
int nr = curr[0] + dir[0];
int nc = curr[1] + dir[1];
if (isValid(nr, nc, grid)) {
queue.offer(new int[]{nr, nc});
grid[nr][nc] = 0; // mark visited
}
}
}
}

3. Two Pointers

int left = 0, right = array.length - 1;

while (left < right) {
int sum = array[left] + array[right];
if (sum == target) return true;
else if (sum < target) left++;
else right--;
}

4. Fast & Slow Pointers

ListNode slow = head, fast = head;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // cycle detected
}
return false;

5. Sliding Window

int left = 0, maxLen = 0;

Map<Character, Integer> map = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (map.containsKey(ch) && map.get(ch) >= left) {
left = map.get(ch) + 1;
}
map.put(ch, right);
maxLen = Math.max(maxLen, right - left + 1);
}

6. Binary Search

int left = 0, right = nums.length - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}

7. Backtracking

void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {

result.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
tempList.add(nums[i]);
backtrack(result, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

8. Prefix Sum + HashMap

Map<Integer, Integer> map = new HashMap<>();

map.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
if (map.containsKey(sum - k)) count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}

9. Union Find (Disjoint Set Union)

int[] parent = new int[n];

for (int i = 0; i < n; i++) parent[i] = i;

int find(int x) {
 if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}

void union(int x, int y) {

int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}

10. Topological Sort (Kahn's Algorithm - BFS)

Queue<Integer> queue = new LinkedList<>();

int[] indegree = new int[n];
for (int[] edge : prerequisites) {
indegree[edge[0]]++;
}
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) queue.offer(neighbor);
}
}