Count Connected Friend Groups
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Count Connected Friend Groups
You are given an `n x n` symmetric adjacency matrix. `is_connected[i][j] == 1` means person `i` and person `j` are directly connected. Connectivity is transitive: people belong to the same friend group if a path of direct connections joins them.
Return the number of connected friend groups.
## Function Contract
```python
def count_friend_groups(is_connected: list[list[int]]) -> int:
...
```
## Constraints
- `1 <= n <= 200`
- `len(is_connected) == n`, and every row has length `n`.
- Each entry is `0` or `1`.
- `is_connected[i][i] == 1` for every `i`.
- `is_connected[i][j] == is_connected[j][i]`.
- Do not mutate the input.
## Example
```text
is_connected = [
[1, 1, 0, 0],
[1, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 1, 1],
]
result = 2
```
Quick Answer: Count connected friend groups from a symmetric adjacency matrix where indirect connections place people in the same group. Work within a 200-person limit, preserve the input, and correctly handle isolated people and multiple disconnected components.
Implement count_friend_groups(is_connected). The input is a symmetric n by n zero-one adjacency matrix with ones on its diagonal. People are in the same group when a path of direct connections joins them. Return the number of connected components without mutating the matrix.
Constraints
- 1 <= n <= 200
- The matrix is n by n, symmetric, contains only 0 and 1, and has a one on every diagonal entry.
- Do not mutate the input matrix.
Examples
Input: ([[1]],)
Expected Output: 1
Explanation: One person forms one group.
Input: ([[1, 0], [0, 1]],)
Expected Output: 2
Explanation: Two isolated people form two groups.
Hints
- Treat matrix indices as graph vertices.
- Each traversal started from an unseen person discovers exactly one connected component.