Quick Overview

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.

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.

Count Islands using BFS (without modifying the grid)

You are given an `m x n` binary grid `grid` where `1` represents land and `0` represents water. Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity). Return the number of islands in the grid. **Constraints on your approach:** - You must solve it using **BFS** (breadth-first search). - You are **not allowed to modify `grid` in-place** (you cannot flip visited `1`s to `0`s). Use a separate `visited` structure to track explored cells. ### Input/Output - **Input:** `grid: List[List[int]]` - **Output:** integer count of islands

Constraints

  • 1 <= m, n <= 200
  • grid[i][j] is 0 or 1
  • Must use BFS
  • Must NOT modify grid in-place; use a separate visited structure

Examples

Input: ([[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]],)

Expected Output: 3

Explanation: Top-left 2x2 block (1 island), the single 1 at (2,2), and the horizontal pair at (3,3)-(3,4) = 3 islands.

Input: ([[1,1,1],[0,1,0],[1,1,1]],)

Expected Output: 1

Explanation: All land cells are connected through the center column into one island.

Hints

  1. Scan every cell. When you hit a land cell that hasn't been visited yet, you've found a new island — increment your count and BFS-flood the whole island.
  2. Because you can't overwrite the grid, keep a parallel boolean `visited[m][n]` matrix and mark cells there as you enqueue them.
  3. Mark a cell visited at enqueue time (not dequeue time) so the same cell is never added to the queue twice.

Count Distinct Island Shapes (translation-invariant)

You are given an `m x n` binary grid `grid` where `1` represents land and `0` represents water. Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity). Two islands are considered the **same shape** if one can be **translated** (shifted up/down/left/right) to match the other exactly. Rotations and reflections do **not** count as the same shape. Return the number of **distinct island shapes** in the grid. **Constraints on your approach:** - Use **BFS** to discover each island. - Do **not** modify `grid` in-place; use a separate `visited` structure. ### Input/Output - **Input:** `grid: List[List[int]]` - **Output:** integer count of distinct island shapes

Constraints

  • 1 <= m, n <= 200
  • grid[i][j] is 0 or 1
  • Same shape = translation only (no rotation/reflection)
  • Use BFS; do NOT modify grid in-place

Examples

Input: ([[1,1,0,0],[1,0,0,0],[0,0,1,1],[0,0,1,0]],)

Expected Output: 1

Explanation: Both islands are the same L-tromino shape after translation, so there is 1 distinct shape.

Input: ([[1,1,0,1,1],[0,0,0,0,0],[1,1,0,1,0],[1,0,0,1,0]],)

Expected Output: 3

Explanation: Two horizontal dominoes (same shape), one L-tromino, and one vertical domino -> distinct shapes are {horizontal domino, L-tromino, vertical domino} = 3.

Hints

  1. Collect every cell of an island during BFS, then convert that set of coordinates into a translation-invariant signature.
  2. To make the signature translation-invariant, subtract the island's minimum row and minimum column from every cell so each island is re-anchored to (0,0).
  3. Sort the normalized coordinate list and store it (as a tuple/string) in a set. The answer is the size of the set. Sorting guarantees two islands discovered in different orders produce identical keys.

Loading coding console...