# Find number of islands Leetcode

Posted on

Problem

Here is the question:

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

And this is my proposed solution. Can someone please help me understand how can I improve the code. Any comments are most welcome.

``````public class NumberOfIsland {
private static final int MIN_ROW = 0;
private static final int MIN_COL = 0;
int noOfRows;
int noOfColumn;
boolean[][] isVisited;
char[][] gridArray;

public int numIslands(char[][] grid) {
final char LAND = '1';
final char WATER = '0';
int numOfIsLands = 0;

if(grid.length == 0) {
return 0;
}
gridArray = grid;

noOfRows = grid.length;
noOfColumn = grid[0].length;

// Assuming that no of rows and columns are constant.
isVisited = new boolean[noOfRows][noOfColumn];

for (int i = 0; i < noOfRows; i++) {
for (int j = 0; j < noOfColumn; j++) {
if(gridArray[i][j] == LAND && !isVisited[i][j]) {
doDFSStartingFromNode(i, j);
numOfIsLands++;
}
}
}

return numOfIsLands;
}

private void doDFSStartingFromNode(final int i, final int j) {

Stack<Coordinates> stack = new Stack<>();
stack.push(new Coordinates(i,j));

while (!stack.empty()) {
Coordinates peekedCoordinates = stack.peek();
if(Objects.isNull(peekedCoordinates)) {
return;
}
if(isNoMorePathAvailable(peekedCoordinates)) {
stack.pop();
} else {
stack.push(nextAvailablePath(peekedCoordinates));
}
}

}

private Coordinates nextAvailablePath(Coordinates peekedCoordinates) {
if(canMoveUp(peekedCoordinates)) {
isVisited[peekedCoordinates.x-1][peekedCoordinates.y] = true;
return new Coordinates(peekedCoordinates.x-1, peekedCoordinates.y);
} else if(canMoveRight(peekedCoordinates)) {
isVisited[peekedCoordinates.x][peekedCoordinates.y+1] = true;
return new Coordinates(peekedCoordinates.x, peekedCoordinates.y+1);
} else if(canMoveBottom(peekedCoordinates)) {
isVisited[peekedCoordinates.x+1][peekedCoordinates.y] = true;
return new Coordinates(peekedCoordinates.x+1, peekedCoordinates.y);
} else if(canMoveLeft(peekedCoordinates)) {
isVisited[peekedCoordinates.x][peekedCoordinates.y-1] = true;
return new Coordinates(peekedCoordinates.x, peekedCoordinates.y-1);
}
return null;
}

private boolean isNoMorePathAvailable(final Coordinates peekedCoordinates) {
if(!canMoveUp(peekedCoordinates) && !canMoveRight(peekedCoordinates) && !canMoveBottom(peekedCoordinates) && !canMoveLeft(peekedCoordinates) ) {
return true;
}
return false;
}

private boolean canMoveBottom(Coordinates peekedCoordinates) {
int x = peekedCoordinates.x;
int y = peekedCoordinates.y;
if((x + 1 <= noOfRows - 1) && (gridArray[x+1][y] == '1' ) && !isVisited[x + 1][y]) {
return true;
}
return false;
}

private boolean canMoveLeft(Coordinates peekedCoordinates) {
int x = peekedCoordinates.x;
int y = peekedCoordinates.y;
if((y-1 >= MIN_COL) && (gridArray[x][y-1] == '1' ) && !isVisited[x][y-1]) {
return true;
}
return false;
}

private boolean canMoveRight(Coordinates peekedCoordinates) {
int x = peekedCoordinates.x;
int y = peekedCoordinates.y;
if((y+1 <= noOfColumn -1) && (gridArray[x][y+1] == '1' ) && !isVisited[x][y+1]) {
return true;
}
return false;
}

private boolean canMoveUp(Coordinates peekedCoordinates) {
int x = peekedCoordinates.x;
int y = peekedCoordinates.y;
if((x-1 >= MIN_ROW) && (gridArray[x-1][y] == '1') && !isVisited[x-1][y]) {
return true;
}
return false;
}
}

class Coordinates {
int x;
int y;

public Coordinates(int x, int y) {
this.x = x;
this.y = y;
}
}
``````

Solution

# Code Organization

Assigning fields in the method. Intialize your fields in the constructor. It isn’t clear what `numIslands` does. The public API lies. It pretends to be a “service” whereas it actually is a “method object”. Services should be immutable.

API says I could use this class like so:

``````final NumberOfIsland n = new NumberOfIsland();
testCases.parallelStream().map(grid -> n.numIslands(grid));
``````

Intended usage is actually:

``````testCases.parallelStream().map(grid -> new NumberOfIsland().numIslands(grid));
``````
• Constants are defined in local scope, and later also used hardcoded. If you define a constant replace all instances of the literal value. for example `char LAND = '1'` should be a static field and later `'1'`s also should be changed.

Whereas you can omit MIN_ROW, because you can assume everyone knows 0 is the minimum array index.

• `doDFSStartingFromNode(final int i, final int j)`:
In this method you create a `Coordinates` from `i`, `j` and never use them again. `i`, `j` are not a node, they are a pair of indices. You can pass the object into the method instead. such that the signature can now become `doDFS(Node startNode)`.

## Naming problems

• Classes are nouns, methods are verbs etc. These are not hard rules but even if you violate them, you should name your code artefacts such that your code reads well regardless.
Compare:

A `NumberOfIsland` consists of a `gridArray`, an `isVisited` matrix,

with

A `NumberOfIslandsSolver` consists of a `grid`, a `visited` matrix,

• `Coordinates` Do not use plural names unless it’s a collection. And this is not a collection, you cannout add a coordinate to coordinates etc. (Even when a class is a collection, name it such that reader can guess its behavior, CoordinateSet, CoordinateQueue etc.) Location, Position, or Cell, or GridCell etc are better names for this class.

## Redundant code

• `canMoveBottom` etc are copy pasted code. and in each of them `y+1` etc is repeated three times. Factor out repetitive code.

## Inefficiencies

• You should use an `ArrayDeque` instead of `Stack`. Don’t use synchronized classes unless you really know what you are doing, or it causes poor performance. (Similarly you shouldn’t use `Vector` where an `ArrayList` will do, `StringBuffer` where a `StringBuilder` will do, etc… (Protip: If you encounter a class with synchronized methods in an API, it’s either very special purpose or a legacy class kept around for backwards compatibility; and you probably should use something else.)

• You call `canMoveX` thrice: once in `nextAvailablePath`, once in `isNoMorePathAvailable` and once after. Organize your logic such that you shouldn’t call that code multiple times.

## Style

• If you follow standard java spacing you can lose unnecessary parentheses and `if`s etc like so:

``````private boolean canMoveRight(Coordinates peekedCoordinates) {
int x = peekedCoordinates.x;
int y = peekedCoordinates.y;
int newY = y + 1;

return newY < noOfColumn && gridArray[x][newY] == '1' && !isVisited[x][newY];
}
``````
• Speaking of standard spacing; put a space after keywords `if`, `while`, `try` so they don’t look weird.