Skip to main content

21. Number of Provinces

mediumAsked at Nubank

Count connected components in an adjacency-matrix graph; Nubank uses this as a clean Union-Find prompt that maps to clustering linked accounts during fraud-ring detection.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n cities, some directly connected. isConnected is an n x n matrix where isConnected[i][j] = 1 if city i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Constraints

  • 1 <= n <= 200
  • isConnected[i][j] is 0 or 1
  • isConnected[i][i] == 1, isConnected[i][j] == isConnected[j][i]

Examples

Example 1

Input
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output
2

Example 2

Input
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output
3

Approaches

1. DFS over visited[]

For each unvisited node, DFS through its row and mark every reachable node visited; each launch is one province.

Time
O(n^2)
Space
O(n)
function findCircleNum(M){ const n=M.length,v=Array(n).fill(false); let c=0; const dfs=i=>{ v[i]=true; for(let j=0;j<n;j++) if(M[i][j]&&!v[j]) dfs(j); }; for(let i=0;i<n;i++) if(!v[i]){c++; dfs(i);} return c; }

Tradeoff:

2. Union-Find

Union connected pairs, count distinct roots. Slightly bigger constants than DFS here but generalizes to streaming edges where DFS would re-walk.

Time
O(n^2 * alpha)
Space
O(n)
function findCircleNum(M) {
  const n = M.length;
  const p = Array.from({ length: n }, (_, i) => i);
  const find = x => p[x] === x ? x : (p[x] = find(p[x]));
  const union = (a, b) => { p[find(a)] = find(b); };
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      if (M[i][j]) union(i, j);
  const roots = new Set();
  for (let i = 0; i < n; i++) roots.add(find(i));
  return roots.size;
}

Tradeoff:

Nubank-specific tips

Nubank engineers will quietly ask which data structure scales to streaming edge updates — Union-Find is the right answer for a fraud-graph being built incrementally.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Number of Provinces and other Nubank interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →