FastPrepNumber of Distinct Islands (For L5 :)

Number of Distinct Islands (For L5 :)

Google logoGoogle● MediumFULLTIMEPHONE SCREEN
Learn

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

See Google hiring insights
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…