FastPrep
Problem · Matrix

Number of Distinct Islands (For L5 :)

Learn this problem
● MediumGoogle logoGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

Problem statement

In an ocean, there are islands marked by 1. Water is represented by 0. Determine how many unique shapes (no rotation or mirror) among these islands. Islands are connected 4-directionally.

Function

numDistinctIslands(grid: int[][]) → int

Complete the function numDistinctIslands in the editor.

numDistinctIslands has the following parameter:

  1. int[][] grid: a 2D array of integers representing the ocean

Returns

int: the number of unique island shapes

Examples

Example 1

grid = [[1, 1, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1], [0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0]]return = 4
There are 4 unique island shapes:
  • the 2 6-sized islands,
  • the 2 2-sized islands,
  • the 1 2-sized island,
  • the 1 1-sized island.
Standard BFS/DFS problem with a translation of the starting point to the origin of each island. The solution is done correctly and optimally with O(n) complexity.

Constraints

  • 1 ≤ grid.length, grid[i].length ≤ 500
  • grid[i][j] is 0 or 1.
  • Cells are connected only in the four cardinal directions.
  • Shapes are equal only under translation; rotations and reflections are distinct.

More Google problems

drafts saved locally
public int numDistinctIslands(int[][] grid) {
  // write your code here
}
grid[[1, 1, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1], [0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0]]
expected4
checking account