Graphs
Java solutions with explanations, time and space complexity for Graphs problems from Blind 75.
Graphs
This section covers problems involving graph algorithms and data structures.
1. Number of Islands (Medium)
Problem: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
Example:
Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3Solution:
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}Time Complexity: O(m * n) Space Complexity: O(m * n)
2. Clone Graph (Medium)
Problem: Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Example:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]Solution:
class Solution {
private Map<Node, Node> visited = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (visited.containsKey(node)) {
return visited.get(node);
}
Node cloneNode = new Node(node.val, new ArrayList<>());
visited.put(node, cloneNode);
for (Node neighbor : node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}Time Complexity: O(n) Space Complexity: O(n)
3. Pacific Atlantic Water Flow (Medium)
Problem: There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.
Example:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]Solution:
class Solution {
private int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> result = new ArrayList<>();
if (heights == null || heights.length == 0) return result;
int m = heights.length, n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
// DFS from Pacific (top and left edges)
for (int i = 0; i < m; i++) {
dfs(heights, pacific, i, 0, Integer.MIN_VALUE);
}
for (int j = 0; j < n; j++) {
dfs(heights, pacific, 0, j, Integer.MIN_VALUE);
}
// DFS from Atlantic (bottom and right edges)
for (int i = 0; i < m; i++) {
dfs(heights, atlantic, i, n - 1, Integer.MIN_VALUE);
}
for (int j = 0; j < n; j++) {
dfs(heights, atlantic, m - 1, j, Integer.MIN_VALUE);
}
// Find intersection
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
private void dfs(int[][] heights, boolean[][] visited, int i, int j, int prevHeight) {
if (i < 0 || i >= heights.length || j < 0 || j >= heights[0].length ||
visited[i][j] || heights[i][j] < prevHeight) {
return;
}
visited[i][j] = true;
for (int[] dir : directions) {
dfs(heights, visited, i + dir[0], j + dir[1], heights[i][j]);
}
}
}Time Complexity: O(m * n) Space Complexity: O(m * n)
4. Course Schedule (Medium)
Problem: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
Return true if you can finish all courses. Otherwise, return false.
Example:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: trueSolution:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
graph.get(prerequisite[1]).add(prerequisite[0]);
}
boolean[] visited = new boolean[numCourses];
boolean[] recStack = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!visited[i] && hasCycle(graph, i, visited, recStack)) {
return false;
}
}
return true;
}
private boolean hasCycle(List<List<Integer>> graph, int node, boolean[] visited, boolean[] recStack) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor] && hasCycle(graph, neighbor, visited, recStack)) {
return true;
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
}Time Complexity: O(V + E) Space Complexity: O(V + E)
5. Graph Valid Tree (Medium)
Problem: Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Example:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: trueSolution:
class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
// Check if connected and no cycles
return !hasCycle(graph, 0, -1, visited) && allVisited(visited);
}
private boolean hasCycle(List<List<Integer>> graph, int node, int parent, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (hasCycle(graph, neighbor, node, visited)) {
return true;
}
} else if (neighbor != parent) {
return true;
}
}
return false;
}
private boolean allVisited(boolean[] visited) {
for (boolean v : visited) {
if (!v) return false;
}
return true;
}
}Time Complexity: O(V + E) Space Complexity: O(V + E)
6. Number of Connected Components in an Undirected Graph (Medium)
Problem: You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return the number of connected components in the graph.
Example:
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2Solution:
class Solution {
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
count++;
}
}
return count;
}
private void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
}Time Complexity: O(V + E) Space Complexity: O(V + E)
Key Takeaways
- DFS/BFS: Use depth-first or breadth-first search for graph traversal
- Cycle Detection: Use visited arrays and recursion stacks
- Connected Components: Count components by exploring unvisited nodes
- Topological Sort: Use for dependency resolution
- Union Find: Alternative approach for connected components