FastPrep

Description

Solutions

Number of Distinct Islands (For L5 :)

🔥 FULLTIME📚RELATED PROBLEMS

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:

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

Returns

int: the number of unique island shapes

Example 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.

Constraints:

:)