Clear & Easy Java Solution


  • 39
    D
    public class Solution {
        public int numIslands(char[][] grid) {
            int count = 0;
            
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        clearRestOfLand(grid, i, j);
                    }
                }
            }
            return count;
        }
        
        private void clearRestOfLand(char[][] grid, int i, int j) {
            if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == '0') return;
            
            grid[i][j] = '0';
            clearRestOfLand(grid, i+1, j);
            clearRestOfLand(grid, i-1, j);
            clearRestOfLand(grid, i, j+1);
            clearRestOfLand(grid, i, j-1);
            return;
        }
    }

  • 0

    is the complexity of this problem n*m?


  • 0
    H

    what is the time complexity of your solution?


  • 0
    G

    "clear the rest of land" is really clever


  • 1
    T

    The cleanest solution I have read so far. Good job!


  • 0
    S

    @mlblount45 If I'm understanding the code correctly, it looks like it's close to O(n + 4c * n). The first n is the original iteration over the size of the grid. You must go over every spot, so size is n.

    The second 4c*n is when you begin clearing land. For every piece of land you're checking, you also check the four pieces around it. However, you only check the pieces around it if the current piece is land, otherwise you immediately return.

    Would love a second opinion, but that's what I came out to.


  • 0
    H

    @SIRHAMY what is 'c'? IMO the time complexity is O(row*col)


  • 0
    L

    So clever! Very intuitive algorithm.


Log in to reply
 

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