0538MediumArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindSortingMatrixHash Function

Distinct Reed Patch Shapes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_distinct_islands(grid: list[list[int]]) -> int:

Java

public int numDistinctIslands(int[][] grid)

The intended approach

Time O(rows * cols * log(rows * cols)) — every cell is visited once and each patch's offsets are sorted.Space O(rows * cols) for the visited flags plus the offset tuples held in the set.

Sweep the rectangle in row-major order. The first unvisited reed cell starts a patch, which is collected with an explicit stack that walks the four orthogonal steps and marks every cell it reaches, so each cell is handled once. To make two slid copies look identical, subtract the patch's smallest row from every row and its smallest column from every column, sort the resulting offset pairs, and drop that tuple into a set. The set's size is the answer. The stack is explicit rather than a recursive call chain because a solid 50 by 50 patch would otherwise nest 2500 calls deep.

Pythonentry point: num_distinct_islands

def num_distinct_islands(grid):
    # O(m*n*log(m*n)) time: one row-major sweep peels off each patch with an
    # explicit stack (so a 50x50 solid patch cannot overflow the interpreter
    # stack), then the patch is slid so its smallest row and smallest column
    # sit at zero and the sorted offset list becomes a comparable signature.
    rows = len(grid)
    cols = len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    shapes = set()
    for sr in range(rows):
        for sc in range(cols):
            if grid[sr][sc] != 1 or seen[sr][sc]:
                continue
            seen[sr][sc] = True
            stack = [(sr, sc)]
            cells = []
            while stack:
                r, c = stack.pop()
                cells.append((r, c))
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        if grid[nr][nc] == 1 and not seen[nr][nc]:
                            seen[nr][nc] = True
                            stack.append((nr, nc))
            base_r = min(r for r, _ in cells)
            base_c = min(c for _, c in cells)
            shapes.add(tuple(sorted((r - base_r, c - base_c) for r, c in cells)))
    return len(shapes)

The obvious version

Collect every patch as a set of absolute cell coordinates using a queue. Then build a list of representatives: for each patch, compare it against each representative already kept by shifting the patch so their top-left corners coincide and testing the two sets for equality. A patch that matches nothing becomes a new representative. The answer is the number of representatives.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_distinct_islands(grid):
    from collections import deque
    rows = len(grid)
    cols = len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    patches = []
    for sr in range(rows):
        for sc in range(cols):
            if grid[sr][sc] != 1 or seen[sr][sc]:
                continue
            seen[sr][sc] = True
            q = deque([(sr, sc)])
            cells = set()
            while q:
                r, c = q.popleft()
                cells.add((r, c))
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols:
                        if grid[nr][nc] == 1 and not seen[nr][nc]:
                            seen[nr][nc] = True
                            q.append((nr, nc))
            patches.append(cells)
    reps = []
    for cells in patches:
        matched = False
        for other in reps:
            if len(other) != len(cells):
                continue
            ar = min(r for r, _ in cells)
            ac = min(c for _, c in cells)
            br = min(r for r, _ in other)
            bc = min(c for _, c in other)
            moved = set()
            for r, c in cells:
                moved.add((r - ar + br, c - ac + bc))
            if moved == other:
                matched = True
                break
        if not matched:
            reps.append(cells)
    return len(reps)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in