Count Distinct Island Shapes in a Binary Grid
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an `m x n` binary grid `grid`, where `grid[i][j]` is either `0` (water) or `1` (land).
An **island** is a maximal group of `1`-cells connected **4-directionally** (up, down, left, right). Diagonal adjacency does **not** connect cells.
Two islands are considered to have the **same shape** if and only if one island can be translated (shifted horizontally and/or vertically, **without rotating or reflecting**) so that it exactly coincides with the other island, cell for cell.
Return the number of **distinct island shapes** in the grid.
**Input**
- `grid`: a list of `m` rows, each a list of `n` integers, each `0` or `1`.
**Output**
- A single integer: the count of distinct island shapes.
**Constraints**
- `1 <= m, n <= 50`
- `grid[i][j]` is `0` or `1`
**Edge cases your solution must handle correctly**
- A grid containing no `1`-cells (the answer is `0`).
- Single-cell islands: all `1x1` islands share one shape regardless of position.
- Islands touching the grid border.
- Multiple islands with identical shapes located at different positions (they count once).
- A grid completely filled with `1`s (one island, one shape).
**Example 1**
```
grid = [
[1, 1, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 1]
]
```
Output: `2`
There are two islands. The first occupies relative cells `{(0,0), (0,1), (1,0)}` and the second `{(0,0), (0,1), (1,1)}`. No translation maps one onto the other (rotations/reflections are not allowed), so there are 2 distinct shapes.
**Example 2**
```
grid = [
[1, 1, 0, 1, 1],
[1, 0, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 1, 0, 0, 0]
]
```
Output: `1`
All three islands are the same L-shaped triomino translated to different positions, so there is exactly 1 distinct shape.
**Example 3**
```
grid = [
[0, 0],
[0, 0]
]
```
Output: `0`
There are no islands.
Quick Answer: This question evaluates a candidate's understanding of grid-based connected components and spatial equivalence, measuring competency in representing and distinguishing island shapes regardless of their location.
You are given an `m x n` binary grid `grid`, where `grid[i][j]` is either `0` (water) or `1` (land).
An **island** is a maximal group of `1`-cells connected **4-directionally** (up, down, left, right). Diagonal adjacency does **not** connect cells.
Two islands have the **same shape** if and only if one island can be **translated** (shifted horizontally and/or vertically, **without rotating or reflecting**) so that it exactly coincides with the other, cell for cell.
Return the number of **distinct island shapes** in the grid.
**Input**
- `grid`: a list of `m` rows, each a list of `n` integers, each `0` or `1`.
**Output**
- A single integer: the count of distinct island shapes.
**Constraints**
- `1 <= m, n <= 50`
- `grid[i][j]` is `0` or `1`
**Edge cases to handle**
- A grid containing no `1`-cells (answer is `0`).
- Single-cell islands: all `1x1` islands share one shape regardless of position.
- Islands touching the grid border.
- Multiple identical shapes at different positions count once.
- A grid completely filled with `1`s (one island, one shape).
Constraints
- 1 <= m, n <= 50
- grid[i][j] is 0 or 1
- Islands are connected 4-directionally only (no diagonals)
- Shapes are compared by translation only — no rotation or reflection
Examples
Input: [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,1,1],[0,0,0,0,1]]
Expected Output: 2
Explanation: Two islands. The first is {(0,0),(0,1),(1,0)}, the second normalizes to {(0,0),(0,1),(1,1)}. No translation maps one onto the other, so 2 distinct shapes.
Input: [[1,1,0,1,1],[1,0,0,1,0],[0,0,0,0,0],[0,1,1,0,0],[0,1,0,0,0]]
Expected Output: 1
Explanation: All three islands are the same L-shaped triomino translated to different positions, so exactly 1 distinct shape.
Hints
- Flood-fill (DFS or BFS) each unvisited land cell to collect all cells of one island, marking them visited so you never process an island twice.
- To make two translated islands compare equal, normalize each island by subtracting the minimum row and minimum column from every cell — this pins every shape to a common origin at (0, 0).
- Store each normalized island as a canonical, order-independent key (e.g. a frozenset of (row, col) offsets, or a sorted tuple) and put it in a set; the answer is the size of that set.
- Alternative canonicalization: record the DFS traversal path as a string of direction moves plus a terminator, which also uniquely encodes a translation-invariant shape.