A city-pairing service counts provinces from an n × n connection matrix: 1 means two cities share a direct road. The intern nested a matrix walk from every city and never marked a city. A four-city fixture in staging hung: two mutually connected cities bounced forever. They added a local seen set but still restarted a full flood from every city. Staging returned in milliseconds. Two thousand cities in production were still flooding when the request timed out.

Number of Provinces asks how many connected components sit in an undirected city graph given as an adjacency matrix. This is not Number of Islands: that prompt is a raster of land and water with four neighbor deltas. Here the vertices are n named cities, and isConnected[i][j] == 1 is the edge. This is an interview writeup, not a layout lecture. The graphs post owns adjacency list versus matrix. The union-find post owns path compression and rank. DFS owns the walk. Here we only union each 1 and count leftover roots.

The problem

Given an n × n matrix isConnected where isConnected[i][j] == 1 means city i and city j are directly connected (and 0 means they are not), return how many provinces the matrix holds. A province is a maximal set of cities linked by any chain of direct roads. The matrix is symmetric; the diagonal is 1.

1 1 0
1 1 0
0 0 1     →  2

1 0 0
0 1 0
0 0 1     →  3

1 1 1
1 1 1
1 1 1     →  1

First matrix: cities 0 and 1 share a road; city 2 is alone. Second: three isolated cities. Third: one fully connected blob.

Note: There is no water and no off-board. City j is a neighbor of i exactly when the matrix cell is 1. Do not invent a 4-direction dirs table; that is the raster problem.

Restarting a flood from every city is the honest brute force

A matrix walk with no mark never returns. From city 0, step to city 1, step back, repeat. Staging’s hang was that bounce.

The honest version marks inside one flood so the walk terminates, throws the marks away, and starts again from the next city — a set of those city-sets collapses duplicates. Correct. Cubic in the city count: each flood scans n columns from each of n cities, and you restart that walk n times. Building an adjacency list of every 1 and then flooding once is also correct: you stored a neighbor list the matrix already is.

int findCircleNumRestart(int[][] isConnected) {
    int n = isConnected.length;
    Set<Set<Integer>> provinces = new HashSet<>();
    for (int i = 0; i < n; i++) {
        Set<Integer> cities = new HashSet<>();
        collect(isConnected, i, cities);
        provinces.add(cities);
    }
    return provinces.size();
}

void collect(int[][] isConnected, int city, Set<Integer> cities) {
    if (!cities.add(city)) {
        return;
    }
    for (int j = 0; j < isConnected.length; j++) {
        if (isConnected[city][j] == 1) {
            collect(isConnected, j, cities);
        }
    }
}

At n = 4 this is a rounding error. On one province of n cities you restart an n-city, n-column flood n times: you paid a full walk per city for a question that only needs one union per road.

Union each 1, then count roots

One parent array of length n. Each city starts as its own root; the province count starts at n. Scan the upper triangle. Every isConnected[i][j] == 1 is a union: if find(i) and find(j) differ, hang one root under the other and decrement. Same root is already one province — skip. Leftover roots are the answer. Flatten-on-find and rank live in the union-find post; do not re-lecture them at this board unless they ask.

1 1 0
1 1 0
0 0 1

parent  0 1 2     provinces 3
(0,1) 1   union 0 under 1    parent[0]=1   provinces 2
(0,2) 0   skip
(1,2) 0   skip
leftover roots: 1, 2         →  2

No neighbor list. The Java is that scan; union returns whether a merge happened so the count can drop.

int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    int provinces = n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1 && union(parent, i, j)) {
                provinces--;
            }
        }
    }
    return provinces;
}

int find(int[] parent, int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

boolean union(int[] parent, int a, int b) {
    int ra = find(parent, a);
    int rb = find(parent, b);
    if (ra == rb) {
        return false;
    }
    parent[ra] = rb;
    return true;
}

Time is O(n² α(n)) — every upper-triangle cell is read once, and each union is nearly constant. Space is O(n) for parent (and the find call stack). A persistent-seen DFS on the matrix is the same O(n²) read with O(n) extra boolean[]; it is the islands sibling, not a second graph.

Note: The matrix is the edge list. Copying every 1 into List<Integer>[] adj is extra storage, not extra insight. Scan j > i so each undirected road is unioned once; unioning both triangles is still correct, just twice the work.

What interviewers usually poke next

  • DFS / BFS on the matrix. A boolean[] seen of length n. Every unseen city is a new province: increment, then flood that row. Same “count starts” idea as Number of Islands, on cities instead of cells. Iterative flood uses an ArrayDeque, not java.util.Stack, not ArrayList.remove(0).
  • Accounts Merge. Union emails that share an account, then emit the leftover groups. Same leftover components; the keys are strings, so map them onto 0 … n-1 first.
  • Redundant Connection. Union until find(a) == find(b); that edge would close a cycle. Same structure, different question.
  • Rank, or a read-only find. The union-find post owns those tweaks. Name them; do not derive them here unless they ask.
  • n = 1, or a fully connected matrix. One city is one province. An all-1s matrix collapses to one root.

You are done with this problem when you can say, out loud, why an unmarked matrix walk never returns, why restarting a flood from every city is cubic, and why leftover roots after unioning each 1 are the province count.