Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Number of Provinces

Number of Provinces explained: count connected components with Union-Find, path compression and union by rank. Tested Python code and a live DSU visual.

Also searched as: count connected components with union find · friend circles problem

🔗

Try it live Free

Union-Find (DSU)

Stream edges into the Union-Find lab and watch separate sets merge; the number of sets left at the end is the number of provinces.

Also useful: Graph Search: BFS vs DFS

Open the playground →

The problem

There are n cities. isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.

InputisConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output2

Cities 0 and 1 form one province; city 2 is alone.

The key insight

A province is a connected component. Union-Find answers it directly: start with every city as its own group (n groups), and for each connection union the two cities' groups. Every union that actually merges two different groups reduces the count by one.

Brute force first: Repeatedly merging lists of cities by scanning them for overlaps works but is O(n³) or worse; DFS or Union-Find is linear in the matrix size.

Step-by-step approach

  1. Create parent[i] = i for every city and set count = n.
  2. Write find(x) that follows parents to the root, compressing the path as it goes.
  3. For every pair i < j with isConnected[i][j] == 1, find both roots.
  4. If the roots differ, attach the smaller-rank root under the larger and decrement count.
  5. Return count.

Python solution

PYTHON 3tested
def find_circle_num(is_connected):
    n = len(is_connected)
    parent, rank = list(range(n)), [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path compression (halving)
            x = parent[x]
        return x

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                a, b = find(i), find(j)
                if a != b:
                    if rank[a] < rank[b]:
                        a, b = b, a
                    parent[b] = a              # union by rank
                    rank[a] += rank[a] == rank[b]
                    count -= 1
    return count

Complexity

TimeO(n²·α(n))
SpaceO(n)

Reading the n by n matrix dominates at O(n²). Each find is nearly constant thanks to path compression and union by rank (α is the inverse Ackermann function, at most 4 in practice).

Common mistakes

Frequently asked questions

What is the time and space complexity of Number of Provinces?

O(n²·α(n)) time because every cell of the matrix is read once and each union-find operation is nearly constant, and O(n) extra space for the parent and rank arrays.

Can I use DFS or BFS instead?

Yes. Loop over cities, and each time you find an unvisited one, start a DFS that visits its whole province and add one to the count. It is also O(n²) on the matrix.

Why use path compression and union by rank?

Together they keep the trees almost flat, so find runs in near-constant amortised time. Without them, a chain of unions can make find walk O(n) parents.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.