My Java solution [Iterative DFS + Stack]


  • 0
    W

    Hello! I think that the code is fairly straightforward and as many have said on here, it is a pretty cool DFS problem. The general idea of my solution is to switch the '1's to '0's if an island is found. Since an island can have more than one '1's interconnected, I used a stack to keep track of the surrounding '1's and switch them to '0's accordingly. This way, the loop can continue effortlessly without having to come across an island that has already been found.

    Feel free to let me know if this solution can be improved upon OR if you have any queries for me. :]

    public int numIslands(char[][] grid) {
            int numOfRow = grid.length;
            if(numOfRow == 0)
                return 0;
            int numOfCol = grid[0].length;
            int numOfIslands = 0;
            Stack<Integer> gridTrackerOfRow = new Stack<Integer>();
            Stack<Integer> gridTrackerOfCol = new Stack<Integer>();
            for(int i = 0; i < numOfRow; i++){
                for(int j = 0; j < numOfCol; j++){
                    if(grid[i][j] == '1'){
                        gridTrackerOfRow.push(i);
                        gridTrackerOfCol.push(j);
                        while(!gridTrackerOfRow.isEmpty() && !gridTrackerOfCol.isEmpty()){
                            int x = gridTrackerOfRow.pop();
                            int y = gridTrackerOfCol.pop();
                            grid[x][y] = '0';
                            
                            if(y+1 < numOfCol && grid[x][y+1] == '1'){
                                gridTrackerOfRow.push(x);
                                gridTrackerOfCol.push(y+1);
                            }
                            if(y-1 >= 0 && grid[x][y-1] == '1'){
                                gridTrackerOfRow.push(x);
                                gridTrackerOfCol.push(y-1);
                            }
                            if(x+1 < numOfRow && grid[x+1][y] == '1'){
                                gridTrackerOfRow.push(x+1);
                                gridTrackerOfCol.push(y);
                            }
                            if(x-1 >= 0 && grid[x-1][y] == '1'){
                                gridTrackerOfRow.push(x-1);
                                gridTrackerOfCol.push(y);
                            }
                        }
                        numOfIslands++;
                    }
                }
            }
            
            return numOfIslands;
        }

Log in to reply
 

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