Max Area of Island

A non-recursive solution using stack.

class Solution {

    public int maxAreaOfIsland(int[][] grid) {
        Stack<Point> stack = new Stack<>();
        int max = 0;

        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                if (grid[row][column] == 1) {
                    grid[row][column] = 0;
                    stack.add(new Point(row, column));
                }
                if (!stack.isEmpty()) {
                    int currentMax = consumeStack(stack, grid);
                    max = Math.max(max, currentMax);
                }
            }
        }

        return max;
    }

    public int consumeStack(Stack<Point> stack, int[][] grid) {
        Integer max = 0;
        while(!stack.isEmpty()) {
            Point point = stack.pop();
            int row = point.row;
            int column = point.column;
            max++;
            if (row < grid.length - 1)
                if (grid[row + 1][column] == 1) {
                    grid[row + 1][column] = 0;
                    stack.add(new Point(row + 1, column));
                }
            if (row > 0)
                if (grid[row - 1][column] == 1) {
                    grid[row - 1][column] = 0;
                    stack.add(new Point(row - 1, column));
                }
            if (column > 0)
                if (grid[row][column - 1] == 1) {
                    grid[row][column - 1] = 0;
                    stack.add(new Point(row , column - 1));
                }
            if (column < grid[0].length - 1)
                if (grid[row][column + 1] == 1) {
                    grid[row][column + 1] = 0;
                    stack.add(new Point(row , column + 1));
                }
        }
        return max;
    }
}

class Point {
    int row;
    int column;
    Point(int row, int column) {
        this.row = row;
        this.column = column;
    }
}

Here is a recursive solution.

TODO:

Last updated