Compute islands in a binary grid
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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.
Quick Answer: 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.