Count islands and distinct shapes

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/

Count Islands and Distinct 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]

Examples

Example 1

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

Explanation: There are 3 islands. The two L-shaped islands are the same shape by translation; the 2-cell horizontal island is different. Distinct shapes = 2.

Example 2

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

Explanation: Four single-cell islands. All have the same shape (single cell), so distinct shapes = 1.

Hints

1. Traverse each unvisited land cell with DFS or BFS to mark its island.
2. Record each island's cells relative to the starting cell to normalize by translation.
3. Sort the relative coordinates to get a canonical shape representation and store it in a set.
4. Use only 4-directional neighbors; diagonals do not connect islands.

Approach

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)