Graphs
Theory and Traversals
Traversal Techniques
Depth First Search (DFS)
Implements Depth First Search (DFS) for a graph. It uses a recursive helper function to traverse the graph, marking visited nodes and adding them to the result list.
Time Complexity: O(V + E)
Space Complexity: O(V) for the visited array and recursion stack.
Breadth First Search (BFS)
Implements Breadth First Search (BFS) for a graph. It uses a queue to explore the graph level by level, marking visited nodes and adding them to the result list.
Time Complexity: O(V + E)
Space Complexity: O(V) for the visited array and the queue.
class Solution {
public List<Integer> dfsOfGraph(int V, List<List<Integer>> adj) {
List<Integer> res = new ArrayList<>();
boolean[] vis = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
dfs(i, adj, vis, res);
}
return res;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] vis, List<Integer> dfsPath) {
vis[node] = true;
dfsPath.add(node);
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis, dfsPath);
}
}
public List<Integer> bfsOfGraph(int V, List<List<Integer>> adj) {
List<Integer> res = new ArrayList<>();
boolean[] vis = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
bfs(i, adj, vis, res);
}
return res;
}
private void bfs(int node, List<List<Integer>> adj, boolean[] vis, List<Integer> bfsPath) {
Deque<Integer> q = new ArrayDeque<>();
vis[node] = true;
q.offer(node);
while (!q.isEmpty()) {
int curr = q.poll();
bfsPath.add(curr);
for (int nbr : adj.get(curr)) {
if (vis[nbr]) continue;
vis[nbr] = true;
q.offer(nbr);
}
}
}
}Connected Components
Finds the number of connected components in an undirected graph using Depth First Search (DFS). It iterates through all vertices, and if an unvisited vertex is found, it increments the component count and performs a DFS traversal from that vertex to mark all reachable vertices as visited.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the visited array and recursion stack.
class Solution {
public int findNumberOfComponent(int V, List<List<Integer>> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adj.add(new ArrayList<>());
}
for (List<Integer> e : edges) {
int u = e.get(0);
int v = e.get(1);
adj.get(u).add(v);
adj.get(v).add(u);
}
int res = 0;
boolean[] vis = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
++res;
dfs(i, adj, vis);
}
return res;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] vis) {
vis[node] = true;
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis);
}
}
}Traversal Problems
Number of provinces
Uses Depth First Search (DFS) to count the number of provinces (connected components) in a given adjacency matrix. It iterates through each city, and if the city hasn't been visited, it increments the province count and performs a DFS from that city to mark all connected cities as visited.
Time Complexity: O(V^2) because of iterating through the adjacency matrix to build the adjacency list and then O(V + E) for DFS, where E can be up to V^2 in a dense graph.
Space Complexity: O(V^2) for the adjacency list (in the worst case) and O(V) for the visited array and recursion stack.
class Solution {
public int numProvinces(int[][] adjMat) {
int v = adjMat.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < v; ++i) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < v; ++i) {
for (int j = 0; j < v; ++j) {
if (adjMat[i][j] != 1) continue;
adj.get(i).add(j);
adj.get(j).add(i);
}
}
int res = 0;
boolean[] vis = new boolean[v];
for (int i = 0; i < v; ++i) {
if (vis[i]) continue;
++res;
dfs(i, adj, vis);
}
return res;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] vis) {
vis[node] = true;
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis);
}
}
}Number of islands
Counts the number of islands in a 2D binary grid using Depth First Search (DFS). It iterates through each cell, and if a '1' (land) is found and it hasn't been visited, it increments the island count and performs a DFS from that cell to mark all connected land cells as visited.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the recursion stack (if the entire grid is one island).
class Solution {
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int res = 0;
boolean[][] vis = new boolean[n][m];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis[i][j]) continue;
if (grid[i][j] == '0') continue;
++res;
dfs(i, j, grid, vis);
}
}
return res;
}
private void dfs(int x, int y, char[][] grid, boolean[][] vis) {
int n = grid.length;
int m = grid[0].length;
vis[x][y] = true;
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
int nx = x + i;
int ny = y + j;
if(!isValid(nx, ny, n, m)) continue;
if (grid[nx][ny] == '0') continue;
if (vis[nx][ny]) continue;
dfs(nx, ny, grid, vis);
}
}
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Flood fill algorithm
Implements a flood fill algorithm on a 2D image. Starting from a given seed pixel (sr, sc), it changes the color of all connected pixels of the same initial color to a new specified color. It typically uses DFS or BFS to traverse connected pixels.
Time Complexity: O(rows * cols) as each pixel is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the recursion stack (DFS) or queue (BFS).
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int n = image.length;
int m = image[0].length;
int oldColor = image[sr][sc];
if (oldColor == newColor) return image;
dfs(sr, sc, image, oldColor, newColor);
return image;
}
private void dfs(int x, int y, int[][] image, int oldColor, int newColor) {
int n = image.length;
int m = image[0].length;
image[x][y] = newColor;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (image[nx][ny] != oldColor) continue;
dfs(nx, ny, image, oldColor, newColor);
}
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Number of enclaves
Counts the number of land cells ('1's) in a 2D binary matrix that are "enclosed", meaning they cannot reach any boundary land cell by moving horizontally or vertically. It identifies land cells connected to the boundary using DFS/BFS and then counts the remaining land cells.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the recursion stack (DFS) or queue (BFS).
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int numberOfEnclaves(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
boolean[][] vis = new boolean[n][m];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis[i][j]) continue;
if (grid[i][j] == 0) continue;
if (!isBoundary(i, j, n, m)) continue;
dfs(i, j, grid, vis);
}
}
int res = 0;
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
if (grid[i][j] == 0) continue;
if (vis[i][j]) continue;
++res;
}
}
return res;
}
private void dfs(int x, int y, int[][] grid, boolean[][] vis) {
int n = grid.length;
int m = grid[0].length;
vis[x][y] = true;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (vis[nx][ny]) continue;
if (grid[nx][ny] == 0) continue;
dfs(nx, ny, grid, vis);
}
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
private boolean isBoundary(int x, int y, int n, int m) {
return (x == 0 || x == n - 1) || (y == 0 || y == m - 1);
}
}Rotten Oranges
Finds the minimum time required for all fresh oranges in a grid to rot. Rotten oranges contaminate adjacent fresh oranges in one minute. This problem is solved using a multi-source BFS where initially all rotten oranges are added to the queue.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the queue.
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int orangesRotting(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int minutes = 0;
boolean[][] vis = new boolean[n][m];
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] != 2) continue;
vis[i][j] = true;
q.offer(new int[]{i, j});
}
}
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
int[] node = q.poll();
int x = node[0];
int y = node[1];
grid[x][y] = 2;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (vis[nx][ny]) continue;
if (grid[nx][ny] != 1) continue;
vis[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
if (!q.isEmpty()) ++minutes;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) return -1;
}
}
return minutes;
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Distance of nearest cell having one
Given a binary matrix, finds the distance of the nearest '1' for each cell. This is a multi-source BFS problem where all cells containing '1' are initially added to the queue, and BFS is performed to find the shortest distance to a '1' for all other cells.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the queue and distance matrix.
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int[][] nearest(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] res = new int[n][m];
for (int i = 0; i < n; ++i) {
Arrays.fill(res[i] , 10000);
}
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] != 1) continue;
res[i][j] = 0;
q.offer(new int[]{i, j});
}
}
int distance = 1;
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
int[] node = q.poll();
int x = node[0];
int y = node[1];
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (res[nx][ny] <= distance) continue;
res[nx][ny] = distance;
q.offer(new int[]{nx, ny});
}
}
++distance;
}
return res;
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Surrounded Regions
Given an m x n matrix board containing 'X' and 'O', captures all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. This is done by identifying 'O's on the boundary and 'O's connected to them (which cannot be surrounded) using DFS/BFS, and then flipping all remaining 'O's.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the recursion stack (DFS) or queue (BFS).
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public char[][] fill(char[][] mat) {
int n = mat.length;
int m = mat[0].length;
boolean[][] vis = new boolean[n][m];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (mat[i][j] == 'X') continue;
if (vis[i][j]) continue;
if (!isBoundary(i, j, n, m)) continue;
dfs(i, j, mat, vis);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (mat[i][j] == 'X') continue;
if (vis[i][j]) continue;
mat[i][j] = 'X';
}
}
return mat;
}
private void dfs(int x, int y, char[][] mat, boolean[][] vis) {
int n = mat.length;
int m = mat[0].length;
vis[x][y] = true;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (mat[nx][ny] == 'X') continue;
if (vis[nx][ny]) continue;
dfs(nx, ny, mat, vis);
}
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
private boolean isBoundary(int x, int y, int n, int m) {
return (x == 0 || x == n - 1) || (y == 0 || y == m - 1);
}
}Number of distinct islands
Counts the number of distinct island shapes in a 2D grid. It uses DFS to traverse each island and records its shape based on relative coordinates from its origin. A HashSet stores these shapes to count only unique ones.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the recursion stack and the HashSet to store island shapes.
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int countDistinctIslands(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
boolean[][] vis = new boolean[n][m];
Set<List<String>> set = new HashSet<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 0) continue;
if (vis[i][j]) continue;
List<String> island = new ArrayList<>();
dfs(i, j, grid, vis, island, i, j);
set.add(island);
}
}
return set.size();
}
private void dfs(int x, int y, int[][] grid, boolean[][] vis, List<String> island, int rootX, int rootY) {
int n = grid.length;
int m = grid[0].length;
vis[x][y] = true;
island.add((x - rootX) + "," + (y - rootY));
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (grid[nx][ny] == 0) continue;
if (vis[nx][ny]) continue;
dfs(nx, ny, grid, vis, island, rootX, rootY);
}
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Cycles
Detect a cycle in an undirected graph
Detects a cycle in an undirected graph using Depth First Search (DFS). During DFS, if an already visited neighbor is encountered that is not the direct parent of the current node, then a cycle is detected.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the visited array and recursion stack.
class Solution {
public boolean isCycle(int V, List<Integer>[] adj) {
boolean[] vis = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
boolean cycle = dfs(i, -1, adj, vis);
if (cycle) return true;
}
return false;
}
private boolean dfs(int node, int parent, List<Integer>[] adj, boolean[] vis) {
vis[node] = true;
for (int nbr : adj[node]) {
if (vis[nbr] && nbr != parent) return true;
if (vis[nbr]) continue;
boolean cycle = dfs(nbr, node, adj, vis);
if (cycle) return true;
}
return false;
}
}Bipartite graph
Checks if a given graph is bipartite using Depth First Search (DFS) or Breadth First Search (BFS). A graph is bipartite if its nodes can be divided into two disjoint and independent sets U and V such that every edge connects a node in U to one in V. This is achieved by coloring nodes alternately; if a conflict arises (adjacent nodes have the same color), the graph is not bipartite.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the color array and recursion stack/queue.
class Solution {
public boolean isBipartite(int V, List<List<Integer>> adj) {
int[] graph = new int[V];
for (int i = 0; i < V; ++i) {
if (graph[i] != 0) continue;
boolean bipartite = dfs(i, 1, adj, graph);
if (!bipartite) return false;
}
return true;
}
private boolean dfs(int node, int color, List<List<Integer>> adj, int[] graph) {
graph[node] = color;
int nbrColor = (color == 1) ? 2 : 1;
for (int nbr : adj.get(node)) {
if (graph[nbr] == color) return false;
if (graph[nbr] == nbrColor) continue;
boolean bipartite = dfs(nbr, nbrColor, adj, graph);
if (!bipartite) return false;
}
return true;
}
}Topological sort or Kahn's algorithm
DFS-based Topological Sort
Performs a topological sort on a Directed Acyclic Graph (DAG) using Depth First Search (DFS). It recursively visits all neighbors of a node, and once all neighbors and their descendants have been visited, the node is pushed onto a stack. The reverse of the stack gives the topological order.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the visited array and recursion stack.
class Solution {
public int[] topoSort(int V, List<List<Integer>> adj) {
boolean[] vis = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
dfs(i, adj, vis, stack);
}
int[] topo = new int[V];
for (int i = 0; i < V; ++i) {
topo[i] = stack.pop();
}
return topo;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] vis, Deque<Integer> stack) {
vis[node] = true;
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis, stack);
}
stack.push(node);
}
}Kahn's algorithm (BFS-based Topological Sort)
Performs a topological sort on a DAG using Breadth First Search (BFS). It works by identifying nodes with an in-degree of zero, adding them to a queue. It then iteratively removes a node from the queue, adds it to the topological order, and decrements the in-degree of its neighbors. If a neighbor's in-degree becomes zero, it's added to the queue.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the in-degree array and queue.
class Solution {
public int[] topoSort(int V, List<List<Integer>> adj) {
int[] inDegree = new int[V];
for (int i = 0; i < V; ++i) {
for (int nbr : adj.get(i)) {
++inDegree[nbr];
}
}
Deque<Integer> q = new ArrayDeque<>();
int[] topo = new int[V];
int idx = 0;
for (int i = 0; i < V; ++i) {
if (inDegree[i] != 0) continue;
q.offer(i);
}
while (!q.isEmpty()) {
int node = q.poll();
topo[idx] = node;
++idx;
for (int nbr : adj.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
return topo;
}
}Detect a cycle in a directed graph
DFS-based Cycle Detection
Detects a cycle in a directed graph using Depth First Search (DFS). It uses two visited arrays: one for keeping track of visited nodes in the current DFS traversal path (pathVis) and another for all visited nodes (vis). A cycle is detected if a node is encountered that is already in the current traversal path (pathVis).
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the visited arrays and recursion stack.
class Solution {
public boolean isCyclic(int V, List<List<Integer>> adj) {
boolean[] vis = new boolean[V];
boolean[] pathVis = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
boolean cycle = dfs(i, adj, vis, pathVis);
if (cycle) return true;
}
return false;
}
private boolean dfs(int node, List<List<Integer>> adj, boolean[] vis, boolean[] pathVis) {
vis[node] = true;
pathVis[node] = true;
for (int nbr : adj.get(node)) {
if (pathVis[nbr]) return true;
if (vis[nbr]) continue;
boolean cycle = dfs(nbr, adj, vis, pathVis);
if (cycle) return true;
}
pathVis[node] = false;
return false;
}
}BFS-based Cycle Detection (Kahn's Algorithm)
Detects a cycle in a directed graph by attempting a topological sort using Kahn's algorithm. If a topological sort can be completed (i.e., all nodes are included in the topological order), then no cycle exists. If the count of nodes in the topological order is less than the total number of nodes, it implies a cycle is present.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the in-degree array and queue.
class Solution {
public boolean isCyclic(int V, List<List<Integer>> adj) {
int[] inDegree = new int[V];
for (int i = 0; i < V; ++i) {
for (int nbr : adj.get(i)) {
++inDegree[nbr];
}
}
Deque<Integer> q = new ArrayDeque<>();
int topoCount = 0;
for (int i = 0; i < V; ++i) {
if (inDegree[i] != 0) continue;
q.push(i);
}
while (!q.isEmpty()) {
int node = q.poll();
++topoCount;
for (int nbr : adj.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
return topoCount != V;
}
}Hard Problems
Find eventual safe states
DFS-based Approach
Finds all eventual safe nodes in a directed graph using Depth First Search (DFS). A node is safe if all paths starting from that node lead to a terminal node (a node with no outgoing edges) or a node that is part of a cycle which eventually leads to a terminal node. The DFS approach uses three states for nodes: unvisited, visiting (in current recursion stack), and visited. Nodes in a cycle or leading to one are unsafe.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the visited arrays and recursion stack.
class Solution {
public int[] eventualSafeNodes(int V, int[][] adj) {
boolean[] vis = new boolean[V];
boolean[] pathVis = new boolean[V];
boolean[] isSafeNodes = new boolean[V];
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
dfs(i, adj, vis, pathVis, isSafeNodes);
}
List<Integer> safeNodes = new ArrayList<>();
for (int i = 0; i < V; ++i) {
if (!isSafeNodes[i]) continue;
safeNodes.add(i);
}
int[] res = new int[safeNodes.size()];
for (int i = 0; i < res.length; ++i) {
res[i] = safeNodes.get(i);
}
return res;
}
private boolean dfs(int node, int[][] adj, boolean[] vis, boolean[] pathVis, boolean[] isSafeNodes) {
vis[node] = true;
pathVis[node] = true;
for (int nbr : adj[node]) {
if (pathVis[nbr]) return true;
if (vis[nbr]) continue;
boolean cycle = dfs(nbr, adj, vis, pathVis, isSafeNodes);
if (cycle) return true;
}
isSafeNodes[node] = true;
pathVis[node] = false;
return false;
}
}BFS-based Approach (using Topological Sort on reversed graph)
Finds eventual safe nodes by reversing all edges of the graph and then performing a topological sort. In the reversed graph, nodes with an in-degree of zero are those that were originally terminal nodes or led only to terminal nodes. By repeatedly processing nodes with zero in-degree (in the reversed graph), all nodes that can eventually reach a terminal node in the original graph are identified as safe.
Time Complexity: O(V + E) for reversing the graph and traversing it.
Space Complexity: O(V + E) for the reversed adjacency list and O(V) for the in-degree array and queue.
class Solution {
public int[] eventualSafeNodes(int V, int[][] adj) {
List<List<Integer>> adjRev = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adjRev.add(new ArrayList<>());
}
int[] inDegree = new int[V];
for (int i = 0; i < V; ++i) {
for (int j : adj[i]) {
adjRev.get(j).add(i);
++inDegree[i];
}
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < V; ++i) {
if (inDegree[i] != 0) continue;
q.offer(i);
}
List<Integer> safeNodes = new ArrayList<>();
while (!q.isEmpty()) {
int node = q.poll();
safeNodes.add(node);
for (int nbr : adjRev.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
Collections.sort(safeNodes);
int[] res = new int[safeNodes.size()];
for (int i = 0; i < res.length; ++i) {
res[i] = safeNodes.get(i);
}
return res;
}
}Course Schedule I
Determines if a set of courses with prerequisites can be finished. This is equivalent to detecting a cycle in a directed graph representing the courses and their prerequisites. If a topological sort can be performed on the graph, then all courses can be finished.
Time Complexity: O(V + E) for building the graph and performing topological sort (Kahn's algorithm).
Space Complexity: O(V + E) for the adjacency list and in-degree array.
class Solution {
public boolean canFinish(int V, int[][] arr) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : arr) {
adj.get(edge[1]).add(edge[0]);
}
int[] inDegree = new int[V];
for (int i = 0; i < V; ++i) {
for (int nbr : adj.get(i)) {
++inDegree[nbr];
}
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < V; ++i) {
if (inDegree[i] != 0) continue;
q.offer(i);
}
int count = 0;
while (!q.isEmpty()) {
int node = q.poll();
++count;
for (int nbr : adj.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
return count == V;
}
}Course Schedule II
Finds a valid order of courses to take given prerequisites, or an empty array if it's impossible (due to a cycle). This is a direct application of topological sort (Kahn's algorithm).
Time Complexity: O(V + E) for building the graph and performing topological sort.
Space Complexity: O(V + E) for the adjacency list, in-degree array, and result list.
class Solution {
public int[] findOrder(int V, int[][] arr) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : arr) {
adj.get(edge[1]).add(edge[0]);
}
int[] inDegree = new int[V];
for (int i = 0; i < V; ++i) {
for (int nbr : adj.get(i)) {
++inDegree[nbr];
}
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < V; ++i) {
if (inDegree[i] != 0) continue;
q.offer(i);
}
List<Integer> resList = new ArrayList<>();
while (!q.isEmpty()) {
int node = q.poll();
resList.add(node);
for (int nbr : adj.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
if (resList.size() != V) return new int[0];
int[] res = new int[resList.size()];
for (int i = 0; i < res.length; ++i) {
res[i] = resList.get(i);
}
return res;
}
}Alien Dictionary
Given a sorted list of words from an alien language, finds the alphabetical order of its characters. This problem can be modeled as finding a topological sort of a directed graph where an edge exists from character 'a' to 'b' if 'a' comes before 'b' in any pair of adjacent words.
Time Complexity: O(N * L + V + E), where N is the number of words, L is the average length of a word, V is the number of unique characters, and E is the number of unique directed edges between characters.
Space Complexity: O(V + E) for the adjacency list and in-degree array.
class Solution {
public String findOrder(String[] dict, int N, int K) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < K; ++i) {
adj.add(new ArrayList<>());
}
int[] inDegree = new int[K];
Set<String> set = new HashSet<>();
for (int i = 0; i < N - 1; ++i) {
String edge = findEdge(dict[i], dict[i + 1]);
if (edge == null) continue;
if (set.contains(edge)) continue;
set.add(edge);
adj.get(edge.charAt(0) - 'a').add(edge.charAt(1) - 'a');
++inDegree[edge.charAt(1) - 'a'];
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < K; ++i) {
if (inDegree[i] != 0) continue;
q.offer(i);
}
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int node = q.poll();
sb.append((char) (node + 'a'));
for (int nbr : adj.get(node)) {
--inDegree[nbr];
if (inDegree[nbr] != 0) continue;
q.offer(nbr);
}
}
return sb.toString();
}
private String findEdge(String src, String dst) {
for (int i = 0; i < Math.min(src.length(), dst.length()); ++i) {
if (src.charAt(i) == dst.charAt(i)) continue;
return "" + src.charAt(i) + dst.charAt(i);
}
return null;
}
}Shortest path in DAG
Finds the shortest path from a source node to all other nodes in a Directed Acyclic Graph (DAG). This is achieved by first performing a topological sort of the DAG, and then iterating through the topologically sorted nodes, relaxing edges for each node.
Time Complexity: O(V + E) for topological sort and relaxation of edges.
Space Complexity: O(V + E) for the adjacency list, stack (for topological sort), and distance array.
class Solution {
private static final int INF = (int) 1e9;
public int[] shortestPath(int N, int M, int[][] edges) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < N; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
boolean[] vis = new boolean[N];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < N; ++i) {
if (vis[i]) continue;
findTopo(i, adj, vis, stack);
}
int[] dist = new int[N];
Arrays.fill(dist, INF);
dist[0] = 0;
while (!stack.isEmpty()) {
int node = stack.pop();
for (int[] nbr : adj.get(node)) {
int nbrNode = nbr[0];
int nbrWeight = nbr[1];
dist[nbrNode] = Math.min(dist[nbrNode], dist[node] + nbrWeight);
}
}
for (int i = 0; i < N; ++i) {
if (dist[i] != INF) continue;
dist[i] = -1;
}
return dist;
}
private void findTopo(int node, List<List<int[]>> adj, boolean[] vis, Deque<Integer> stack) {
vis[node] = true;
for (int[] nbr : adj.get(node)) {
if (vis[nbr[0]]) continue;
findTopo(nbr[0], adj, vis, stack);
}
stack.push(node);
}
}Shortest path in undirected graph with unit weights
Finds the shortest path from a source node to all other nodes in an undirected graph where all edge weights are 1. This can be efficiently solved using Breadth First Search (BFS), as BFS naturally explores the graph layer by layer, finding the shortest path in terms of number of edges.
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V) for the queue and distance array.
class Solution {
private static final int INF = (int) 1e9;
public int[] shortestPath(int[][] edges, int N, int M) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < N; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
Deque<Integer> q = new ArrayDeque<>();
int[] dist = new int[N];
Arrays.fill(dist, INF);
q.offer(0);
dist[0] = 0;
while (!q.isEmpty()) {
int node = q.poll();
for (int nbr : adj.get(node)) {
if (dist[nbr] != INF) continue;
dist[nbr] = dist[node] + 1;
q.offer(nbr);
}
}
for (int i = 0; i < N; ++i) {
if (dist[i] != INF) continue;
dist[i] = -1;
}
return dist;
}
}Word ladder I
Finds the length of the shortest transformation sequence from a beginWord to an endWord using a dictionary wordList, where each transformation changes only one letter. This is a classic Breadth First Search (BFS) problem on a graph where words are nodes and an edge exists between two words if they differ by only one character.
Time Complexity: O(N * L^2), where N is the number of words in the word list and L is the length of each word. (N * L for iterating through words, L for comparing characters and L for string manipulation)
Space Complexity: O(N * L) for storing words in the queue and set.
class Solution {
static class Pair {
String word;
int length;
public Pair(String word, int length) {
this.word = word;
this.length = length;
}
}
public int wordLadderLength(String startWord, String targetWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
Deque<Pair> q = new ArrayDeque<>();
q.offer(new Pair(startWord, 1));
while (!q.isEmpty()) {
Pair node = q.poll();
set.remove(node.word);
if (node.word.equals(targetWord)) return node.length;
char[] charWord = node.word.toCharArray();
for (int i = 0; i < node.word.length(); ++i) {
char original = node.word.charAt(i);
for (char ch = 'a'; ch <= 'z'; ++ch) {
charWord[i] = ch;
String next = new String(charWord);
if (!set.contains(next)) continue;
q.offer(new Pair(next, node.length + 1));
}
charWord[i] = original;
}
}
return 0;
}
}Word Ladder II
Finds all shortest transformation sequences from a beginWord to an endWord using a dictionary wordList, where each transformation changes only one letter. This problem is typically solved using a BFS to find the shortest path(s) and then a DFS to reconstruct all possible shortest paths.
Time Complexity: O(N * L^2 + N * L), where N is the number of words in the word list and L is the length of each word. (N * L^2 for BFS, N * L for path reconstruction in worst case).
Space Complexity: O(N * L) for storing words in the queue, set, and paths.
class Solution {
public List<List<String>> findSequences(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
Deque<List<String>> q = new ArrayDeque<>();
Set<String> foundOnLevel = new HashSet<>();
q.offer(new ArrayList<>(List.of(beginWord)));
set.remove(beginWord);
List<List<String>> res = new ArrayList<>();
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
List<String> currPath = q.poll();
String lastWord = currPath.get(currPath.size() - 1);
if (lastWord.equals(endWord)) {
res.add(currPath);
continue;
}
char[] lastWordCharArray = lastWord.toCharArray();
for (int i = 0; i < lastWordCharArray.length; ++i) {
char original = lastWord.charAt(i);
for (char ch = 'a'; ch <= 'z'; ++ch) {
lastWordCharArray[i] = ch;
String next = new String(lastWordCharArray);
if (!set.contains(next)) continue;
List<String> newPath = new ArrayList<>(currPath);
newPath.add(next);
foundOnLevel.add(next);
q.offer(newPath);
}
lastWordCharArray[i] = original;
}
}
for (String word : foundOnLevel) {
set.remove(word);
}
foundOnLevel.clear();
}
return res;
}
}Shortest Path Algorithms
Dijkstra's algorithm
Finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It uses a priority queue to greedily select the unvisited node with the smallest known distance from the source.
Time Complexity: O(E log V) or O(E + V log V) depending on the priority queue implementation, where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for storing the graph and priority queue.
class Solution {
private static final int INF = (int) 1e9;
public int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {
int[] dist = new int[V];
Arrays.fill(dist, INF);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{S, 0});
dist[S] = 0;
while (!pq.isEmpty()) {
int[] nodeObj = pq.poll();
int node = nodeObj[0];
int dis = nodeObj[1];
for (List<Integer> nbrObj : adj.get(node)) {
int nbr = nbrObj.get(0);
int edgeWt = nbrObj.get(1);
if (dist[nbr] <= dis + edgeWt) continue;
dist[nbr] = dis + edgeWt;
pq.add(new int[]{nbr, dist[nbr]});
}
}
return dist;
}
}Print Shortest Path
Extends Dijkstra's algorithm to not only find the shortest distance but also reconstruct the actual path from a source to a destination in a graph with non-negative edge weights. It does this by keeping track of the predecessor (parent) of each node during the distance calculation.
Time Complexity: O(E log V) or O(E + V log V) depending on the priority queue implementation, similar to Dijkstra's.
Space Complexity: O(V + E) for storing the graph, priority queue, and parent array.
class Solution {
private static final int INF = (int) 1e9;
public List<Integer> shortestPath(int n, int m, int[][] edges) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int wt = edge[2];
adj.get(u).add(new int[]{v, wt});
adj.get(v).add(new int[]{u, wt});
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
pq.add(new int[]{1, 0});
dist[1] = 0;
parent[1] = -1;
while (!pq.isEmpty()) {
int[] nodeObj = pq.poll();
int node = nodeObj[0];
int dis = nodeObj[1];
for (int[] nbrObj : adj.get(node)) {
int nbr = nbrObj[0];
int edgeWt = nbrObj[1];
if (dist[nbr] <= dis + edgeWt) continue;
dist[nbr] = dis + edgeWt;
parent[nbr] = node;
pq.add(new int[]{nbr, dist[nbr]});
}
}
if (dist[n] == INF) return new ArrayList<>(List.of(-1));
List<Integer> path = new ArrayList<>();
int curr = n;
while (curr != -1) {
path.add(curr);
curr = parent[curr];
}
path.add(dist[n]);
Collections.reverse(path);
return path;
}
}Shortest Distance in a Binary Maze
Finds the shortest distance (number of steps) to reach a destination from a source in a binary maze (grid) where '1' represents an open path and '0' an obstacle. This is a Breadth First Search (BFS) problem, as BFS guarantees finding the shortest path in an unweighted graph.
Time Complexity: O(rows * cols) as each cell is visited at most once.
Space Complexity: O(rows * cols) in the worst case for the queue and visited array.
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int shortestPath(int[][] grid, int[] source, int[] destination) {
int n = grid.length;
int m = grid[0].length;
boolean[][] vis = new boolean[n][m];
Deque<int[]> q = new ArrayDeque<>();
vis[source[0]][source[1]] = true;
q.offer(source);
int dist = 0;
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
int[] nodeObj = q.poll();
int x = nodeObj[0];
int y = nodeObj[1];
if (x == destination[0] && y == destination[1]) return dist;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (grid[nx][ny] == 0) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
++dist;
}
return -1;
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Path with minimum effort
Finds a path from the top-left cell to the bottom-right cell in a 2D grid of heights such that the maximum absolute difference in heights between any two adjacent cells along the path is minimized. This problem can be solved using Dijkstra's algorithm or a modified BFS where the cost of an edge is the absolute difference in heights and we are looking for the path with the minimum maximum edge cost.
Time Complexity: O(rows * cols * log(rows * cols)) due to the priority queue operations, where V = rows * cols.
Space Complexity: O(rows * cols) for the distance matrix and priority queue.
class Solution {
private int INF = (int) 1e9;
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int MinimumEffort(List<List<Integer>> heights) {
int n = heights.size();
int m = heights.get(0).size();
int[][] dist = new int[n][m];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dist[i][j] = INF;
}
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
dist[0][0] = 0;
pq.add(new int[]{0, 0, 0});
while (!pq.isEmpty()) {
int[] nodeObj = pq.poll();
int x = nodeObj[0];
int y = nodeObj[1];
int dis = nodeObj[2];
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
int currEffort = Math.max(dis, Math.abs(heights.get(x).get(y) - heights.get(nx).get(ny)));
if (dist[nx][ny] <= currEffort) continue;
dist[nx][ny] = currEffort;
pq.add(new int[]{nx, ny, dist[nx][ny]});
}
}
return dist[n - 1][m - 1];
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Cheapest flight within K stops
Finds the cheapest price from a source city src to a destination city dst with at most K stops. This problem can be solved using a modified Breadth First Search (BFS) or Bellman-Ford-like approach. Instead of tracking just the minimum cost, we track the minimum cost for a given number of stops.
Time Complexity: O(K * E) in the worst case, as each edge might be processed up to K times. (More accurately, O(V + E) for each level of BFS, up to K levels).
Space Complexity: O(V + E) for the adjacency list and queue.
class Solution {
public int CheapestFlight(int n, int[][] flights, int src, int dst, int K) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; ++i) {
adj.add(new ArrayList<>());
}
for (int[] flight : flights) {
int u = flight[0];
int v = flight[1];
int cost = flight[2];
adj.get(u).add(new int[]{v, cost});
}
Deque<int[]> q = new ArrayDeque<>();
int[] totalPrice = new int[n];
Arrays.fill(totalPrice, (int) 1e9);
totalPrice[src] = 0;
q.offer(new int[]{src, 0});
int stops = 0;
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
int[] nodeObj = q.poll();
int node = nodeObj[0];
int cost = nodeObj[1];
if (stops > K) continue;
for (int[] nbrObj : adj.get(node)) {
int nbr = nbrObj[0];
int nbrCost = nbrObj[1];
if (totalPrice[nbr] <= cost + nbrCost) continue;
totalPrice[nbr] = cost + nbrCost;
q.offer(new int[]{nbr, totalPrice[nbr]});
}
}
++stops;
}
return totalPrice[dst] == (int) 1e9 ? -1 : totalPrice[dst];
}
}Minimum multiplications to reach end
Given a starting integer start and a target integer end, along with an array arr of integers, finds the minimum number of multiplications by elements of arr required to transform start into end. All multiplications are performed modulo 100000. This is a BFS problem where states are the current numbers and edges are multiplications.
Time Complexity: O(N * M), where N is the number of elements in arr and M is the modulo value (100000 in this case). Each possible number (0 to M-1) is visited at most once, and for each, we iterate through N multiplications.
Space Complexity: O(M) for the set to store visited numbers and the queue.
class Solution {
public int minimumMultiplications(int[] arr, int start, int end) {
Set<Integer> set = new HashSet<>();
Deque<Integer> q = new ArrayDeque<>();
set.add(start);
q.offer(start);
int steps = 0;
while (!q.isEmpty()) {
for (int qSize = q.size(); qSize > 0; --qSize) {
int node = q.poll();
if (node == end) return steps;
for (int num : arr) {
int curr = (num * node) % 100000;
if (set.contains(curr)) continue;
set.add(curr);
q.offer(curr);
}
}
++steps;
}
return -1;
}
}Number of ways to arrive at destination
Finds the number of shortest paths from a source node to a destination node in a weighted, directed graph. This problem extends Dijkstra's algorithm by, in addition to tracking the minimum distance to each node, also counting the number of ways to achieve that minimum distance. If a new path to a node is shorter, update distance and ways. If equal, add ways.
Time Complexity: O(E log V) or O(E + V log V) depending on priority queue implementation.
Space Complexity: O(V + E) for storing the graph, distance array, ways array, and priority queue.
class Solution {
private int MOD = (int) 1e9 + 7;
public int countPaths(int n, List<List<Integer>> roads) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; ++i) {
adj.add(new ArrayList<>());
}
for (List<Integer> road : roads) {
int u = road.get(0);
int v = road.get(1);
int dis = road.get(2);
adj.get(u).add(new int[]{v, dis});
adj.get(v).add(new int[]{u, dis});
}
long[] dist = new long[n];
int[] ways = new int[n];
Arrays.fill(dist, Long.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{0, 0});
dist[0] = 0;
ways[0] = 1;
while (!pq.isEmpty()) {
int[] nodeObj = pq.poll();
int node = nodeObj[0];
int dis = nodeObj[1];
for (int[] nbrObj : adj.get(node)) {
int nbr = nbrObj[0];
int edgeWt = nbrObj[1];
if (dist[nbr] < dis + edgeWt) continue;
if (dist[nbr] == dis + edgeWt) {
ways[nbr] = (ways[nbr] + ways[node]) % MOD;
continue;
}
dist[nbr] = dis + edgeWt;
ways[nbr] = ways[node];
pq.add(new int[]{nbr, (int) dist[nbr]});
}
}
return ways[n - 1];
}
}Bellman ford algorithm
Finds the shortest paths from a single source node to all other nodes in a weighted graph, even if it contains negative edge weights. It can also detect negative cycles. It iteratively relaxes all edges V-1 times.
Time Complexity: O(V * E) where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) for the distance array.
class Solution {
static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
int[] dist = new int[V];
Arrays.fill(dist, (int) 1e9);
dist[S] = 0;
for (int i = 0; i < V - 1; ++i) {
for (List<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
int wt = edge.get(2);
if (dist[u] == (int) 1e9) continue;
if (dist[v] <= dist[u] + wt) continue;
dist[v] = dist[u] + wt;
}
}
for (List<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
int wt = edge.get(2);
if (dist[u] == (int) 1e9) continue;
if (dist[v] <= dist[u] + wt) continue;
return new int[]{-1};
}
return dist;
}
}Floyd Warshall algorithm
Finds the shortest paths between all pairs of vertices in a weighted graph. It works by iteratively improving an estimate of the shortest path between two vertices, considering all possible intermediate vertices. It can handle negative edge weights but not negative cycles (as they would imply infinite paths).
Time Complexity: O(V^3) where V is the number of vertices.
Space Complexity: O(V^2) for the distance matrix.
class Solution {
public void shortestDistance(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != -1) continue;
matrix[i][j] = (int) 1e9;
}
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != (int) 1e9) continue;
matrix[i][j] = -1;
}
}
}
}Find the city with the smallest number of neighbors
Given a set of cities and the distances between them, and a distance threshold, finds the city that has the smallest number of other cities reachable within the distance threshold. This problem can be solved by first computing all-pairs shortest paths (e.g., using Floyd-Warshall or by running Dijkstra's from each city) and then counting reachable cities for each.
Time Complexity: O(V^3) if using Floyd-Warshall, or O(V * (E log V)) if using Dijkstra's from each node.
Space Complexity: O(V^2) for the distance matrix.
class Solution {
public int findCity(int n, int m, int edges[][], int distanceThreshold) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = (int) 1e9;
if (i == j) {
dist[i][j] = 0;
}
}
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int wt = edge[2];
dist[u][v] = wt;
dist[v][u] = wt;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int res = -1;
int minCount = (int) 1e9;
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j < n; ++j) {
if (dist[i][j] > distanceThreshold) continue;
++count;
}
if (count < minCount) {
minCount = count;
res = i;
} else if (count == minCount) {
res = i;
}
}
return res;
}
}Minimum Spanning Tree
Disjoint Set
A data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides two primary operations: find (determines which subset a particular element is in) and union (merges two subsets into a single subset). Implementations often use "union by rank/size" and "path compression" for optimization.
Time Complexity: O(α(N)) (amortized constant time), where α is the inverse Ackermann function, which is extremely slow-growing, effectively constant for practical purposes. N is the number of elements.
Space Complexity: O(N) for parent and size/rank arrays.
class DisjointSet {
private int[] parent;
private int[] size;
private int[] rank;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
rank = new int[n];
Arrays.fill(rank, 0);
}
public boolean find(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
return parentU == parentV;
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
public void unionByRank(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (rank[parentU] > rank[parentV]) {
parent[parentV] = parentU;
} else if (rank[parentU] < rank[parentV]) {
parent[parentU] = parentV;
} else {
++rank[parentU];
parent[parentV] = parentU;
}
}
public void unionBySize(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (size[parentU] > size[parentV]) {
parent[parentV] = parentU;
size[parentU] += size[parentV];
} else {
parent[parentU] = parentV;
size[parentV] += size[parentU];
}
}
}Find the MST weight
Prim's Algorithm
Finds a Minimum Spanning Tree (MST) for a weighted undirected graph. It starts from an arbitrary vertex and iteratively adds the cheapest edge that connects a tree vertex to a non-tree vertex, until all vertices are included. Uses a priority queue to efficiently find the next cheapest edge.
Time Complexity: O(E log V) or O(E + V log V) with a Fibonacci heap.
Space Complexity: O(V + E) for storing the graph and priority queue.
class Solution {
public int spanningTree(int V, List<List<List<Integer>>> adj) {
boolean[] vis = new boolean[V];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{0, 0});
int sum = 0;
while (!pq.isEmpty()) {
int[] nodeObj = pq.poll();
int node = nodeObj[0];
int wt = nodeObj[1];
if (vis[node]) continue;
vis[node] = true;
sum += wt;
for (List<Integer> nbrObj : adj.get(node)) {
int nbr = nbrObj.get(0);
int nbrWt = nbrObj.get(1);
if (vis[nbr]) continue;
pq.add(new int[]{nbr, nbrWt});
}
}
return sum;
}
}Kruskal's Algorithm
Finds a Minimum Spanning Tree (MST) for a weighted undirected graph. It sorts all edges by weight in non-decreasing order and iteratively adds the cheapest edge to the MST if it does not form a cycle with already added edges. Uses a Disjoint Set Union (DSU) data structure to efficiently detect cycles.
Time Complexity: O(E log E) or O(E log V) (since E < V^2, log E < 2 log V).
Space Complexity: O(V + E) for storing edges and the DSU data structure.
class DisjointSet {
private int[] parent;
private int[] size;
private int[] rank;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
rank = new int[n];
Arrays.fill(rank, 0);
}
public boolean find(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
return parentU == parentV;
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
public void unionByRank(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (rank[parentU] > rank[parentV]) {
parent[parentV] = parentU;
} else if (rank[parentU] < rank[parentV]) {
parent[parentU] = parentV;
} else {
++rank[parentU];
parent[parentV] = parentU;
}
}
public void unionBySize(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (size[parentU] > size[parentV]) {
parent[parentV] = parentU;
size[parentU] += size[parentV];
} else {
parent[parentU] = parentV;
size[parentV] += size[parentU];
}
}
}
class Solution {
public int spanningTree(int V, List<List<List<Integer>>> adj) {
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < V; ++i) {
for (List<Integer> nodeObj : adj.get(i)) {
int u = i;
int v = nodeObj.get(0);
int wt = nodeObj.get(1);
edges.add(new int[]{u, v, wt});
}
}
Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
DisjointSet ds = new DisjointSet(V);
int sum = 0;
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int wt = edge[2];
int rootU = ds.findParent(u);
int rootV = ds.findParent(v);
if (rootU == rootV) continue;
sum += wt;
ds.unionBySize(u, v);
}
return sum;
}
}Hard Problems II
Number of operations to make network connected
Given n computers and connections representing a network, finds the minimum number of operations (moving a cable) to connect all computers. If it's impossible, return -1. This problem involves counting connected components using DFS/BFS or DSU. If the number of available extra cables (edges beyond what's needed for an MST within components) is less than (number of components - 1), it's impossible. Otherwise, the answer is (number of components - 1).
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V + E) for the adjacency list (or DSU structure) and visited array/recursion stack.
class Solution {
public int solve(int n, int[][] edges) {
int m = edges.length;
if (n > m + 1) return -1;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; ++i) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
boolean[] vis = new boolean[n];
int components = 0;
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
++components;
dfs(i, adj, vis);
}
return components - 1;
}
void dfs(int node, List<List<Integer>> adj, boolean[] vis) {
vis[node] = true;
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis);
}
}
}Accounts merge
Merges accounts that belong to the same person. Each account is a list where the first element is the name, and the rest are emails. If two accounts have at least one common email, they belong to the same person and should be merged. The merged account should have the person's name followed by all unique emails sorted lexicographically. This problem is effectively finding connected components in a graph where emails are nodes and accounts imply connections. A Disjoint Set Union (DSU) data structure is ideal for managing these connections.
Time Complexity: O(N * L * log(N * L)) where N is the number of accounts and L is the maximum number of emails per account. (Building DSU is nearly linear, sorting emails dominates).
Space Complexity: O(N * L) for storing emails and DSU structures.
class DisjointSet {
private int[] parent;
private int[] size;
private int[] rank;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
rank = new int[n];
Arrays.fill(rank, 0);
}
public boolean find(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
return parentU == parentV;
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
public void unionByRank(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (rank[parentU] > rank[parentV]) {
parent[parentV] = parentU;
} else if (rank[parentU] < rank[parentV]) {
parent[parentU] = parentV;
} else {
++rank[parentU];
parent[parentV] = parentU;
}
}
public void unionBySize(int u, int v) {
int parentU = findParent(u);
int parentV = findParent(v);
if (parentU == parentV) return;
if (size[parentU] > size[parentV]) {
parent[parentV] = parentU;
size[parentU] += size[parentV];
} else {
parent[parentU] = parentV;
size[parentV] += size[parentU];
}
}
}
class Solution {
static List<List<String>> accountsMerge(List<List<String>> accounts) {
int n = accounts.size();
DisjointSet ds = new DisjointSet(n);
Map<String, Integer> emailOwner = new HashMap<>();
for (int i = 0; i < n; ++i) {
List<String> account = accounts.get(i);
for (int j = 1; j < account.size(); ++j) {
String email = account.get(j);
if (emailOwner.containsKey(email)) {
ds.unionBySize(i, emailOwner.get(email));
} else {
emailOwner.put(email, i);
}
}
}
List<List<String>> mergedMails = new ArrayList<>();
for (int i = 0; i < n; ++i) {
mergedMails.add(new ArrayList<>());
}
for (Map.Entry<String, Integer> entry : emailOwner.entrySet()) {
String email = entry.getKey();
Integer userIdx = entry.getValue();
mergedMails.get(ds.findParent(userIdx)).add(email);
}
List<List<String>> res = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (mergedMails.get(i).isEmpty()) continue;
List<String> curr = new ArrayList<>();
curr.add(accounts.get(i).get(0));
Collections.sort(mergedMails.get(i));
for (String email : mergedMails.get(i)) {
curr.add(email);
}
res.add(curr);
}
return res;
}
}Number of Islands II
Given an m x n grid initialized with water ('0'), and a list of operations where each operation turns a water cell into land ('1'), counts the number of islands after each operation. This problem is efficiently solved using a Disjoint Set Union (DSU) data structure. For each new land cell, check its 4-directional neighbors. If a neighbor is also land, union the sets of the current cell and the neighbor. The number of islands is the number of disjoint sets.
Time Complexity: O(K * α(mn)), where K is the number of operations, mn is the total number of cells, and α is the inverse Ackermann function (effectively constant).
Space Complexity: O(m*n) for the DSU parent/size arrays and the grid representation.
class DisjointSet {
private int[] parent;
private int[] size;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
void unite(int u, int v) {
int rootU = findParent(u);
int rootV = findParent(v);
if (rootU == rootV) return;
if (size[rootU] > size[rootV]) {
parent[rootV] = rootU;
size[rootU] += size[rootV];
} else {
parent[rootU] = rootV;
size[rootV] += size[rootU];
}
}
}
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public List<Integer> numOfIslands(int n, int m, int[][] operations) {
int[][] arr = new int[n][m];
DisjointSet ds = new DisjointSet(n * m);
List<Integer> res = new ArrayList<>();
int islands = 0;
for (int[] opp : operations) {
int x = opp[0];
int y = opp[1];
int node = opp[0] * m + opp[1];
if (arr[x][y] == 1) {
res.add(islands);
continue;
}
arr[x][y] = 1;
++islands;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n, m)) continue;
if (arr[nx][ny] == 0) continue;
int nbr = nx * m + ny;
int rootNode = ds.findParent(node);
int rootNbr = ds.findParent(nbr);
if (rootNode != rootNbr) {
ds.unite(node, nbr);
--islands;
}
}
res.add(islands);
}
return res;
}
private boolean isValid(int x, int y, int n, int m) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
}Making a large island
Given a binary matrix representing a grid of '0's (water) and '1's (land), if we are allowed to change at most one '0' to '1', finds the size of the largest island. This problem involves first finding the size of all existing islands using DFS/BFS and storing them (e.g., mapping root of DSU to size). Then, iterate through all '0' cells, and for each '0', calculate the potential new island size by summing the sizes of adjacent distinct islands (using DSU to identify distinct islands) plus 1 (for the changed '0').
Time Complexity: O(N^2 * α(N^2)) where N is the dimension of the grid (N*N cells). Initial DFS/DSU and then iterating through all cells to find potential island sizes.
Space Complexity: O(N^2) for DSU structures and potentially for storing island sizes.
class DisjointSet {
public int[] parent;
public int[] size;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
void unite(int u, int v) {
int rootU = findParent(u);
int rootV = findParent(v);
if (rootU == rootV) return;
if (size[rootU] > size[rootV]) {
parent[rootV] = rootU;
size[rootU] += size[rootV];
} else {
parent[rootU] = rootV;
size[rootV] += size[rootU];
}
}
}
class Solution {
private int[] dx = {-1, 0, 1, 0};
private int[] dy = {0, 1, 0, -1};
public int largestIsland(int[][] grid) {
int n = grid.length;
DisjointSet ds = new DisjointSet(n * n);
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (grid[x][y] == 0) continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n)) continue;
if (grid[nx][ny] == 0) continue;
int node = x * n + y;
int nbr = nx * n + ny;
ds.unite(node, nbr);
}
}
}
int res = 0;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
int curr = 0;
Set<Integer> vis = new HashSet<>();
if (grid[x][y] == 1) {
curr = ds.size[ds.findParent(x * n + y)];
} else {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isValid(nx, ny, n)) continue;
if (grid[nx][ny] == 0) continue;
int nbr = nx * n + ny;
int rootNbr = ds.findParent(nbr);
if (vis.contains(rootNbr)) continue;
curr += ds.size[rootNbr];
vis.add(rootNbr);
}
++curr;
}
res = Math.max(res, curr);
}
}
return res;
}
private boolean isValid(int x, int y, int n) {
return (0 <= x && x < n) && (0 <= y && y < n);
}
}Most stones removed with same row or column
Given a list of 2D coordinates representing stones, if two stones are in the same row or same column, they can be removed. The goal is to maximize the number of removed stones. This problem can be modeled as finding connected components in a graph where stones are nodes, and an edge exists between two stones if they share a row or column. The number of removable stones is (total stones - number of connected components). A Disjoint Set Union (DSU) data structure is used to count connected components.
Time Complexity: O(N * α(N)) where N is the number of stones.
Space Complexity: O(N) for DSU structures and hash maps (if used to map coordinates to indices).
class DisjointSet {
public int[] parent;
public int[] size;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
}
int findParent(int u) {
if (parent[u] == u) return u;
return parent[u] = findParent(parent[u]);
}
void unite(int u, int v) {
int rootU = findParent(u);
int rootV = findParent(v);
if (rootU == rootV) return;
if (size[rootU] > size[rootV]) {
parent[rootV] = rootU;
size[rootU] += size[rootV];
} else {
parent[rootU] = rootV;
size[rootV] += size[rootU];
}
}
}
class Solution {
public int maxRemove(int[][] stones, int n) {
int r = 0;
int c = 0;
for (int[] stone : stones) {
r = Math.max(r, stone[0]);
c = Math.max(c, stone[1]);
}
DisjointSet ds = new DisjointSet(r + c + 2);
Set<Integer> set = new HashSet<>();
for (int[] stone : stones) {
int x = stone[0];
int y = stone[1] + r + 1;
set.add(x);
set.add(y);
ds.unite(x, y);
}
int component = 0;
for (Integer u : set) {
if (ds.findParent(u) != u) continue;
++component;
}
return n - component;
}
};Additional Algorithms
Kosaraju's algorithm
An algorithm to find the Strongly Connected Components (SCCs) of a directed graph. It involves three main steps:
- Perform DFS on the original graph and store nodes in order of finishing times (on a stack).
- Compute the transpose (reverse) of the graph.
- Perform DFS on the transposed graph in the order of finishing times obtained from step 1. Each DFS traversal in this step explores one SCC.
Time Complexity: O(V + E) for performing two DFS traversals and transposing the graph.
Space Complexity: O(V + E) for storing the original graph, transpose graph, visited arrays, and stack.
class Solution {
public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] vis = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; ++i) {
if (vis[i]) continue;
dfs(i, adj, vis, stack);
}
ArrayList<ArrayList<Integer>> adjT = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adjT.add(new ArrayList<>());
}
for(int i = 0; i < V; ++i) {
for (int j : adj.get(i)) {
adjT.get(j).add(i);
}
}
Arrays.fill(vis, false);
int scc = 0;
List<List<Integer>> sccNodes = new ArrayList<>();
List<Integer> currentScc = new ArrayList<>();
while (!stack.isEmpty()) {
int node = stack.pop();
if (vis[node]) continue;
currentScc.clear();
dfsReverse(node, adjT, vis, currentScc);
++scc;
sccNodes.add(currentScc);
}
return scc;
}
private void dfs(int node, ArrayList<ArrayList<Integer>> adj, boolean[] vis, Deque<Integer> stack) {
vis[node] = true;
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfs(nbr, adj, vis, stack);
}
stack.push(node);
}
void dfsReverse(int node, ArrayList<ArrayList<Integer>> adj, boolean[] vis, List<Integer> currentScc) {
vis[node] = true;
currentScc.add(node);
for (int nbr : adj.get(node)) {
if (vis[nbr]) continue;
dfsReverse(nbr, adj, vis, currentScc);
}
}
}Bridges in graph
Finds all "bridges" (also known as cut edges) in an undirected graph. A bridge is an edge whose removal increases the number of connected components in the graph. This problem is typically solved using Depth First Search (DFS) while keeping track of discovery times (insertTime) and the lowest discovery time reachable from the current node (lowestTime). An edge (u, v) is a bridge if insertTime[u] < lowestTime[v].
Time Complexity: O(V + E) for traversing the graph.
Space Complexity: O(V + E) for adjacency list, visited array, discovery times, and lowest times arrays, and recursion stack.
class Solution {
int timer = 0;
public List<List<Integer>> criticalConnections(int V, List<List<Integer>> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; ++i) {
adj.add(new ArrayList<>());
}
for (List<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
adj.get(u).add(v);
adj.get(v).add(u);
}
boolean[] vis = new boolean[V];
int[] insertTime = new int[V];
int[] lowestTime = new int[V];
List<List<Integer>> bridges = new ArrayList<>();
dfs(0, -1, adj, vis, insertTime, lowestTime, bridges);
return bridges;
}
void dfs(int node, int parent, List<List<Integer>> adj, boolean[] vis, int[] insertTime, int[] lowestTime, List<List<Integer>> bridges) {
vis[node] = true;
insertTime[node] = lowestTime[node] = timer;
++timer;
for (int nbr : adj.get(node)) {
if (nbr == parent) continue;
if (vis[nbr]) {
lowestTime[node] = Math.min(lowestTime[node], insertTime[nbr]);
} else {
dfs(nbr, node, adj, vis, insertTime, lowestTime, bridges);
lowestTime[node] = Math.min(lowestTime[node], lowestTime[nbr]);
if (lowestTime[nbr] > insertTime[node]) {
bridges.add(new ArrayList<>(List.of(node, nbr)));
}
}
}
}
}Articulation point in graph
Finds all "articulation points" (also known as cut vertices) in an undirected graph. An articulation point is a vertex whose removal increases the number of connected components in the graph. Similar to finding bridges, this problem is solved using Depth First Search (DFS) while keeping track of discovery times (insertTime) and the lowest discovery time reachable from the current node (lowestTime). A node 'u' is an articulation point if it's the root of the DFS tree and has more than one child, or if it's not the root and there exists a child 'v' such that lowestTime[v] >= insertTime[u]. │
Time Complexity: O(V + E) for traversing the graph
Space Complexity: O(V + E) for adjacency list, visited array, discovery times, lowest times arrays, and recursion stack.
class Solution {
int timer = 0;
public ArrayList<Integer> articulationPoints(int n, ArrayList<ArrayList<Integer>> adj) {
boolean[] vis = new boolean[n];
int[] insertTime = new int[n];
int[] lowestTime = new int[n];
boolean[] points = new boolean[n];
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
dfs(i, -1, adj, vis, insertTime, lowestTime, points);
}
ArrayList<Integer> artPoints = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (points[i]) artPoints.add(i);
}
if (artPoints.isEmpty()) return new ArrayList<>(List.of(-1));
return artPoints;
}
void dfs(int node, int parent, ArrayList<ArrayList<Integer>> adj, boolean[] vis, int[] insertTime, int[] lowestTime, boolean[] points) {
vis[node] = true;
insertTime[node] = lowestTime[node] = timer;
++timer;
int child = 0;
for (int nbr : adj.get(node)) {
if (nbr == parent) continue;
if (vis[nbr]) {
lowestTime[node] = Math.min(lowestTime[node], insertTime[nbr]);
} else {
dfs(nbr, node, adj, vis, insertTime, lowestTime, points);
++child;
lowestTime[node] = Math.min(lowestTime[node], lowestTime[nbr]);
if (lowestTime[nbr] >= insertTime[node] && parent != -1) {
points[node] = true;
}
}
}
if (parent == -1 && child > 1) {
points[node] = true;
}
}
}