Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Understand Problem
We need to traverse through adjacent 1’s which would form one island.Idea – 1
The grid can be thought of as an undirected graph and the islands are connected components. A dfs from a vertex in a connected component stays within the component and traverses all nodes in the component. So, we would be doing dfs’s from each unvisited island node (grid cell with ‘1’) and keep count. We would be traversing each edge at most once and there are
edges, so time complexity is 
. We use recursion, so worst case stack space is as well (which could happen say if there is a single island).
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if(m==0)
{
return 0;
}
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int islandCount = 0;
for(int row = 0; row < m; ++row)
{
for(int col = 0; col < n; ++col)
{
if(grid[row][col]=='1' && !visited[row][col])
{
++islandCount;
dfs(grid, row, col, visited);
}
}
}
return islandCount;
}
private void dfs(char[][] grid, int row, int col, boolean[][] visited)
{
int m = grid.length;
int n = grid[0].length;
if(row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0' || visited[row][col])
{
return;
}
visited[row][col] = true;
// visit upwards
dfs(grid, row-1, col, visited);
// visit rightwards
dfs(grid, row, col+1, visited);
// visit downwards
dfs(grid, row+1, col, visited);
// visit leftwards
dfs(grid, row, col-1, visited);
}
}
Runtime: 1 ms, faster than 100.00% of Java online submissions for Number of Islands.
Memory Usage: 40.8 MB, less than 40.82% of Java online submissions forNumber of Islands.
Idea - 2
If we are allowed to modify the grid, we could used it to keep track of visited and save some space. The worst case time and space are still.
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if(m==0)
{
return 0;
}
int n = grid[0].length;
int islandCount = 0;
for(int row = 0; row < m; ++row)
{
for(int col = 0; col < n; ++col)
{
if(grid[row][col]=='1')
{
++islandCount;
dfs(grid, row, col);
}
}
}
return islandCount;
}
private void dfs(char[][] grid, int row, int col)
{
int m = grid.length;
int n = grid[0].length;
if(row < 0 || row >= m || col < 0 || col >= n || grid[row][col] != '1')
{
return;
}
grid[row][col] = 'X';
// visit upwards
dfs(grid, row-1, col);
// visit rightwards
dfs(grid, row, col+1);
// visit downwards
dfs(grid, row+1, col);
// visit leftwards
dfs(grid, row, col-1);
}
}
Runtime: 1 ms, faster than 100.00% of Java online submissions for Number of Islands.
Memory Usage: 42.3 MB, less than 5.02% of Java online submissions forNumber of Islands.
Interestingly the memory usage has gone up, probably because I used 'X' to mark visited nodes. Using '2' to mark visited node the result is better:
Runtime: 1 ms, faster than 100.00% of Java online submissions for Number of Islands.
Memory Usage: 41 MB, less than 28.87% of Java online submissions forNumber of Islands.
Idea - 3
If stack space is limited, we can avoid recursion and use a stack object. The time and space complexity do not change.
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if(m==0)
{
return 0;
}
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int islandCount = 0;
for(int row = 0; row < m; ++row)
{
for(int col = 0; col < n; ++col)
{
if(grid[row][col]=='1' && !visited[row][col])
{
++islandCount;
Deque<int[]> stack = new ArrayDeque<>();
int[] root = {row, col};
stack.addLast(root);
while(!stack.isEmpty())
{
int[] node = stack.removeLast();
int x = node[0];
int y = node[1];
if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y]=='1' && !visited[x][y])
{
visited[x][y] = true;
int[] up = {x-1, y};
stack.addLast(up);
int[] right = {x, y+1};
stack.addLast(right);
int[] down = {x+1, y};
stack.addLast(down);
int[] left = {x, y-1};
stack.addLast(left);
}
}
}
}
}
return islandCount;
}
}
Runtime: 8 ms, faster than 9.89% of Java online submissions for Number of Islands.
Memory Usage: 42 MB, less than 5.02% of Java online submissions for Number of Islands.
Idea - 4
Using BFS we could reduce worst case space to
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if(m==0)
{
return 0;
}
int n = grid[0].length;
int islandCount = 0;
for(int row = 0; row < m; ++row)
{
for(int col = 0; col < n; ++col)
{
if(grid[row][col]=='1')
{
++islandCount;
Deque<int[]> queue = new ArrayDeque<>();
int[] root = {row, col};
queue.addLast(root);
while(!queue.isEmpty())
{
int[] node = queue.removeFirst();
int x = node[0];
int y = node[1];
if(x >=0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
{
grid[x][y] = '2';
int[] up = {x-1, y};
queue.addLast(up);
int[] right = {x, y+1};
queue.addLast(right);
int[] down = {x+1, y};
queue.addLast(down);
int[] left = {x, y-1};
queue.addLast(left);
}
}
}
}
}
return islandCount;
}
}
RuRuntime: 7 ms, faster than 13.47% of Java online submissions for Number of Islands.
Memory Usage: 41.9 MB, less than 5.02% of Java online submissions forNumber of Islands.
time.
pairs and see if the sum equals target.
programmingpuzzles 