Count islands and distinct shapes
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 200. Number of Islands LeetCode 694. Number of Distinct Islands
https://leetcode.com/problems/number-of-islands/description/ https://leetcode.com/problems/number-of-distinct-islands/description/
Quick Answer: This question evaluates a candidate's understanding of grid-based graph traversal and connected-component detection, along with the ability to recognize and canonicalize distinct island shapes.
Given a binary grid of 0s and 1s, count the total number of islands and the number of distinct island shapes. An island is a maximal group of 1s connected 4-directionally (up, down, left, right). Two islands are the same shape if one can be translated (shifted) to match the other; rotations and reflections do not count. Return [number_of_islands, number_of_distinct_shapes].
Constraints
- 1 <= rows, cols <= 200
- grid[i][j] is 0 or 1
- Connectivity is 4-directional (up, down, left, right)
- Two islands are the same shape only under translation; rotations/reflections are different
- Return format: [number_of_islands, number_of_distinct_shapes]
Solution
from typing import List
def count_islands_and_distinct_shapes(grid: List[List[int]]) -> List[int]:
if not grid or not grid[0]:
return [0, 0]
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
islands = 0
shapes = set()
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and not visited[r][c]:
islands += 1
origin_r, origin_c = r, c
stack = [(r, c)]
visited[r][c] = True
rel = []
while stack:
cr, cc = stack.pop()
rel.append((cr - origin_r, cc - origin_c))
for dr, dc in directions:
nr, nc = cr + dr, cc + dc
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
visited[nr][nc] = True
stack.append((nr, nc))
rel.sort()
shapes.add(tuple(rel))
return [islands, len(shapes)]
Explanation
Iterate over the grid. When a land cell is found that has not been visited, start a DFS to explore its entire island, marking cells visited. To capture the island's shape independent of its position, for each cell in the island record the coordinate relative to the first cell of that island. Sort these relative coordinates to form a canonical representation and insert it into a set. The number of DFS starts is the number of islands; the size of the set is the number of distinct shapes.
Time complexity: O(rows * cols). Space complexity: O(rows * cols).
Hints
- Traverse each unvisited land cell with DFS or BFS to mark its island.
- Record each island's cells relative to the starting cell to normalize by translation.
- Sort the relative coordinates to get a canonical shape representation and store it in a set.
- Use only 4-directional neighbors; diagonals do not connect islands.