Show problems as
Classic problem #694MediumArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindSortingMatrixHash Function

Number of Distinct Islands

Real-world version: Distinct Reed Patch Shapes
Tracked in this browser only
Read Number of Distinct Islands on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A wetland survey arrives as grid, a rectangle of cells where 1 marks a cell full of reeds and 0 marks open water.

A patch is a largest possible collection of reed cells that can be reached from one another by repeatedly stepping to a cell directly above, below, to the left or to the right. Two reed cells that meet only at a corner belong to different patches.

Two patches count as the same shape when one can be slid horizontally and vertically, without any turning or flipping, so that its cells land exactly on the other patch's cells. Return how many different shapes the survey contains.

Examples

Example 1

Input
grid = [[1, 1, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1], [0, 1, 0, 0, 1, 1]]
Output
2

There are four patches of three cells each. The patch rooted at row 0 column 0, the one at row 0 column 4 and the one at row 3 column 1 all slide onto one another. The patch in the bottom right corner covers row 3 column 5, row 4 column 4 and row 4 column 5, which no slide turns into any of the others, so two shapes occur.

Example 2

Input
grid = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]
Output
1

Corner contact does not join cells, so this survey holds three patches of one cell each. Every single cell slides onto every other, leaving one shape.

Example 3

Input
grid = [[1, 1, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1], [0, 0, 0, 1, 1, 0]]
Output
2

Both patches hold four cells arranged as two horizontal pairs on adjacent rows. In the upper patch the lower pair sits one column to the right of the upper pair; in the lower patch it sits one column to the left, and sliding cannot fix that, so two shapes occur.

Constraints

  • rows == grid.length
  • cols == grid[i].length
  • 1 <= rows, cols <= 50
  • grid[i][j] is either 0 or 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_distinct_islands(grid: list[list[int]]) -> int:
Java
public int numDistinctIslands(int[][] grid)

More on the same topics