import java.util.*;

class Solution {

    static class Node
    {
        public Node(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        int x;
        int y;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int maxRows = grid.length;
        int maxCols = grid[0].length;
        int maxIslandArea = 0;

        // Used to check if a 1 has been visited when performing BFS or DFS
        boolean[][] isNodeCheckedGrid = new boolean[maxRows][maxCols];

        // Check for the largest island by iterating through the grid
        for (int i = 0; i < maxRows; ++i)
        {
            for (int j = 0; j < maxCols; ++j)
            {
                // When we encounter a 1 and that 1 is not yet checked, then perform BFS at that node
                if (grid[i][j] == 1 && isNodeCheckedGrid[i][j] == false)
                {
                    int islandArea = countIslandBFS(new Node(i, j), isNodeCheckedGrid, grid);
                    if (islandArea > maxIslandArea)
                    {
                        maxIslandArea = islandArea;
                    }
                }
            }
        }

        return maxIslandArea;
    }

    // Perform an iterative BFS to count connected 1s
    public static int countIslandBFS(Node startNode, boolean[][] isCheckedGrid, int[][] grid)
    {
        int islandArea = 0;

        // Our priorityQ that stores our visited nodes
        Deque<Node> bfsQueue = new ArrayDeque<Node>();
        bfsQueue.add(startNode);

        while (bfsQueue.size() != 0)
        {
            islandArea++;
            Node currNode = bfsQueue.pop();
            Node leftNode = new Node(currNode.x - 1, currNode.y);
            Node rightNode = new Node(currNode.x + 1, currNode.y);
            Node topNode = new Node(currNode.x, currNode.y + 1);
            Node downNode = new Node(currNode.x, currNode.y - 1);

            // Check left
            if (isWithinGrid(leftNode, isCheckedGrid) && grid[leftNode.x][leftNode.y] == 1)
            {
                bfsQueue.add(leftNode);
            }
            // Check right
            if (isWithinGrid(rightNode, isCheckedGrid) && grid[rightNode.x][rightNode.y] == 1)
            {
                bfsQueue.add(rightNode);
            }
            // Check top
            if (isWithinGrid(topNode, isCheckedGrid) && grid[topNode.x][topNode.y] == 1)
            {
                bfsQueue.add(topNode);
            }
            // Check down
            if (isWithinGrid(downNode, isCheckedGrid) && grid[downNode.x][downNode.y] == 1)
            {
                bfsQueue.add(downNode);
            }
        }

        return islandArea;
    }

    // Simple boolean check to see if a node is within our grid
    public static boolean isWithinGrid(Node node, boolean[][] grid)
    {
        if (node.x >= 0 && node.x < grid.length && node.y >= 0 && node.y < grid[0].length)
        {
            if (grid[node.x][node.y] == false)
            {
                grid[node.x][node.y] = true;
                return true;
            }
        }
        return false;
    }
}