Java solution with detailed explanation
The idea of this solution is similar with other explanataions, but uses different data structures. The logic contains 2 steps:\n1. find all the islands\n2. chec
The idea of this solution is similar with other explanataions, but uses different data structures. The logic contains 2 steps:\n1. find all the islands\n2. check every cells with zero if they are "bridges" between islands.\n\nIn order to use a cell\'s address as a map key, the solution uses a hash function from the procedure getAddressHash();\n\nThe solution uses the next data structures:\n* **islands**. It is a list of sets, where a set contains all the cells of the island. So, a size of an island is a size of a set.\n* **addressIslandIndex**. It is a map, where a key is the hash of a cell\'s address and a value is an index of an island that contains this cell. It\'s used for getting an island index by a cell\'s address.\n\nSo, the algorith of the solution is the next:\n1. Go through the matrix and recursively find all the islands.\n2. Go through the matrix one more time and if a cell contains 0, check if it is a **bridge** between two islands and can connect them. It\'s possible to do this by just checking if the neighbouring cells are keys of the structure **addressIslandIndex**. If so, get a size of an island by its index and increase a local max size.\n\n```\n\nclass Solution {\n    List<Set<Integer>> islands; //Contains all the islands, where an island is a set of all included cells\n    Map<Integer,Integer> addressIslandIndex; //Key - a cell, value - index of an island that contains this cell.\n    int[][] grid;\n    int maxSquare; // result\n    public int largestIsland(int[][] grid) {\n        //initialise all the variables\n        islands = new ArrayList();        \n        addressIslandIndex = new HashMap();\n        maxSquare=0;\n        this.grid = grid;\n        \n        //fill list of islands\n        for (int i=0;i<grid.length;i++){\n            for (int j=0;j<grid.length;j++){\n                if (addressIslandIndex.containsKey(getAddressHash(i,j))) continue;\n                if (grid[i][j]==1){\n                    Set<Integer> island = new HashSet();\n                    fillIsland(island, i,j, islands.size());\n                    islands.add(island);\n                    maxSquare = Math.max(maxSquare,island.size());\n                }\n            }\n        }\n        \n        //arrays are used for getting addresses of neighbouring cells\n        int[] horizontalOffset = {0,0,1,-1};\n        int[] verticalOffset = {1,-1,0,0};\n        \n        //System.out.println(islands.size());\n        \n        //check all the possible bridges\n        for (int i=0;i<grid.length;i++){\n            for (int j=0;j<grid.length;j++){                \n                if (grid[i][j]==0){\n                    int localMax=1;\n                    \n                    //A set of visited islands is used in order not to use a size of an island several times\n                    Set<Integer> visitedIslands = new HashSet();\n                    for (int k=0;k<horizontalOffset.length;k++){\n                        \n                        int addressHash = getAddressHash(i+horizontalOffset[k],j+verticalOffset[k]);\n                        if (addressIslandIndex.containsKey(addressHash)){                            \n                            int islandIndex = addressIslandIndex.get(addressHash);\n                            if (!visitedIslands.contains(islandIndex)){\n                                localMax+=islands.get(islandIndex).size();\n                                visitedIslands.add(islandIndex);\n                            }\n                        }\n                    }\n                    maxSquare = Math.max(maxSquare,localMax);\n                }\n            }\n        }\n        \n        return maxSquare;\n    }\n    \n    private void fillIsland(Set<Integer> island, int i, int j, int islandIndex){\n        if (addressIslandIndex.containsKey(getAddressHash(i,j))) return; //cell was already checked\n        if (i<0 || j<0 || i>=grid.length || j>=grid.length) return; //cell is out of a grid\n        if (grid[i][j]==1){\n            island.add(getAddressHash(i,j));            \n            addressIslandIndex.put(getAddressHash(i,j),islandIndex);\n            //up\n            fillIsland(island, i, j-1, islandIndex);\n            //down\n            fillIsland(island, i, j+1, islandIndex);\n            //right\n            fillIsland(island, i+1, j, islandIndex);\n            //left\n            fillIsland(island, i-1, j, islandIndex);\n        }\n    }\n    \n    private int getAddressHash(int i, int j){\n        return i*1000 + j;\n    }\n}\n\n```\n\n*Thank you for reading this solution!*
['Java']