Katkat
Back

Count regions with DFS

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.