Solving Number of Islands
To see the question, click here.
Naive Approach 1
The idea is to use the DFS algorithm to explore the grid. Whenever it encounters a land cell ('1') that has not been visited, it marks it as visited and recursively explores all its adjacent (up, down, left, right) land cells, marking them as visited. This process effectively groups connected land cells into a single island.
// TC: O(m*n)
// SC: O(m*n)
public class NumberofIslands {
public void dfs(char[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length;
int n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0' || visited[i][j])
return;
visited[i][j] = true;
dfs(grid, i + 1, j, visited);
dfs(grid, i - 1, j, visited);
dfs(grid, i, j + 1, visited);
dfs(grid, i, j - 1, visited);
}
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0)
return count;
int m = grid.length;
int n = grid[0].length;
boolean visited[][] = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j, visited);
count++;
}
}
return count;
}
public static void main(String[] args) {
NumberofIslands noi = new NumberofIslands();
char[][] grid = { { '1', '1', '1', '0' },
{ '0', '0', '1', '0' },
{ '1', '0', '0', '1' }, };
System.out.println(noi.numIslands(grid));
}
}
Performance
The time complexity of the numIslands method is O(m*n) because we are iterating through each cell in the grid once. The space complexity is also O(m*n) because we use a boolean array to track visited cells the same size as the input grid.
Refined Approach 1
The idea is to implement the DFS algorithm using stack. Suppose the grid is very large or the islands are extensive. In that case, the iterative stack solution avoids the risk of stack overflow by using the heap memory for the Stack, which is generally larger than the call stack used in recursion.
// TC: O(m*n)
// SC: O(m*n)
import java.util.Stack;
public class NumberofIslands {
public void dfs(char[][] grid, int i, int j, boolean[][] visited) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[] { i, j });
while (!stack.isEmpty()) {
int[] p = stack.pop();
int x = p[0];
int y = p[1];
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0' || visited[x][y])
continue;
visited[x][y] = true;
stack.push(new int[] { x - 1, y });
stack.push(new int[] { x + 1, y });
stack.push(new int[] { x, y - 1 });
stack.push(new int[] { x, y + 1 });
}
}
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0)
return count;
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j, visited);
count++;
}
}
}
return count;
}
public static void main(String[] args) {
NumberofIslands noi = new NumberofIslands();
char[][] grid = {
{ '1', '1', '1', '0' },
{ '0', '0', '1', '0' },
{ '1', '0', '0', '1' }
};
System.out.println(noi.numIslands(grid));
}
}
Performance
The time complexity of the numIslands method is O(m*n). This is because, in the worst-case scenario, we may have to visit every cell in the grid once. The space complexity is also O(m*n) because we use a boolean array of the same size to keep track of visited cells. Additionally, the stack used in the DFS traversal can potentially hold all cells in the grid in the worst-case scenario.
Efficient Approach 1
Instead of creating another matrix to mark visited cells, we can change the 1s to 0s to ensure they have been visited.
// TC: O(m*n)
// SC: O(m*n)
import java.util.Stack;
public class NumberofIslands {
public void dfs(char[][] grid, int i, int j) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[] { i, j });
while (!stack.isEmpty()) {
int[] p = stack.pop();
int x = p[0];
int y = p[1];
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0')
continue;
grid[x][y] = '0';
stack.push(new int[] { x - 1, y });
stack.push(new int[] { x + 1, y });
stack.push(new int[] { x, y - 1 });
stack.push(new int[] { x, y + 1 });
}
}
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0)
return count;
int m = grid.length;
int n = grid[0].length;
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;
}
public static void main(String[] args) {
NumberofIslands noi = new NumberofIslands();
char[][] grid = {
{ '1', '1', '1', '0' },
{ '0', '0', '1', '0' },
{ '1', '0', '0', '1' }
};
System.out.println(noi.numIslands(grid));
}
}
Performance
The time complexity of the numIslands method is O(m*n). This is because we are iterating through each cell in the grid once and performing a DFS traversal if the cell contains a '1'. The space complexity is also O(m*n) because, in the worst-case scenario, the stack can contain all the cells in the grid if they are all connected to a single island.
Naive Approach 2
The idea is to use the BFS algorithm to explore the grid. It starts by marking the initial cell as visited and then uses a Queue to explore all adjacent land cells level by level. When it encounters a land cell ('1') that has not been visited, it explores its unvisited land neighbours and continues this process until there are no more cells to explore from the current island.
// TC: O(m*n)
// SC: O(m*n)
import java.util.Queue;
import java.util.LinkedList;
public class NumberofIslands {
public void bfs(char[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { i, j });
visited[i][j] = true;
int[][] dirs = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int[] dir : dirs) {
int r = curr[0] + dir[0];
int c = curr[1] + dir[1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1' && !visited[r][c]) {
q.add(new int[] { r, c });
visited[r][c] = true;
}
}
}
}
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0)
return count;
int m = grid.length;
int n = grid[0].length;
boolean visited[][] = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (grid[i][j] == '1' && !visited[i][j]) {
bfs(grid, i, j, visited);
count++;
}
}
return count;
}
public static void main(String[] args) {
NumberofIslands noi = new NumberofIslands();
char[][] grid = { { '1', '1', '1', '0' },
{ '0', '0', '1', '0' },
{ '1', '0', '0', '1' }, };
System.out.println(noi.numIslands(grid));
}
}
Performance
The numIslands method has a time complexity of O(m*n) as well because, in the worst-case scenario, we may have to visit all cells in the grid. The space complexity is also O(m*n) because we use a boolean array of the same size to keep track of visited cells. Additionally, the BFS queue can contain all cells in the grid.
Efficient Approach 2
Instead of creating another matrix to mark visited cells, we can change the 1s to 0s to ensure they have been visited.
// TC: O(m*n)
// SC: O(m*n)
import java.util.Queue;
import java.util.LinkedList;
public class NumberofIslands {
public void bfs(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { i, j });
grid[i][j] = '0';
int[][] dirs = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int[] dir : dirs) {
int r = curr[0] + dir[0];
int c = curr[1] + dir[1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
q.add(new int[] { r, c });
grid[r][c] = '0';
}
}
}
}
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0)
return count;
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
count++;
}
}
}
return count;
}
public static void main(String[] args) {
NumberofIslands noi = new NumberofIslands();
char[][] grid = { { '1', '1', '1', '0' },
{ '0', '0', '1', '0' },
{ '1', '0', '0', '1' }, };
System.out.println(noi.numIslands(grid));
}
}
Performance
The time complexity of the numIslands method is O(m*n) because we are iterating through each cell in the grid once. The space complexity is also O(m*n) because, in the worst-case scenario, the BFS queue can contain all cells in the grid.
Thank you for reading!
Check out other DSA patterns here.
You can support me by buying me a book.