Scribd
Upload
108 views3 pages

Java DSA Patterns: 10 Essential Templates

The document outlines 10 common data structures and algorithms (DSA) patterns in Java, including DFS, BFS, Two Pointers, Fast & Slow Pointers, Sliding Window, Binary Search, Backtracking, Prefix Sum with HashMap, Union Find, and Topological Sort. Each pattern is accompanied by a brief explanation and a code template. These patterns are essential for solving various algorithmic problems efficiently.

Uploaded by

rohitsarla69
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
108 views3 pages

Java DSA Patterns: 10 Essential Templates

The document outlines 10 common data structures and algorithms (DSA) patterns in Java, including DFS, BFS, Two Pointers, Fast & Slow Pointers, Sliding Window, Binary Search, Backtracking, Prefix Sum with HashMap, Union Find, and Topological Sort. Each pattern is accompanied by a brief explanation and a code template. These patterns are essential for solving various algorithmic problems efficiently.

Uploaded by

rohitsarla69
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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 >= [Link] || 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<>();
[Link](new int[]{r, c});
while (![Link]()) {
int[] curr = [Link]();
for (int[] dir : directions) {
int nr = curr[0] + dir[0];
int nc = curr[1] + dir[1];
if (isValid(nr, nc, grid)) {
[Link](new int[]{nr, nc});
grid[nr][nc] = 0; // mark visited
}
}
}
}

3. Two Pointers

int left = 0, right = [Link] - 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 && [Link] != null) {
slow = [Link];
fast = [Link];
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 < [Link](); right++) {
char ch = [Link](right);
if ([Link](ch) && [Link](ch) >= left) {
left = [Link](ch) + 1;
}
[Link](ch, right);
maxLen = [Link](maxLen, right - left + 1);
}

6. Binary Search

int left = 0, right = [Link] - 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) {


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

8. Prefix Sum + HashMap

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


[Link](0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
if ([Link](sum - k)) count += [Link](sum - k);
[Link](sum, [Link](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) [Link](i);
}
while (![Link]()) {
int node = [Link]();
for (int neighbor : [Link](node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) [Link](neighbor);
}
}

You might also like