Quick Overview

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.

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.

Size of Connected Region in Matrix

Given an `m x n` grid of characters `grid`, a starting cell `(r0, c0)`, and a target character `ch`, return the size of the 4-directionally connected region of `ch` that contains `(r0, c0)`. A region is a maximal set of cells all equal to `ch` that are connected horizontally or vertically (not diagonally). If `grid[r0][c0] != ch`, return `0`. Use DFS (an explicit stack is preferred over recursion to avoid hitting recursion-depth limits — with `m, n` up to 2000 a worst-case fully-connected region can contain 4,000,000 cells, far exceeding the default recursion limit). **Constraints:** - `1 <= m, n <= 2000` - `grid[i][j]` is a single character - `0 <= r0 < m`, `0 <= c0 < n`

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.

Hints

  1. Connectivity is 4-directional (up/down/left/right), never diagonal.
  2. If the starting cell does not equal ch, the region is empty — return 0 immediately.
  3. 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.
  4. 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

Given an `m x n` grid of characters `grid` and a target character `ch`, return the number of distinct 4-directionally connected regions composed entirely of `ch` in the whole grid. Two `ch` cells belong to the same region if they are connected horizontally or vertically (not diagonally). Scan every cell once; whenever you encounter an unvisited `ch` cell, increment the count and flood-fill its entire region so it is not counted again. Use DFS with an explicit stack to stay safe against recursion-depth limits at the maximum grid size. **Constraints:** - `1 <= m, n <= 2000` - `grid[i][j]` is a single 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.

Hints

  1. Iterate over every cell; start a new region only at an unvisited cell equal to ch.
  2. When you start a region, flood-fill it completely (DFS/BFS) so its other cells are not counted as new regions.
  3. A shared visited matrix across the whole scan guarantees each region is counted exactly once.
  4. Prefer an iterative stack over recursion: at m, n = 2000 a single region can span millions of cells.

Loading coding console...