Short Java solution using stack class instead of recursion


  • 0
    S

    This solution utilizes a stack instead of recursion. It also overwrites the grid with zeros to keep track of what's been marked as an Island so far.

    public class Solution {

        public int numIslands(char[][] grid) {
            int islands=0;
            for (int x=0 ; x< grid.length;x++) { 
                for(int y=0; y<grid[x].length;y++) { 
                    if (grid[x][y]=='1') {
                        islands++;
                        Stack<Integer[]> s=new Stack<Integer[]>();
                        s.push(new Integer[] {x,y});
                        while (!s.empty()) {
                            Integer p[]=s.pop();      
                            if (grid[p[0]][p[1]]=='0') continue;
                                grid[p[0]][p[1]]='0';
                            if (p[1]+1 < grid[p[0]].length)
                                s.push(new Integer[] { p[0],p[1]+1 });
                            if (p[1]-1 >=0)
                                s.push(new Integer[] { p[0],p[1]-1 });
                            if (p[0]+1 < grid.length)
                                s.push(new Integer[] { p[0]+1,p[1] });
                            if (p[0]-1 >=0)
                                s.push(new Integer[] { p[0]-1,p[1] });
                        }
                    }
                }
            }
            return islands;
        }
    }

Log in to reply
 

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