3
\$\begingroup\$

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;
    }
}
\$\endgroup\$
2
\$\begingroup\$

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 ifs 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.