Count islands using BFS without modifying grid
Company: TikTok
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: HR Screen
You are given an `m x n` binary grid `grid` where:
- `1` represents land
- `0` represents water
- Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity).
### Part A
Return the number of islands in the grid.
**Constraint:** You must solve it using **BFS**, and you are **not allowed to modify `grid` in-place** (e.g., you cannot flip visited `1`s to `0`s).
### Part B (follow-up)
Two islands are considered the **same shape** if one can be translated (shifted up/down/left/right) to match the other exactly (rotations/reflections do **not** count unless explicitly stated).
Return the number of **distinct island shapes** in the grid.
### Input/Output
- **Input:** `grid: List[List[int]]`
- **Output (Part A):** integer count of islands
- **Output (Part B):** integer count of distinct island shapes
### Assumptions / Constraints
- `1 <= m, n <= 200` (or similar)
- Time should be near `O(mn)`
- Extra space allowed for visited tracking and shape encoding
Quick Answer: This question evaluates understanding of BFS-based graph traversal on grids, managing visited state without modifying the input, and techniques for encoding island shapes to detect distinct configurations.