Count regions with DFS
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an m x n grid of 0s and 1s, count the number of connected regions consisting of 1s using depth-first search (4-directional adjacency). Return the count. Discuss time and space complexity, show both recursive and iterative (stack-based) approaches, and explain how you would avoid revisiting cells. Consider edge cases like empty grids and very large inputs.
Quick Answer: This question evaluates proficiency in graph traversal and grid-based connected-component detection using depth-first search on a binary m x n grid, along with algorithmic complexity analysis and techniques to avoid revisiting cells.
