Skip to content

Instantly share code, notes, and snippets.

@jiahaoliuliu
Created November 17, 2018 16:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jiahaoliuliu/3015e1dabd2b8876be39d0d5a7d5f0c5 to your computer and use it in GitHub Desktop.
Save jiahaoliuliu/3015e1dabd2b8876be39d0d5a7d5f0c5 to your computer and use it in GitHub Desktop.
SImple algorithm to find the number of islands in a matrix
/**
* Given a matrix of 0 and 1, where 0 represents water and 1 represent land.
* Two pieces of land are connected if they are touching each other(vertical, horizontal or diagonal)
* Please write a method that counts the number of islands.
*
* Here is an example :
* 0 (1 1) 0 0 0 [1]
* 0 (1) 0 0 [1 1] 0
* 0 (1 1) 0 0 [1] 0
* 0 0 0 0 0 0 0
* 0 "1 1 1 1 1" 0
*
* The number of islands is three.
* Write a method count the number of islands
*/
public class NumberOfIslands {
static int numberOfIslands(int[][] surface) {
int result = 0;
for (int i = 0; i < surface.length; i++) {
for (int j = 0; j < surface[i].length; j++) {
int value = surface[i][j];
if (value == 0) {
continue;
} else if (value == 1) {
if (isFirstElementOfTheIsland(i, j, surface)) {
result++;
}
}
}
}
return result;
}
/**
* Check if it is the first element of an island. This is that for any position previous
* to this they are always 0
* 0 0 => true . Otherwise return false
* 0 -> 1
* 0
* @param row
* @param column
* @param surface
* @return
*/
private static boolean isFirstElementOfTheIsland(int row, int column, int[][]surface) {
return isLeftUpDiagonalWater(row, column, surface) &&
isLeftDownDiagonalWater(row, column, surface) &&
isPreviousRowWater(row, column, surface) &&
isPreviousColumnWater(row, column, surface);
}
private static boolean isPreviousColumnWater(int row, int column, int[][] surface) {
if (column == 0) {
return true;
}
return surface[row][column-1] == 0;
}
private static boolean isPreviousRowWater(int row, int column, int[][] surface) {
if (row == 0) {
return true;
}
return surface[row -1][column] == 0;
}
private static boolean isLeftUpDiagonalWater(int row, int column, int[][] surface) {
if ((row == 0) || (column == 0)) {
return true;
}
return surface[row - 1][column - 1] == 0;
}
private static boolean isLeftDownDiagonalWater(int row, int column, int[][] surface) {
if ((row == surface.length - 1) || (column == 0)) {
return true;
}
return surface[row + 1][column - 1] == 0;
}
public static void main(String... args) {
test1();
test2();
test3();
test4();
}
/**
*/
private static void test1() {
int[][] surface = {{}};
System.out.println(numberOfIslands(surface)); // it should return 0
}
/**
* 0 1 1 0
* 0 0 0 0
* 1 0 0 1
*/
private static void test2() {
int[][] surface = {{0, 1, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 1}};
System.out.println(numberOfIslands(surface)); // it should return 3
}
/**
* 0 1 1 0 0 0 1
* 0 1 0 0 1 1 0
* 0 1 1 0 0 1 0
* 0 0 0 0 0 0 0
* 0 1 1 1 1 1 0
*/
private static void test3() {
int[][] surface = {
{0, 1, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0}};
System.out.println(numberOfIslands(surface)); // it should return 3
}
/**
* 0 0 0 0 0 0 0
* 0 0 0 0 1 0 0
* 0 1 1 1 0 1 0
* 0 0 0 0 0 0 0
* 0 1 1 1 1 1 0
*/
private static void test4() {
int[][] surface = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0}};
System.out.println(numberOfIslands(surface)); // it should return 2
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment