1. Number of Islands

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.

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 all surrounded by water.

Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Approach

• we will start wherever we have one then we need to check in all directions
• Time complexity: O(m∗n)O(m∗n)
• Space complexity: O(m∗n)O(m∗n)

class Solution {
    private int[][] dir = new int[][] {{1,0},{0,1},{-1,0},{0,-1}};
    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        int island = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    island++;
                    dfs(grid,i,j);
                }
            }
        }
        return island;
    }
    public void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0')
            return;
 
        grid[row][col] = '0';
        for (int[] n: dir) {
            dfs(grid,row+n[0],col+n[1]);
        }    
    }
}