707/750 cases passed


  • 0
    R

    I know this is a lengthy code. I calculate the area of the islands and use a HashMap to store<Area, starting coordinates> . Whenever i find an island with the same area, i run dfs(checkDFS method) to check if both the islands are identical. I could not clear all testcases with this. If anyone could point out my mistake, would really appreciate it

    static int[] dx={1,0,0,-1};
        static int[] dy={0,1,-1,0};
        static int area;
        static boolean flag;
        public static void dfs(int x,int y, int[][] grid, int row, int col,boolean[][] v )     //calculating area logic remains same
        {
            v[x][y]=true;
            int testx,testy;
            for(int i=0;i<4;i++)
            {
                testx=x+dx[i];
                testy=y+dy[i];
                
                //boundary condition
                if(testx>=0 && testx<row && testy>=0 && testy<col && v[testx][testy]==false)
                {
                    if(grid[testx][testy]==1)
                    {
                        area++;
                        dfs(testx,testy,grid,row,col,v);
                    }
                }
            }
        }
        
        public static void checkDFS(int a,int b,int c,int d,int[][] grid,boolean[][] v,int row,int col)
        {
            v[a][b]=true;
            v[c][d]=true;
            
            int testx,testy;
            int testx1,testy1;
            boolean A,B;
            for(int i=0;i<4;i++)
            {
                testx=a+dx[i];
                testy=b+dy[i];
                testx1=c+dx[i];
                testy1=d+dy[i];
                
                if((testx>=0 && testx<row && testy>=0 && testy<col && v[testx][testy]==false))
                    A=true;
                else
                    A=false;
                
                if((testx1>=0 && testx1<row && testy1>=0 && testy1<col && v[testx1][testy1]==false))
                    B=true;
                else
                    B=false;
                
                //boundary condition
                if(A||B)
                {
                    //case 1
                    if(A==true && B==false)
                    {
                        if(grid[testx][testy]==1)
                            flag=false;
                    }
                    
                    //case 2
                    if(A==false && B==true)
                    {
                        if(grid[testx1][testy1]==1)
                            flag=false;
                    }
                    
                    //case 3 : both true
                    if(A==true && B==true)
                    {
                    if((grid[testx][testy]==1) &&(grid[testx1][testy1]==1) || (grid[testx][testy]==0) &&(grid[testx1][testy1]==0))
                    {
                        if((grid[testx][testy]==1) &&(grid[testx1][testy1]==1))
                            checkDFS(testx,testy,testx1,testy1,grid,v,row,col);
                    }
                    else
                    {
                        flag=false;
                    }
                }
                
            }
                
        }
        }
        
        public static int numDistinctIslands(int[][] grid) {
            Map<Integer,int[]>myMap= new HashMap<Integer,int[]> ();
            int row=grid.length;
            int col=grid[0].length;
            
            int ans=0;
          
            boolean[][] visited=new boolean[row][col];      //initially all false
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    if(grid[i][j]==1 && visited[i][j]==false)
                    {
                        
                        area=1;                                 //always starts with 1
                        dfs(i,j,grid,row,col,visited);
                        
                        if(myMap.containsKey(area))         //if area is already there in map
                        {
                            int[] arr=myMap.get(area);
                            flag=true;
                             boolean[][] v=new boolean[row][col];      //initially all false
                            checkDFS(arr[0],arr[1],i,j,grid,v,row,col);
                            if(flag==false)
                                ans++;
                        }
                        else
                        {
                            ans++;                      //if new area then obviously increase count
                            int[] arr=new int[2];
                            arr[0]=i;           //row number
                            arr[1]=j;           //column number
                            //enter in map
                            myMap.put(area,arr);
                        }
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.