3ms JAVA using DFS + recursion


  • 1
    Y

    Traverse all the number in the array, when meeting 1, change all the 1 adjacent it into non-1; than the number of the island is the number of '1' you meet

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

  • 0

    Very interesting thought!


  • 0
    J

    Very nice solution.

    Just curious though, would java create another "grid" in memory for every recursive call?


  • 0

    @jcubz From my understanding, Java passes values of references of arrays. This means only the references are copied, but not the actual array. If otherwise, it will be a disaster of space complexity to program Java.


Log in to reply
 

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