How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at TikTok during technical interviews.

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.

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

Expected Output: 0

Explanation: All water, so there are no islands.

Input: ([[1]],)

Expected Output: 1

Explanation: A single land cell is one island.

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

Expected Output: 3

Explanation: Three separate land cells separated by water = 3 islands.

Input: ([],)

Expected Output: 0

Explanation: Empty grid has no islands (edge case).

Hints

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.
Because you can't overwrite the grid, keep a parallel boolean `visited[m][n]` matrix and mark cells there as you enqueue them.
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.

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

Expected Output: 0

Explanation: No land, so no shapes.

Input: ([[1]],)

Expected Output: 1

Explanation: A single-cell island is one distinct shape.

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

Expected Output: 1

Explanation: Four separate single-cell islands all share the same single-cell shape -> 1 distinct shape.

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

Expected Output: 1

Explanation: All cells form one connected island, so there is exactly 1 shape.

Input: ([],)

Expected Output: 0

Explanation: Empty grid has no shapes (edge case).

Hints

Collect every cell of an island during BFS, then convert that set of coordinates into a translation-invariant signature.
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).
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.

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.