Connected Groups
Reported by candidates from Fivetran's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
This Fivetran OA, reported in June 2024, looks like a matrix problem but it's really a graph problem in disguise. The matrix is an adjacency matrix, and you're counting connected components. If you've seen Number of Provinces, you've seen this. If you haven't, the whole thing reduces to one idea: walk from each unvisited person and mark everyone reachable. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but the pattern is short enough to carry in your head.
The problem
You are given a square binary matrix related. Each row and column represents one person at the same party. related[i][j] == 1 means that person i and person j have a direct connection. related[i][j] == 0 means that they do not have a direct connection. Connections are transitive. If person a is connected to person b, and person b is connected to person c, then all three people belong to the same group. Return the number of distinct groups. If related is empty, return 0. Function countConnectedGroups(related: int[][]) → int Examples Example 1 related = [[1,1,0],[1,1,1],[0,1,1]] return = 1 Person 0 is directly connected to person 1, and person 1 is directly connected to person 2. Transitivity places all three people in one group. Example 2 related = [[1,0,0],[0,1,1],[0,1,1]] return = 2 Person 0 forms one group. Persons 1 and 2 form the other group. Example 3 related = [[1,0,1,0],[0,1,0,1],[1,0,1,0],[0,1,0,1]] return = 2 Persons 0 and 2 form one group, while persons 1 and 3 form the other. Group members do not need consecutive indices. Constraints Let n = related.length. 0 <= n <= 1000. related has exactly n rows, and every row has exactly n entries. Every entry in related is either 0 or 1. related[i][i] == 1 for every valid index i. related[i][j] == related[j][i] for all valid indices i and j.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: treat each row as a node's neighbor list. Keep a visited array of size n. Loop i from 0 to n-1. If i is unvisited, increment the group count and run DFS or BFS from i, visiting every j where related[i][j] == 1. Union-Find works too, and the answer is the number of roots left. Complexity is O(n^2) since you scan the full matrix once, which is fine for n up to 1000. Pitfalls: handle the empty matrix and return 0, don't count the diagonal as a separate group, and watch recursion depth. With n at 1000 a recursive DFS can chain deep, so an iterative stack or BFS is safer. Example 3 shows groups don't need consecutive indices, so don't scan neighbors only by adjacent position. If you freeze in the live OA, StealthCoder can hand you the working traversal while you keep your head clear.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Connected Groups cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as number of provinces. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Fivetran's OA.
Fivetran reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Connected Groups FAQ
What's the trick in the Fivetran Connected Groups problem?+
It's counting connected components in an undirected graph given as an adjacency matrix. Loop over every person, and when you hit an unvisited one, bump the counter and flood-fill everyone reachable. The count of flood-fills is your answer.
Should I use DFS, BFS, or Union-Find?+
Any works. DFS and BFS are the quickest to write and need a visited array. Union-Find is clean if you're comfortable with it. With n up to 1000, prefer BFS or an iterative DFS to avoid a deep recursion stack.
What's the time complexity I should aim for?+
O(n^2) time and O(n) extra space. You must read the matrix to find connections, and each row is scanned once per visited node. Anything slower than that, like repeated full rescans per component, is a red flag.
What edge cases does this problem hide?+
The empty matrix must return 0. A single person returns 1. A matrix of only the diagonal gives n groups. Also, group members can be non-adjacent indices, like persons 0 and 2 in Example 3, so check every column in a row.
How do I prepare for this in 48 hours?+
Write Number of Provinces from scratch twice, once with DFS and once with Union-Find. Then run the three examples by hand. Spend the rest of your time on other graph basics like grid islands, since the same component-counting idea shows up in many OAs.