6ms constant space DFS solution. Using the grid itself as a marker array.


  • 0
    F
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        
        int count = 0;
        for (int i=0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j, m, n, grid);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void dfs(int i, int j, int m, int n, char [][] grid) {
        grid[i][j] = '#'; // our way to mark visited land
        
        int [][] masks = {{0,1}, {0,-1}, {1,0}, {-1, 0}};
        
        for (int k=0 ; k<masks.length; k++) {
            int newI = i + masks[k][0];
            int newJ = j+ masks[k][1];
            
            if (newI >=0 && newI <m && newJ >=0 && newJ < n && grid[newI][newJ] == '1') {
                dfs(newI, newJ, m, n , grid);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.