Very concise Java AC solution


  • 166
    W
    public class Solution {
    
    private int n;
    private int m;
    
    public int numIslands(char[][] grid) {
        int count = 0;
        n = grid.length;
        if (n == 0) return 0;
        m = grid[0].length;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
                if (grid[i][j] == '1') {
                    DFSMarking(grid, i, j);
                    ++count;
                }
        }    
        return count;
    }
    
    private void DFSMarking(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
        grid[i][j] = '0';
        DFSMarking(grid, i + 1, j);
        DFSMarking(grid, i - 1, j);
        DFSMarking(grid, i, j + 1);
        DFSMarking(grid, i, j - 1);
    }
    

    }


  • 3
    Y

    This code cannot work. In numIslands function, it should be "n = grid.length;" and "m = grid[0].length;".


  • 0
    W

    Thank you for pointing out this.


  • 21

    Nice solution :)
    Op's thought process - Just drown every island - one by one!!


  • 0
    D
    This post is deleted!

  • 0
    P

    so beautiful


  • 0
    C

    Definitely amazing and inspiring!!


  • 2
    C

    C# implementation

        private static void Marking(char[,] grid, int i, int j)
        {
            if (i < 0 || j < 0 || i >= grid.GetLength(0) || j >= grid.GetLength(1) || grid[i, j] == '0')
            {
                return;
            }
    
            grid[i, j] = '0';
            Marking(grid, i + 1, j);
            Marking(grid, i - 1, j);
            Marking(grid, i, j + 1);
            Marking(grid, i, j - 1);
        }
    
        public int NumIslands(char[,] grid)
        {
            int cnt = 0;
    
            for (int i = 0; i < grid.GetLength(0); i++)
            {
                for (int j = 0; j < grid.GetLength(1); j++)
                {
                    if (grid[i, j] == '1')
                    {
                        Marking(grid, i, j);
                        cnt++;
                    }
                }
            }
    
            return cnt;
        }

  • 0
    P

    What would be the time complexity?


  • 20
    G

    I really like this solution.

    Below is my refactoring from studying it, with comments

    public class Solution {
        int y;          // The height of the given grid
        int x;          // The width of the given grid
        char[][] g;     // The given grid, stored to reduce recursion memory usage
        
        /**
         * Given a 2d grid map of '1's (land) and '0's (water),
         * count the number of islands.
         * 
         * This method approaches the problem as one of depth-first connected
         * components search
         * @param grid, the given grid.
         * @return the number of islands.
         */
        public int numIslands(char[][] grid) {
            // Store the given grid
            // This prevents having to make copies during recursion
            g = grid;
    
            // Our count to return
            int c = 0;
            
            // Dimensions of the given graph
            y = g.length;
            if (y == 0) return 0;
            x = g[0].length;
            
            // Iterate over the entire given grid
            for (int i = 0; i < y; i++) {
                for (int j = 0; j < x; j++) {
                    if (g[i][j] == '1') {
                        dfs(i, j);
                        c++;
                    }
                }
            }
            return c;
        }
        
        /**
         * Marks the given site as visited, then checks adjacent sites.
         * 
         * Or, Marks the given site as water, if land, then checks adjacent sites.
         * 
         * Or, Given one coordinate (i,j) of an island, obliterates the island
         * from the given grid, so that it is not counted again.
         * 
         * @param i, the row index of the given grid
         * @param j, the column index of the given grid
         */
        private void dfs(int i, int j) {
            
            // Check for invalid indices and for sites that aren't land
            if (i < 0 || i >= y || j < 0 || j >= x || g[i][j] != '1') return;
            
            // Mark the site as visited
            g[i][j] = '0';
            
            // Check all adjacent sites
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i, j + 1);
            dfs(i, j - 1);
        }
    }
    

  • 13
    G

    @pantherNation The time complexity is linear.

    much-later edit: The time complexity is O(m*n), where m and n are the width and height of the grid, respectively. The time complexity is only "linear" in the number of cells in the grid.

    Since we are conducting a depth-first search on grid, we have to touch every cell in grid at least once.

    However, in the worst-conceivable case, we're only touching every interior cell in grid five times (and touching the exterior cells three or four times).

    We would encounter the worst case if we had a grid like:

    01010101
    10101010
    01010101
    10101010
    

    Note that the cell in the top-left is touched initially when the iteration begins, then it is touched for the 1 to its right and for the 1 below it, for a total of three times.


  • 1
    Y

    @GrubenM Hi,
    I am still confused that why the time complexity is not O(mn)?
    In the first function, it seems like every value in grid has been visited via the function.


  • 3
    G

    @Yizhang_John You're correct, the complexity is O(m*n), where n is the number of columns in the grid and m is the number of rows in the grid.

    We can consider this to be quadratic in the dimensions of the grid. That is, for an n-by-n grid, the time complexity would be O(n^2).

    To state the same thing in a different way, we can consider this to be linear in the number of cells in the grid. As you correctly note, the function does visit every value in the grid (at most 5 times). Note that this is an equivalent restatement of time complexity, since for an n-by-n grid, there are n^2 cells, and so the time complexity is still O(n^2).

    I should have been clearer in my reply to pantherNation :p


  • 1
    Y

    @GrubenM
    Thanks for that.
    Now I understand it.


  • 0
    Y

    For the below input, it shows the output as 7 , but I believe it is only 6.
    Even in the leet code the expected output is 7 which i'm not sure why there is extra 1
    If you observe carefully it shows only 6 islands/groups here.

    ["0000001110",
    "0000000000",
    "1000010000",
    "1000000110",
    "1000000110",
    "1000100000",
    "0001000001"]


  • 0
    J

    @yugendhar still 7


  • 0
    Y

    @jiny1981 How it is still 7 ? can you explain where I'm missing one more entry


  • 4
    G

  • 0
    Y

    @GrubenM I think in the last two rows, the two small islands are considered as one as they are connected diagonally. They can't be two separate islands


  • 3
    G

    @yugendhar That's why you're counting 6 :)

    An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

    The above does not mention diagonals, which I interpret to mean that diagonal 1s do not qualify as islands by that alone.

    Problem link.


Log in to reply
 

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