why stackoverflow for simple Java DFS solution?


  • 0
    S

    Hello guys,
    I wrote DFS solution for this problem but it is giving stackoverflow error for test cases.

    
    public int numIslands(char[][] grid) {
            if (grid.length == 0) {
                return 0;
            }
            int nums = 0;
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            
            for(int i = 0; i < grid.length; i++) {
                for (int j=0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1' && !visited[i][j]) {
                        nums++;
                        makeConnectedOnesZeroes(grid, visited, i, j, grid.length, grid[0].length);
                    }
                }
            }
            
            return nums;
        }
        
        void makeConnectedOnesZeroes(char[][] grid, boolean[][] visited, int i, int j, int m, int n) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                return;
            }
            if(visited[i][j])
                return;
            
            grid[i][j] = '0';
            visited[i][j] = true;
            
            makeConnectedOnesZeroes(grid, visited, i+1, j, m, n);
            makeConnectedOnesZeroes(grid, visited, i-1, j, m, n);    
            makeConnectedOnesZeroes(grid, visited, i, j+1, m, n);    
            makeConnectedOnesZeroes(grid, visited, i, j-1, m, n);    
        }
    
    

  • 0
    V

    You should add here "(i < 0 || i >= m || j < 0 || j >= n)" grid[i][j] != '0'. which will make the condition as

    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
                return;
      }
    

  • 0
    S

    @vishalgaurav Thanks :)


Log in to reply
 

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