Find connected region sizes in matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given an m x n grid of characters grid and a target character ch, implement:
(
1) sizeOfRegion(grid, r0, c0, ch) -> int that returns the size of the 4-directionally connected region containing (r0, c
0) if grid[r0][c0] == ch, otherwise 0.
(
2) countRegions(grid, ch) -> int that returns the number of distinct 4-directionally connected regions composed of ch in the entire grid.
Constraints: 1 <= m, n <= 2000. Use DFS (recursive or iterative). Analyze time and space complexity, and discuss how to avoid recursion depth limits for worst-case inputs.
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.