My accepted Java solution with Stacks and O(nm) extra space, 312ms.


  • 0
    W

    Here is my Java code. The basic analysis is the same as this solution.

    By the way, I actually had to solve this question for real work several years ago - it was for an image comparison component where we want to "circle" where the differences are between two images. This OJ problem is a simplified version of that - in real world user want to choose how close two different pixels should be considered within the same island (we use 3 as default as it looks best, but user can pick distance of 1 to 10).

    [Code]

    import java.awt.Point;
    import java.util.*;
    public class Solution {
        public int numIslands(char[][] grid) {
            int result = 0; //number of islands
            if (grid.length == 0 || grid[0].length == 0) {
                return result;
            }
            int[][] v = new int[grid.length][grid[0].length]; // whether the note has been visited.
            Stack<Point> stack = new Stack<Point>();
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    // Loop to iterate through nodes that has not been visited.
                    if (grid[i][j] == '1' && v[i][j] == 0) {
                        // process if there is a difference and we have not visited this node before
                        // found a new island!
                        result++;
                        stack.push(new Point(i, j));
                        while(!stack.empty()) {
                            Point p = stack.pop();
                            v[p.x][p.y] = result;
                            if (p.x > 0) {
                                // top
                                if (grid[p.x -1][p.y] == '1' && v[p.x -1][p.y] == 0) {
                                    stack.push(new Point(p.x -1, p.y));
                                }
                            }
                            if (p.y > 0) {
                                // left
                                if (grid[p.x][p.y - 1] == '1' && v[p.x][p.y -1] == 0) {
                                    stack.push(new Point(p.x, p.y -1));
                                }
                            }
                            if (p.x < grid.length - 1) {
                                // bottom
                                if (grid[p.x + 1][p.y] == '1' && v[p.x +1 ][p.y] == 0) {
                                    stack.push(new Point(p.x + 1, p.y));
                                }
                            }
                            if (p.y < grid[0].length - 1) {
                                // right
                                if (grid[p.x][p.y+1] == '1' && v[p.x][p.y+1] == 0) {
                                    stack.push(new Point(p.x, p.y + 1));
                                }
                            }
                        }
                    }
                }
            }
            return result;
        }
    }
    

  • 0
    R

    My answer is essentially the same. Only that I wrote it in recursive fashion. 284ms

    [code]:

    public class Solution {
        public int numIslands(char[][] grid) {
            if (grid==null || grid.length==0 || grid[0].length==0) return 0;
            boolean[][] map = new boolean[grid.length][grid[0].length];
            int counter = 0;
            for (int idxRow=0; idxRow<grid.length; idxRow++){
                for (int idxCol=0; idxCol<grid[0].length; idxCol++){
                    if (!map[idxRow][idxCol]) {
                        if (grid[idxRow][idxCol]=='1'){
                            counter++;
                            DFSmoving(grid, map, idxRow, idxCol);
                        }
                        else map[idxRow][idxCol]=true;
    
                    }
                }
            }
            
            return counter;
        }
        
        public void DFSmoving(char[][] grid, boolean[][] map, int row, int col){
            map[row][col]=true;
            if (grid[row][col]=='1') {
                if (row>0 && !map[row-1][col]) DFSmoving(grid, map, row-1, col);
                if (row<map.length-1 && !map[row+1][col]) DFSmoving(grid, map, row+1, col);
                if (col>0 && !map[row][col-1]) DFSmoving(grid, map, row, col-1);
                if (col<map[0].length-1 && !map[row][col+1]) DFSmoving(grid, map, row, col+1);  
            }
       
        }
    }

Log in to reply
 

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