Problem
Island Perimeter
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
Answer: 16
Solution
Use line scan is a straight-forward solution. The time cost is O(NM), the space cost is O(1). If we saw a 1 cell, the count increase 4.
we check cell above, if it is 1, count decrease 2.
we check cell on left, if it is 1, count decrease 2.
If majority of the map is water, we wasted lots of time scan 0s. A faster way is to use graph traversal. We found the first 1 cell, then do a dfs, only scan the cells on the island and around it. The time cost for bfs is O(V+E), where V is the island area, each cell has at most 4 edges. So the time and space is O(V).
import java.util.*;
class IslandPerimeter {
private static int countCellPerimeter(int[][] map, int i, int j) {
int count = 4;
if(i > 0 && map[i-1][j] == 1) count -= 2;
if(j > 0 && map[i][j-1] == 1) count -= 2;
return count;
}
public static void main(String...args) {
int[][] map = new int[][] {
{0,1,0,0},
{1,1,1,0},
{0,1,0,0},
{1,1,0,0}
};
System.out.println(perimeter(map));
}
public static int perimeter(int[][] map) {
int N = map.length;
int M = map[0].length;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1) {
return countPerimeter(map, i, j);
}
}
}
return 0;
}
private static List<int[]> adj(int[][] map, int[] v) {
int N = map.length;
int M = map[0].length;
List<int[]> adj = new ArrayList<>();
int i = v[0];
int j = v[1];
if(i-1 >= 0 && map[i-1][j] == 1) adj.add(new int[]{i-1, j});
if(i+1 < N && map[i+1][j] == 1) adj.add(new int[]{i+1, j});
if(j-1 >= 0 && map[i][j-1] == 1) adj.add(new int[]{i, j-1});
if(j+1 < M && map[i][j+1] == 1) adj.add(new int[]{i, j+1});
return adj;
}
private static int countPerimeter(int[][] map, int i, int j) {
int count = 0;
Queue<int[]> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
String key = i + "-" + j;
queue.add(new int[]{i, j});
visited.add(key);
count = count + countCellPerimeter(map, i, j);
while(!queue.isEmpty()) {
int[] w = queue.poll();
for(int[] v : adj(map, w)) {
key = v[0] + "-" + v[1];
if(!visited.contains(key)) {
visited.add(key);
queue.add(v);
count = count + countCellPerimeter(map, v[0], v[1]);
//System.out.println(key + " " + count);
}
}
}
return count;
}
}
class IslandPerimeter {
private static int countCellPerimeter(int[][] map, int i, int j) {
int count = 4;
if(i > 0 && map[i-1][j] == 1) count -= 2;
if(j > 0 && map[i][j-1] == 1) count -= 2;
return count;
}
public static void main(String...args) {
int[][] map = new int[][] {
{0,1,0,0},
{1,1,1,0},
{0,1,0,0},
{1,1,0,0}
};
System.out.println(perimeter(map));
}
public static int perimeter(int[][] map) {
int N = map.length;
int M = map[0].length;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1) {
return countPerimeter(map, i, j);
}
}
}
return 0;
}
private static List<int[]> adj(int[][] map, int[] v) {
int N = map.length;
int M = map[0].length;
List<int[]> adj = new ArrayList<>();
int i = v[0];
int j = v[1];
if(i-1 >= 0 && map[i-1][j] == 1) adj.add(new int[]{i-1, j});
if(i+1 < N && map[i+1][j] == 1) adj.add(new int[]{i+1, j});
if(j-1 >= 0 && map[i][j-1] == 1) adj.add(new int[]{i, j-1});
if(j+1 < M && map[i][j+1] == 1) adj.add(new int[]{i, j+1});
return adj;
}
private static int countPerimeter(int[][] map, int i, int j) {
int count = 0;
Queue<int[]> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
String key = i + "-" + j;
queue.add(new int[]{i, j});
visited.add(key);
count = count + countCellPerimeter(map, i, j);
while(!queue.isEmpty()) {
int[] w = queue.poll();
for(int[] v : adj(map, w)) {
key = v[0] + "-" + v[1];
if(!visited.contains(key)) {
visited.add(key);
queue.add(v);
count = count + countCellPerimeter(map, v[0], v[1]);
//System.out.println(key + " " + count);
}
}
}
return count;
}
}
Time cost O(island size), space cost O(island size).
