Find connected region sizes in matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates proficiency in graph traversal and connected-component algorithms, specifically DFS-based region sizing and counting, along with algorithmic complexity analysis and considerations for recursion depth or iterative alternatives.
Size of Connected Region in Matrix
Constraints
- 1 <= m, n <= 2000
- grid[i][j] is a single character
- 0 <= r0 < m, 0 <= c0 < n
- Returns 0 if grid[r0][c0] != ch
Examples
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 0, 0, 'a')
Expected Output: 3
Explanation: The 'a' region containing (0,0) covers (0,0),(0,1),(1,0). The lone 'a' at (2,2) is disconnected, so size is 3.
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 0, 2, 'b')
Expected Output: 3
Explanation: The 'b' region containing (0,2) covers (0,2),(1,1),(1,2), size 3.
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 2, 2, 'a')
Expected Output: 1
Explanation: The 'a' at (2,2) is isolated from the top-left 'a' cluster, so its region size is 1.
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 0, 0, 'z')
Expected Output: 0
Explanation: grid[0][0] == 'a' != 'z', so the function returns 0.
Input: ([['x']], 0, 0, 'x')
Expected Output: 1
Explanation: Single-cell grid matching ch returns size 1.
Input: ([['x']], 0, 0, 'y')
Expected Output: 0
Explanation: Single cell 'x' does not equal target 'y', so 0.
Input: ([['a','a','a'],['a','a','a']], 1, 1, 'a')
Expected Output: 6
Explanation: Every cell is 'a' and all are connected, so the region is the whole 2x3 grid, size 6.
Hints
- Connectivity is 4-directional (up/down/left/right), never diagonal.
- If the starting cell does not equal ch, the region is empty — return 0 immediately.
- Use an explicit stack instead of recursion: with m, n up to 2000 a region can hold 4,000,000 cells, blowing past Python's default recursion limit and any practical call-stack depth.
- Mark a cell visited when you push it (not when you pop it) to avoid pushing the same cell multiple times.
Count Connected Regions of a Character
Constraints
- 1 <= m, n <= 2000
- grid[i][j] is a single character
- Regions are 4-directionally connected
- Returns 0 when ch does not appear in the grid
Examples
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'a')
Expected Output: 2
Explanation: Two 'a' regions: the top-left cluster {(0,0),(0,1),(1,0)} and the isolated (2,2).
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'b')
Expected Output: 1
Explanation: All 'b' cells {(0,2),(1,1),(1,2)} are connected, so 1 region.
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'c')
Expected Output: 1
Explanation: The two 'c' cells (2,0),(2,1) are adjacent, forming 1 region.
Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'z')
Expected Output: 0
Explanation: 'z' never appears, so there are 0 regions.
Input: ([['x']], 'x')
Expected Output: 1
Explanation: Single matching cell forms 1 region.
Input: ([['a','b','a'],['b','a','b'],['a','b','a']], 'a')
Expected Output: 5
Explanation: Checkerboard: the five 'a' cells at the corners and center are each isolated, giving 5 regions.
Input: ([['a','a','a'],['a','a','a']], 'a')
Expected Output: 1
Explanation: Every cell is 'a' and fully connected, so exactly 1 region.
Hints
- Iterate over every cell; start a new region only at an unvisited cell equal to ch.
- When you start a region, flood-fill it completely (DFS/BFS) so its other cells are not counted as new regions.
- A shared visited matrix across the whole scan guarantees each region is counted exactly once.
- Prefer an iterative stack over recursion: at m, n = 2000 a single region can span millions of cells.