Count clusters covered by dashers
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: Count clusters covered by dashers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given two m x n binary matrices of equal size: `D` for dasher availability and `U` for user presence. A cell value of `1` indicates presence; `0` indicates absence.
In `U`, a **cluster** is a maximal group of horizontally or vertically adjacent `1`-cells (4-neighborhood; diagonal adjacency does NOT connect cells).
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 the cluster has a dasher at the same position.
Write a function `countCoveredClusters(D, U)` that returns this count.
**Example**
```
D = [[1,1],
[1,1]]
U = [[1,0],
[0,1]]
```
There are two clusters in U (the single cell (0,0) and the single cell (1,1)). Both are fully covered by D, so the answer is `2`.
**Approach.** Scan every cell of `U`. When you find an unvisited user cell, flood-fill (BFS or DFS) its whole connected component using only 4-directional moves, marking each cell visited. While exploring, check whether every member cell also has `D == 1`. If the entire cluster is covered, increment the count. Each cell is visited once, giving O(m·n) time and O(m·n) space for the visited grid and the traversal frontier.
**Follow-up.** For each qualifying cluster, you could additionally collect its member coordinates `(row, col)`. Sorting them by increasing row then column adds O(k log k) per cluster of size k (or O(m·n) total if you collect in scan order). Memory grows by the total number of qualifying user cells stored.
Constraints
- 1 <= m, n (matrices may also be empty, in which case return 0)
- D and U have identical dimensions m x n
- Every cell of D and U is 0 or 1
- Clusters use 4-directional (horizontal/vertical) adjacency only; diagonals do not connect
- A cluster qualifies only if EVERY one of its cells has D == 1
Examples
Input: ([[1,1],[1,1]], [[1,0],[0,1]])
Expected Output: 2
Explanation: Two single-cell clusters at (0,0) and (1,1); both have D==1, so both qualify.
Input: ([[1,0],[1,1]], [[1,1],[1,1]])
Expected Output: 0
Explanation: All four user cells form one cluster, but D[0][1]==0, so the cluster is not fully covered.
Hints
- Iterate over all cells; when you hit an unvisited user cell (U==1), it is the seed of a new cluster — flood-fill it.
- Use BFS or DFS with only the 4 orthogonal neighbors. Mark cells visited as you push them so you never count a cluster twice.
- Track a boolean for the current cluster: it stays true only if every visited cell also satisfies D[i][j]==1. Don't break early — you must mark the whole component visited even if it already fails coverage.
- Edge cases: empty matrix returns 0; a single user cell with no dasher under it does not qualify.