200 Number of Islands

Techniques Used

• Graph
• DFS

Approach

• Initialize the visited matrix to keep track of visited elements & also the island_count.
• Apply nested for loops to visit all elements of the grid
  • Conditions to apply dfs on an element of the grid
    • if it has not been visited and it is not equal to '0'.
    • Apply dfs for the current element
    • Increment the island_count
• Our dfs utility function will take in the grid, row, col, and the visited matrix as arguments
  • check the boundary conditions AND whether the element has been visited yet or not AND whether it is '0' or not, return accordingly.
  • Once inside the function after checking above,
    • we mark the current element ( grid[row][col]) as visited.
    • apply the same dfs function recursively for 4-directionally neighboring elements.

Complexity

• Time Complexity: O(mn) - At most, we will end up visiting all elements.
• Space Complexity: O(mn) - For the visited matrix. We can reduce the space complexity by modifying the elements of the original matrix smartly.

Code:

class Solution {
    public int numIslands(char[][] grid) {

        // perform dfs element by element while keeping track of visited elements
        // increment the count accordingly

        int m = grid.length;
        int n = grid[0].length;

        int island_count = 0;

        boolean[][] visited = new boolean[m][n];

        for(int i =  0; i < m; i++){
            for(int j =  0; j < n; j++){
                if(!visited[i][j] && grid[i][j] != '0'){
                    dfs(grid, i, j, visited);
                    island_count++;
                }

            }
        }

        return island_count;

    }

    static void dfs(char[][] grid, int row, int col, boolean[][] visited){

        // check bounds
        if(row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || visited[row][col] || grid[row][col] == '0' ) return;


        visited[row][col] = true;

        dfs(grid, row - 1, col, visited);
        dfs(grid, row + 1, col, visited);
        dfs(grid, row, col  + 1, visited);
        dfs(grid, row, col - 1, visited);

        return;



    }
}