Making a island large leetcode – spotting mistake Java

I am working on LeetCode problem 827. Making A Large Island:

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

My solution fails for the following test case:

[[1,1,0],[0,0,0], [1,1,0]]

The output of my code is 3, but 5 is expected.

Here is my code:

class Solution {
    public int largestIsland(int[][] grid) {
        int n=grid.length;
        int max=0;
        boolean hasZero=false;
        boolean[][] visited = new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    grid[i][j]=1;
                    max=Math.max(max,area(grid,n,i,j,visited));  
                    grid[i][j]=0;
                   // visited[i][j]=false;
                    hasZero=true;
                }
            }
        }
        
        return hasZero?max:n*n;
    }
    
    private int area(int[][] grid, int n, int i, int j, boolean[][] visited){
        if(i<0 || i>n-1 || j>n-1 || j<0 || grid[i][j]==0 || visited[i][j])
            return 0;
        
        visited[i][j]=true;
        int a1 =  area(grid,n,i+1,j,visited);
        int a2 =  area(grid,n,i,j+1,visited);
        int a3 = area(grid,n,i-1,j,visited);
        int a4 =  area(grid,n,i,j-1,visited);
            
        return 1+a1+a2+a3+a4;
    }
}

This solution is O(N^4) and I know other, more efficient working solutions, but I’m not able to spot what’s wrong with my attempt.

Could someone spot what is wrong?

Answer

The problem is that after you have marked an island as visited, it can no longer play a role in a better connection.

For instance, your failing test case:

[[1, 1, ],[0, 0, 0],[1, 1, 0]]

…can be depicted as:

 1 1 0
 0 0 0
 1 1 0

Your code will first try this (changing the value in brackets):

 1 1(1)
 0 0 0
 1 1 0

… and mark those as visited (I’ll mark those with “v”):

 v v v
 0 0 0
 1 1 0

…and so it finds 3 for max.

Then it will continue with finding the following:

 v v v
(1)0 0
 1 1 0

This will lead to a value of 3, which does not improve the previous value for max. But this is wrong, because it really connects with another island that you had marked visited. It should have found this:

 1 1 0
(1)0 0
 1 1 0

… which is 5.

As you already found working algorithms, I suppose this answers your question.