Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Number of Provinces
• Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Problem gist

There are n cities, and isConnected[i][j] tells whether city i is directly connected to city j. A province is a full connected component: if city 0 is connected to city 1, and city 1 is connected to city 2, then all three cities belong to the same province even if 0 and 2 are not directly connected.

The task is to count how many separate connected groups exist in the matrix.

The matrix is really an undirected graph in adjacency-matrix form. Each city is a node. Each 1 away from the diagonal is an edge. The answer is the number of connected components.

Core idea

The direct way to solve the problem is graph traversal: start at an unvisited city, mark everything reachable from it, and count that as one province. That works well and is easy to explain.

Union-Find gives the same result from a different angle. Instead of starting a traversal from each component, it begins with every city in its own province. Whenever the matrix says two cities are connected, merge their two sets. At the end, the number of remaining sets is the number of provinces.

This is a good fit because “being in the same province” is transitive:

• If A is connected to B, they must be in one group.
• If B is connected to C, that same group must also contain C.
• Union-Find is built exactly for maintaining these merge operations efficiently.

Deriving the algorithm

Start with n isolated cities, so the province count is n.

Scan the upper triangle of the matrix. The matrix is symmetric, so checking both isConnected[i][j] and isConnected[j][i] would repeat the same edge. The diagonal is also unhelpful because every city is connected to itself.

For every pair (city_a, city_b) where isConnected[city_a][city_b] == 1, union their sets:

1. Find the representative parent of city_a.
2. Find the representative parent of city_b.
3. If the representatives differ, attach one set to the other and decrement the component count.
4. If they already match, the cities were already connected through earlier edges, so the province count does not change.

Path compression keeps each find call cheap by making visited nodes point directly to their root. Union by size keeps the trees shallow by attaching the smaller group under the larger group.

Python solution

from typing import List


class DisjointSetUnion:
    def __init__(self, size: int) -> None:
        self._parent = list(range(size))
        self._component_size = [1] * size
        self.component_count = size

    def find(self, city: int) -> int:
        """Return the representative city for this connected component."""
        if self._parent[city] != city:
            self._parent[city] = self.find(self._parent[city])
        return self._parent[city]

    def union(self, first_city: int, second_city: int) -> bool:
        """Merge two components. Return True only when a merge happened."""
        first_root = self.find(first_city)
        second_root = self.find(second_city)

        if first_root == second_root:
            return False

        if self._component_size[first_root] < self._component_size[second_root]:
            first_root, second_root = second_root, first_root

        self._parent[second_root] = first_root
        self._component_size[first_root] += self._component_size[second_root]
        self.component_count -= 1
        return True


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        city_count = len(isConnected)
        provinces = DisjointSetUnion(city_count)

        for city_a in range(city_count):
            # The matrix is symmetric, so only inspect each city pair once.
            for city_b in range(city_a + 1, city_count):
                if isConnected[city_a][city_b] == 1:
                    provinces.union(city_a, city_b)

        return provinces.component_count

Complexity

The algorithm inspects the upper triangle of an n x n matrix, so it performs O(n^2) connection checks.

Each Union-Find operation is almost constant time with path compression and union by size. More formally, the total cost is O(n^2 * alpha(n)), where alpha is the inverse Ackermann function and is effectively constant for interview-sized inputs.

The extra space is O(n) for the parent and component-size arrays.

Interview follow-ups

Could this be solved with DFS or BFS instead?

Yes. Treat the matrix as an adjacency matrix and run a traversal from every unvisited city. Each traversal marks one whole province, so increment the answer when starting from a new unvisited city.

This works because a province is exactly a connected component. DFS or BFS explores all cities reachable from the starting city, including indirect connections. After that traversal finishes, any remaining unvisited city must belong to a different province.

The complexity is still O(n^2), because checking a city’s neighbors in an adjacency matrix costs O(n), and this happens across up to n cities. The space is O(n) for the visited set and recursion stack or queue. DFS/BFS is usually the simplest explanation; Union-Find becomes more attractive when the interviewer asks about repeated merges or dynamic connections.

What if the input were an edge list instead of an adjacency matrix?

Union-Find becomes even more natural. Initialize one component per city, then union every edge (u, v) from the list. The final component count is still the answer.

For n cities and m edges, this runs in O(m * alpha(n)) time and O(n) space. That is better than building or scanning an n x n matrix when the graph is sparse. DFS/BFS would also work with an adjacency list in O(n + m) time, but Union-Find keeps the code compact when the only required output is the component count.

How would the solution change if connections arrived one at a time?

Keep the same Union-Find object alive across updates. Each new direct connection calls union(a, b). If the union merges two previously separate sets, the province count decreases by one; if the cities were already connected, the count stays the same.

This gives near-constant amortized update time and O(1) query time for “how many provinces exist now?” The tradeoff is that this handles added connections cleanly but not deleted connections. Removing an edge can split a component, and standard Union-Find cannot undo merges without extra machinery.

How would you return the actual groups instead of just the count?

After all unions are complete, run find(city) for every city and group cities by their representative root in a hash map. The map values are the province member lists.

Path compression matters here too. Calling find during the grouping pass normalizes each city to its final representative, so cities in the same connected component land in the same bucket. The extra grouping pass costs O(n * alpha(n)) time and O(n) additional space for the output structure.

Why is it safe to scan only half of the matrix?

The problem’s matrix represents an undirected graph, so isConnected[i][j] and isConnected[j][i] describe the same relationship. The diagonal isConnected[i][i] only says each city is connected to itself, which never changes the component count.

Scanning only pairs where j > i still sees every real city pair exactly once. It does not change the answer, but it avoids duplicate union attempts and makes the intent clearer.