In this tutorial, I am going to discuss a very famous interview problem. How to count the number of islands.
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are surrounded by water.
Now, The important question is how do we approach this problem. In this tutorial, I am going to explain the number of islands LeetCode solution using BFS and DFS technique and its java code.
At the end of this post, I have shared a video tutorial link.
Count Number of Islands using DFS (Depth First Search) – Java Code
In this example, I am going to explain how to solve this problem using DFS (Depth First Search).
The first step is to traverse a matrix. When we found a grid whose value is 1 then check all the connected 1’s and mark them as visited. After doing this increment the count which keeps track of the no. of islands.
Repeat this process until the matrix is traversed completely.
The time complexity of this approach is O(n*m) where n is the no of rows and m is the no. of columns.
Number of islands DFS video tutorial
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//Number of islands using DFS public static int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1') { //Find all connected 1's countIslandHelper(grid, i, j); count++; } } } return count; } public static void countIslandHelper(char[][] grid, int i, int j) { if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') { return; } //To mark them as visited, i put 2 grid[i][j] = '2'; //Move in 4 directions countIslandHelper(grid, i+1, j); countIslandHelper(grid, i-1, j); countIslandHelper(grid, i, j-1); countIslandHelper(grid, i, j+1); } |
Count Number of Islands using BFS (Breadth First Search) – Java Code
In our previous example, we have discussed how we can solve this problem using DFS. In this example, Let’s solve this problem using BFS (Breadth-First Search).
To solve this problem, Traverse a 2D grid, and when we find the grid whose value is 1. Then check all connected 1’s and mark them as visited. We can only move in four directions. Also, Once all connected 1’s are traversed then increment the value of count. This process is repeated until the matrix is traversed completely.
The time complexity of this approach is O(n*m) where n is the no of rows and m is the no. of columns.
Number of islands using BFS video tutorial
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
//count the number of islands problem - Java Code public static int numIslands(char[][] grid) { if(grid == null || grid.length == 0) return 0; int count =0; int row = grid.length; int col = grid[0].length; //Move in Four Directions int [][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; Queue<int []> qu = new LinkedList<>(); for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(grid[i][j] == '1') { count++; qu.add(new int[] {i,j}); //Mark as visited grid[i][j] = '2'; while(!qu.isEmpty()){ int [] curr = qu.poll(); for(int [] dir : directions){ int r = curr[0] + dir[0]; int c = curr[1] + dir[1]; if(r >= 0 && r < row && c >= 0 && c < col && grid[r][c] == '1'){ qu.add(new int[] {r,c}); grid[r][c] = '2'; } } } } } } return count; } |
