How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Count regions with DFS | Amazon Coding Question

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.

Given an `m x n` grid of `0`s and `1`s, count the number of connected regions consisting of `1`s. Two cells belong to the same region if they are both `1` and are 4-directionally adjacent (up, down, left, right). Diagonal adjacency does NOT connect cells. Return the total number of distinct regions. This is the classic "Number of Islands" problem solved with depth-first search. As you visit each cell, mark it as seen so you never revisit it — that keeps the traversal O(m·n). You can use either recursive DFS or an explicit stack (iterative DFS) to flood-fill each region; the stack-based form avoids deep recursion on very large or pathological inputs. Example: ``` grid = [[1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]] ``` There are 3 regions: the 2x2 block of 1s in the top-left, the single 1 in the middle, and the pair of 1s in the bottom-right. So the answer is `3`.

Constraints

1 <= m, n is the grid dimensions; the grid may also be empty ([] or [[]]), which has 0 regions.
grid[i][j] is either 0 or 1.
Adjacency is 4-directional only (up, down, left, right) — diagonals do not connect.
Mark each cell as visited the moment you enqueue/push it to avoid revisiting and double-counting.

Examples

Input: ([[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]],)

Expected Output: 3

Explanation: Three regions: the 2x2 block top-left, the lone 1 in the middle, and the pair of 1s bottom-right.

Input: ([[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1]],)

Expected Output: 8

Explanation: Checkerboard pattern — every 1 is isolated (no 4-directional neighbor that is also 1), so each of the 8 ones is its own region.

Input: ([[1,1,1],[1,1,1],[1,1,1]],)

Expected Output: 1

Explanation: All cells are 1 and fully connected, forming a single region.

Input: ([[0,0,0],[0,0,0]],)

Expected Output: 0

Explanation: No 1s, so there are no regions.

Input: ([],)

Expected Output: 0

Explanation: Empty grid edge case — returns 0 without indexing into a non-existent first row.

Input: ([[1]],)

Expected Output: 1

Explanation: Single cell containing a 1 is one region.

Input: ([[0]],)

Expected Output: 0

Explanation: Single cell containing a 0 has no regions.

Input: ([[1,0,1,1,0,1]],)

Expected Output: 3

Explanation: Single-row grid: the standalone 1, the connected pair '1,1', and the trailing standalone 1 — three regions.

Hints

Scan every cell. When you find a 1 that hasn't been visited yet, you've found a new region — increment your counter, then flood-fill the entire region so its cells aren't counted again.
Flood-fill with DFS: from the starting cell, visit all 4-directionally adjacent 1s, then their neighbors, and so on. Mark a cell as seen *before* pushing it so it's never added to the stack twice.
For the iterative version, use an explicit stack of (row, col). Pop a cell, look at its 4 neighbors, and push any in-bounds, unvisited 1-cells. This avoids recursion-depth limits on huge grids.
Handle empty inputs first: `[]` and `[[]]` should return 0 before you index into rows.

Quick Overview

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.