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

• 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;
}
}
``````

• 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);
}

}
}``````

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