FastPrepFastPrep
Problem Brief

Number of Distinct Islands (For L5 :)

FULLTIMEPHONE SCREEN
See Google online assessment and 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

1Example 1

Input
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]]
Output
4
Explanation
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.
public int numDistinctIslands(int[][] grid) {
  // write your code here
}
Input

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]]

Output

4

Sign in to submit your solution.