Number of Provinces
Reported by candidates from SambaNova Systems's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
SambaNova Systems reported this one in June 2022, and the detail that matters is that isConnected is an n x n matrix where the diagonal is always 1. It's Number of Provinces dressed up as friend circles. You count groups of people linked directly or through others. It's a connected components problem, and the OA wants the count, not the groups. If you've seen union-find or DFS, you're fine. If you blank, StealthCoder runs invisibly during the live OA and gives you a working solution as a safety net. Read the matrix as an adjacency matrix and you're most of the way there.
The problem
You are given an n x n matrix isConnected. If isConnected[i][j] = 1, person i and person j are direct friends. A friend circle is a group of directly or indirectly connected people with no friendship to anyone outside the group. Return the total number of friend circles. Function findCircleNum(isConnected: int[][]) → int Examples Example 1 isConnected = [[1,1,0],[1,1,0],[0,0,1]] return = 2 People 0 and 1 form one friend circle, while person 2 forms another. Example 2 isConnected = [[1,0,0],[0,1,0],[0,0,1]] return = 3 No two distinct people are friends, so every person is their own friend circle. Example 3 isConnected = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] return = 1 The direct friendships form one transitive chain containing all four people. Constraints 1 ≤ n ≤ 200 isConnected.length = n isConnected[i].length = n isConnected[i][j] is 0 or 1. isConnected[i][i] = 1 isConnected[i][j] = isConnected[j][i]
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is that this is a graph in disguise. Each person is a node, and isConnected[i][j] = 1 is an undirected edge. Count connected components. Two clean approaches work. First, DFS: keep a visited array, loop over each person, and if unvisited, increment the count and DFS through row i to mark everyone reachable. Second, union-find: start with n components, union each pair where the cell is 1, and decrement on every successful merge. Both run in O(n^2) time, which is fine for n up to 200. The common pitfall is treating it like a grid island problem and doing 4-direction flood fill on cells. Don't. You iterate over people, not cells. Another slip is forgetting the diagonal is 1, so skip i == j or let visited handle it. If you freeze on the live OA, StealthCoder is the hedge that hands you the DFS or union-find skeleton.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Number of Provinces 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. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
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 SambaNova Systems's OA.
SambaNova Systems reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Number of Provinces FAQ
How hard is Number of Provinces really?+
It's a medium on paper but easy once you see it's connected components. With n capped at 200, an O(n^2) DFS or union-find passes comfortably. The only real difficulty is recognizing the matrix as an adjacency matrix instead of a grid.
What's the trick for this SambaNova Systems question?+
Treat each person as a node and each 1 as an undirected edge. Count components. Loop through people, start a DFS from every unvisited one, and increment your counter each time you start. That count is the answer.
Should I use DFS or union-find?+
Either passes. DFS is shorter and harder to bug under pressure. Union-find is nice if you already have a template memorized. Pick whichever you can write without thinking, because speed and correctness matter more than elegance here.
What mistakes sink people on this problem?+
Flood-filling cells like an islands grid, forgetting a visited array and looping forever, and counting every pair of friends instead of components. Also don't iterate only the upper triangle in DFS and miss neighbors. Scan the full row for each person.
How do I prepare in 48 hours for a graph OA like this?+
Write DFS connected components and union-find from scratch twice each, no notes. Then do a couple of variants like number of islands and redundant connection. Know the complexity: O(n^2) for matrix input. That covers most graph questions an OA throws at you.