Skip to main content

547. Number of Provinces

mediumAsked at GoDaddy

Count connected components in an adjacency-matrix graph — GoDaddy maps this to identifying isolated hosting-cluster groups where servers are directly or transitively connected through shared VPC peering relationships.

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

Problem

There are n cities. Some of them are connected, directly or indirectly. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if city i and city 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
  • n == isConnected.length == isConnected[i].length
  • isConnected[i][j] is 1 or 0
  • 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 adjacency matrix

Mark each visited city; DFS into all connected unvisited neighbors; each unvisited starting city is a new province.

Time
O(n^2)
Space
O(n)
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;
  function dfs(i) {
    visited[i] = true;
    for (let j = 0; j < n; j++) {
      if (isConnected[i][j] === 1 && !visited[j]) dfs(j);
    }
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      provinces++;
      dfs(i);
    }
  }
  return provinces;
}

Tradeoff:

2. Union-Find

Path-compressed Union-Find; union all directly connected city pairs; count distinct roots to get province count.

Time
O(n^2 * alpha(n))
Space
O(n)
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }
  function union(x, y) {
    const px = find(x);
    const py = find(y);
    if (px === py) return;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
  }
  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;
}

Tradeoff:

GoDaddy-specific tips

GoDaddy values the Union-Find approach here because their hosting infrastructure team uses it for fast dynamic connectivity queries as servers are added or removed from clusters. Explain path compression and union-by-rank — they look for candidates who know both DFS and UF and can pick the right one for online vs offline queries.

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 GoDaddy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →