Count Connected Groups in a Relationship Matrix
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Count Connected Groups in a Relationship Matrix
### Problem
Implement `countConnectedGroups(related)`.
`related` is an `n x n` relationship matrix encoded as an array of strings. `related[i][j] == '1'` means entities `i` and `j` are directly connected; `related[i][j] == '0'` means they are not directly connected. Connectivity is transitive, so every entity belongs to exactly one connected group.
Return the number of connected groups.
### Function Contract
- Python: `def countConnectedGroups(related: list[str]) -> int`
- JavaScript: `function countConnectedGroups(related)` accepts a string array and returns an integer `Number`.
- Java: `int countConnectedGroups(List<String> related)`
- C++: `int countConnectedGroups(const vector<string>& related)`
Do not mutate `related`.
### Examples
```text
related = [
"1100",
"1110",
"0110",
"0001"
]
output = 2
```
Entities `0`, `1`, and `2` form one group; entity `3` forms the other.
```text
related = [
"100",
"010",
"001"
]
output = 3
```
```text
related = ["1"]
output = 1
```
### Constraints
- `1 <= n == related.length <= 300`.
- Every row has exactly `n` characters, each either `0` or `1`.
- `related[i][i] == '1'` for every `i`.
- The matrix is symmetric: `related[i][j] == related[j][i]`.
- Let `B` be the compact UTF-8 JSON byte length of the entire `related` array, including brackets, commas, and quotes. The strings contain only `0` and `1`, so no JSON escapes are needed. Inputs satisfy `B <= 96,000`.
- The returned integer is between `1` and `300`; its compact JSON encoding uses at most `3` bytes. Serialized input plus result is therefore at most `96,003` bytes.
- Target `O(n^2)` time and `O(n)` auxiliary space.
```hint Finish one group at a time
When an unseen entity starts a new group, mark every entity reachable from it before looking for the next unseen entity.
```
### Discussion Requirements
1. Explain why direct-neighbor counts do not determine the number of transitive groups.
2. Describe an iterative DFS, BFS, or union-find implementation.
3. Show why scanning the dense matrix takes `O(n^2)` time even when there are few groups.
4. Explain how the visited state ensures each group is counted exactly once.
Quick Answer: Count the transitive connected groups represented by a symmetric relationship matrix. Candidates should explain graph traversal or union techniques, visited-state correctness, dense-matrix complexity, and why direct neighbor counts do not reveal component count.
Implement countConnectedGroups(related). related is an n by n relationship matrix encoded as an array of strings. related[i][j] is '1' when entities i and j are directly connected and '0' otherwise. Connectivity is transitive, so every entity belongs to exactly one connected group. Return the number of connected groups and do not mutate related.
Constraints
- 1 <= n == related.length <= 300
- Every row has exactly n characters, each either 0 or 1
- related[i][i] is 1 for every i
- The matrix is symmetric
- The compact UTF-8 JSON byte length of related is at most 96000, and serialized input plus result is at most 96003 bytes
- The returned integer is between 1 and 300
Examples
Input: (['1100', '1110', '0110', '0001'],)
Expected Output: 2
Explanation: Entities 0, 1, and 2 form one group, and entity 3 forms another.
Input: (['100', '010', '001'],)
Expected Output: 3
Explanation: Each entity is isolated.
Hints
- When an unseen entity starts a group, finish marking everything reachable from it before counting another group.