Easy

Meta-styleAmazon-style

Count Connected Land Regions in a Grid DSA Interview

Given a 2D grid of land and water cells, count the number of distinct connected land regions, where cells are connected horizontally or vertically.

Mock Interview with AI

1. Problem Statement

You are given a 2D grid where each cell is land (1) or water (0). Count the number of connected land regions, where connectivity is horizontal or vertical only.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify adjacency rules and grid mutability before coding.
✓Explain a naive re-scanning baseline and improve to a visited-tracking flood fill.
✓Think aloud while implementing careful traversal and boundary checks.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and pace the easy core problem to leave room for a coding follow-up.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies that connectivity is 4-directional (not diagonal), confirms the grid is rectangular, and asks whether the grid may be empty.
✓Confirms whether the input grid may be mutated during traversal or an external visited structure is preferred.

Staff-level signals

◆Raises how a very large grid affects the choice between recursion and an explicit stack for traversal.

Common red flags

×Codes immediately while assuming diagonal connectivity without confirming.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that re-explores land cells without marking them visited, identifies the resulting redundant work or infinite loop risk, and improves to a visited-tracking DFS or BFS flood fill.
✓Explains why marking a cell as visited immediately upon first visiting it prevents recounting the same region.

Staff-level signals

◆Discusses the tradeoff between recursive DFS (simpler code, stack risk) and iterative BFS/DFS with an explicit stack or queue (more code, no recursion depth risk).

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the visited-marking invariant while implementing.
✓Completes the easy core problem efficiently enough to leave meaningful time for a follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.
×Spends most of the interview on the easy core problem and leaves insufficient time for a follow-up.

Implementation correctness

25%

Senior signals

✓Implements a correct flood fill that, for every unvisited land cell, marks the entire connected region visited and increments the region count once per region.
✓Handles an empty grid, an all-water grid, an all-land grid, and a single-cell grid.
✓Provides a convincing invariant argument for why each region is counted exactly once.

Common red flags

×Counts diagonal neighbors as connected or fails to mark cells visited, causing overcounting.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clear boundary checks and a defined visited-tracking mechanism.

Common red flags

×Contains out-of-bounds access risks or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, including a drawn grid.
✓Covers an empty grid, all water, all land, and multiple separate regions of varying shapes.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States time complexity proportional to the number of cells and auxiliary space for the visited structure or recursion stack, comparing it with the naive re-exploration baseline.

Staff-level signals

◆Discusses recursion depth risk for very large connected regions.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up after solving an easy first problem, despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Re-exploring land cells without tracking visited state risks overcounting regions or infinite loops.
A visited-tracking flood fill (DFS or BFS) achieves linear time in the number of cells using auxiliary space for the visited structure or traversal frontier.
Mutating the input grid in place to mark visited cells saves auxiliary space but destroys the original input, which may not be acceptable.

Practice follow-up questions

1.Coding follow-up: modify the solution to return the size (cell count) of the largest connected land region instead of the total region count.
2.Verbal extension: how would the approach change if the grid were too large to fit in memory and had to be processed in row-by-row chunks?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Grid TraversalDFS/BFSConnected ComponentsComplexity Analysis