Compute islands in a binary grid

Q: Compute islands in a binary grid

This question evaluates a candidate's competency in modeling grids as graphs, detecting connected components, applying graph traversal algorithms (DFS/BFS) and disjoint-set (Union-Find) data structures, and analyzing algorithmic time and space 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

You are given an m-by-n grid of characters where '1' represents land and '0' represents water. Count the number of connected land masses (islands) using 4-directional connectivity (up, down, left, right) and return that count. Also implement a variant that returns the sizes of all islands in descending order. Discuss and compare DFS, BFS, and Union-Find approaches, including their time and space complexities.

Compute islands in a binary grid

Overview

Comments (0)