Count islands and implement BFS variant

Q: Count islands and implement BFS variant

This question evaluates a candidate's ability to apply grid and graph traversal concepts—counting connected components with four-directional connectivity—implement breadth-first search variants, and reason about correctness and linear-time (O(mn)) complexity.

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

Given a 2D grid of characters '1' (land) and '0' (water), count the number of distinct land regions where connectivity is four-directional (up, down, left, right). Implement a solution of your choice that runs in O(mn) time and explain its correctness and complexity. Then implement a second version that uses breadth-first search explicitly. Handle edge cases such as an empty grid, all-water grid, and very large dimensions, and provide tests to validate your solution on multiple nontrivial cases.

Count islands and implement BFS variant

Overview

Comments (0)