Find connected region sizes in matrix

Q: Find connected region sizes in matrix

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an m x n grid of characters grid and a target character ch, implement: (

sizeOfRegion(grid, r0, c0, ch) -> int that returns the size of the 4-directionally connected region containing (r0, c
if grid[r0][c0] == ch, otherwise 0. (
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.

Find connected region sizes in matrix

Overview

Comments (0)