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