#106

Number of Provinces

medium

graphunion-finddepth-first-searchbreadth-first-searchmatrix

You are given an n x n adjacency matrix isConnected describing direct connections between n cities. isConnected[i][j] === 1 means city i and city j are directly connected, and isConnected[i][j] === 0 means they are not.

A province is a group of cities that are connected either directly or indirectly (through other cities), where no city outside the group is connected to any city inside it — in graph terms, a connected component.

Return the total number of provinces.

The matrix is symmetric (isConnected[i][j] === isConnected[j][i]) and every city is connected to itself (isConnected[i][i] === 1).

Example

Input: isConnected =

110

001

Output: 2

Cities 0 and 1 are directly connected, forming one province. City 2 is isolated, forming a second.

Constraints

1 <= n <= 200
n === isConnected.length === isConnected[i].length
isConnected[i][j] is 0 or 1
isConnected[i][i] === 1
isConnected[i][j] === isConnected[j][i]

Intuition

A province is a maximal group of mutually-connected cities — a connected component of the friendship graph, given here as an adjacency matrix. The straightforward read is to count components by traversal: but it's worth seeing the problem through the lens of merging, which is what the stored Union-Find solution does.

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  const dfs = (city) => {
    visited[city] = true;
    // Follow every direct connection out of this city.
    for (let next = 0; next < n; next++)
      if (isConnected[city][next] === 1 && !visited[next]) dfs(next);
  };
  let provinces = 0;
  for (let city = 0; city < n; city++) {
    // Each unvisited city begins a brand-new province.
    if (!visited[city]) { provinces++; dfs(city); }
  }
  return provinces;
}

A clean DFS baseline — count the launches of a component flood. O(n²), the matrix size.

The DFS is already O(n²) and perfectly good. But the canonical tool for "how many groups, given a stream of pairwise connections" is Union-Find, and it's the model the stored solution teaches.

The key observation: start with every city in its own singleton set, then for each edge isConnected[i][j], union the two endpoints. Two cities end up in the same set exactly when they're connected directly or transitively — so the number of provinces is the number of distinct roots left at the end. Path compression plus union-by-rank makes each operation effectively constant.

Union-Find tracks an evolving forest, not a sequence or a grid, so there's no lane to animate; the static graph below shows the three components the unions discover. (The matrix [[1,1,0],[1,1,1],[0,1,1]] from the example is one province; here is a clearer three-province instance for the picture.)

Cities {0,1,2} are pairwise reachable, {3,4} form a second group, and 5 stands alone. Union 0–1 and 1–2 collapse the first trio to a single root; union 3–4 collapses the pair; 5 is never unioned. Three roots remain → three provinces.

Only scan `j > i`. The matrix is symmetric and every city connects to itself (isConnected[i][i] = 1); unioning the upper triangle covers every real edge without redundant work or spurious self-unions.
Count roots, not unions. The province count is the number of indices that are their own parent after all unions — equivalently n minus the number of successful (non-redundant) unions.

Optimization

DFS over the adjacency matrix

Treat the matrix as a graph and count connected components. Keep a visited set; for each unvisited city, start a depth-first search that follows every isConnected[city][next] === 1 edge, marking each reached city visited. Each DFS launch is one new province.

O(n²) time (every matrix cell is inspected once) and O(n) space for the visited array and recursion stack.

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);

  const dfs = (city) => {
    visited[city] = true;
    for (let next = 0; next < n; next++) {
      if (isConnected[city][next] === 1 && !visited[next]) dfs(next);
    }
  };

  let provinces = 0;
  for (let city = 0; city < n; city++) {
    if (!visited[city]) {
      provinces++;
      dfs(city);
    }
  }
  return provinces;
}

Union-Find (disjoint set)

Start with n singleton sets and union the endpoints of every edge isConnected[i][j] === 1 (j > i suffices by symmetry). The number of provinces is the number of roots left — count the indices that are their own parent.

Path compression plus union by rank makes each operation near-constant (inverse Ackermann), so it's effectively O(n²) time, O(n) space.

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);

  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };

  const union = (a, b) => {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
  };

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) union(i, j);
    }
  }

  let provinces = 0;
  for (let i = 0; i < n; i++) {
    if (find(i) === i) provinces++;
  }
  return provinces;
}

Complexity analysis

Time complexity: O(n²). Here's why:

Scanning the upper triangle of the n × n matrix to find edges is O(n²).
Each union/find is effectively constant (inverse-Ackermann) with path compression and union by rank.

The matrix scan dominates, so the overall time is O(n²) — unavoidable given the adjacency-matrix input.

Space complexity: O(n). Here's why:

The parent and rank arrays are one entry per city, O(n).

No copy of the matrix is made, so the auxiliary space is O(n) (the DFS alternative uses an O(n) visited array plus recursion stack instead).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
isConnected = 110 110 001	2	Cities 0–1 form a province; city 2 is isolated — two in all.
isConnected = 110 111 011	1	0–1 and 1–2 are connected, so 0 and 2 join indirectly through 1 — one province.
isConnected = 111 111 111	1	Every city connected to every other — a single province.
isConnected = 1001 0110 0110 1001	2	Non-adjacent indices connected: {0,3} and {1,2} — two provinces.
isConnected = 10100 01000 10110 00110 00001	3	Components {0,2,3}, {1}, {4} — a chain of connections plus two loners.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor