Amazon | Phone screen | Number of distinct islands
Anonymous User
2374
AmazonInterview

Location: Seattle
Role: SDE

Given a non-empty 2D array grid of 0's(water) and 1's(land), an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) Return the distinct islands(1's) count, here distinct island means they should not have the same size of island(made from land(1's)) in grid:

Code =>

class Solution {
    // time complexity - m*n,  space complexity - m*n
    public int getDistinctCount(int[][] grid) {
        int size = 0;
		Set<Integer> set = new HashSet<>();
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]==1){
                    size = getArea(grid, i, j);
					set.add(size);
                }
            }
        }
        return set.size();
    }
    
    private int getArea(int[][] grid, int row, int col){
        if(row<0 || row>grid.length-1 
           || col<0 || col> grid[0].length-1
          || grid[row][col]!=1)
            return 0;
        grid[row][col]=-1;
        return 1+getArea(grid, row+1, col)
                +getArea(grid, row-1, col)
                +getArea(grid, row, col+1)
                +getArea(grid, row, col-1);
    }
}
Comments (2)