Count clusters covered by dashers

Q: Count clusters covered by dashers

This question evaluates understanding of grid traversal and connected-component detection in binary matrices, testing competencies in graph connectivity concepts, handling overlapping boolean grids, and algorithmic complexity analysis within the Coding & Algorithms domain.

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

You are given two m×n binary matrices of equal size: D for dasher availability and U for user presence. A cell value 1 indicates presence; 0 indicates absence. In U, define a cluster as a maximal group of horizontally or vertically adjacent 1-cells (4-neighborhood; diagonal adjacency does not connect). Task: Return the number of clusters in U such that every cell (i, j) in the cluster also has D[i][j] = 1 (i.e., every user in that cluster has a dasher at the same position). Describe your algorithm and analyze time and space complexity. Follow-up: For each qualifying cluster, output the list of its member coordinates (row, col) in a consistent order (e.g., increasing row, then column), and discuss how this affects complexity and memory usage.

Count clusters covered by dashers

Overview

Comments (0)