Count islands using BFS without modifying grid

Q: Count islands using BFS without modifying grid

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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 1s to 0s).

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

Count islands using BFS without modifying grid

Quick Overview

Part A

Part B (follow-up)

Input/Output

Assumptions / Constraints

Comments (0)