FastPrep
Problem · Matrix

Number of Distinct Islands (For L5 :)

● MediumGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

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 Description

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
01 · 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.
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