Number of Provinces LeetCode: DFS & Union-Find Guide

If you have solved Number of Islands, you already understand the core idea behind Number of Provinces. Both problems ask you to count connected components. The difference is the data structure: Islands uses a 2D grid of land and water, while number of provinces leetcode (#547) hands you an adjacency matrix that represents direct connections between cities.

This distinction matters because it changes how you traverse. Instead of checking four directional neighbors on a grid, you scan a row of the matrix to find which cities are connected to the current one. The algorithms — DFS and Union-Find — stay the same, but the way you feed data into them is different.

In this walkthrough, we will break down the problem, walk through both approaches with a concrete example, and cover the edge cases interviewers like to probe.

You are given an n x n matrix called isConnected where 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 to each other directly or indirectly. Your task is to return the total number of provinces.

The matrix is symmetric — if city 0 is connected to city 2, then city 2 is also connected to city 0. The diagonal is always 1 because every city is connected to itself. This is a classic adjacency matrix representation of an undirected graph.

The problem was originally called "Friend Circles" on LeetCode before being renamed. The mental model is the same: each person is a node, friendships are edges, and you count how many separate friend groups exist. Whether you think of it as cities or friends, you are counting connected components in an undirected graph.

The DFS approach is the most intuitive way to solve the number of provinces leetcode problem. You maintain a visited array of size n. For each city that has not been visited, you start a DFS, mark all reachable cities as visited, and increment your province count by one.

Inside the DFS, you look at the current city's row in the adjacency matrix. For every column j where isConnected[city][j] == 1 and j has not been visited, you recurse into j. This effectively explores the entire connected component starting from the initial city.

The time complexity is O(n^2) because in the worst case you examine every cell of the n x n matrix. Space complexity is O(n) for the visited array and the recursion stack. This is identical to running DFS on a graph with n nodes and up to n^2 edges.

Union-Find is the other classic approach for connected components and works particularly well when you need to merge groups incrementally. You initialize n disjoint sets — one for each city. Then you scan the upper triangle of the matrix (since it is symmetric) and union any pair (i, j) where isConnected[i][j] == 1.

After processing all pairs, count the number of distinct roots. Each unique root represents one province. With path compression and union by rank, the find operation runs in nearly O(1) amortized time, giving an overall complexity of O(n^2 * alpha(n)) which is effectively O(n^2).

Union-Find shines when the problem has follow-up operations like dynamically adding or removing connections. For this static problem, both DFS and Union-Find perform equally well, but interviewers often ask for both to test your breadth.

Let us trace through the classic example. We have three cities (0, 1, 2) with isConnected = [[1,1,0],[1,1,0],[0,0,1]]. City 0 is connected to city 1 (isConnected[0][1] = 1), but neither is connected to city 2.

With DFS: Start at city 0 (unvisited). DFS visits city 0, then finds isConnected[0][1] = 1 so it visits city 1. From city 1, isConnected[1][0] = 1 but city 0 is already visited, and isConnected[1][2] = 0. DFS returns. Province count = 1. Move to city 1 — already visited. Move to city 2 — unvisited. DFS visits city 2, finds no unvisited connections. Province count = 2. Final answer: 2 provinces.

With Union-Find: Initialize parent = [0, 1, 2]. Check isConnected[0][1] = 1, union(0, 1) so parent becomes [0, 0, 2]. Check isConnected[0][2] = 0, skip. Check isConnected[1][2] = 0, skip. Count roots: find(0) = 0, find(1) = 0, find(2) = 2. Two distinct roots (0 and 2), so two provinces.

The edge cases for this problem are straightforward but worth mentioning because interviewers sometimes start with them. If every cell in the matrix is 1 (except it already is by symmetry), all cities are in one province — the answer is 1. If the matrix is the identity matrix (only the diagonal is 1), no cities are connected to each other, so the answer is n.

Self-loops (the diagonal) do not affect the algorithm because a city being connected to itself does not create a new province or merge separate ones. Your DFS or Union-Find naturally handles this — visiting a city and finding it is connected to itself just means you stay in the same component.

Both approaches run in O(n^2) time and O(n) extra space. The matrix itself is n^2, and you read every cell at most once (DFS) or once per upper-triangle pair (Union-Find). In interviews, mention that Union-Find has a slight constant-factor overhead but offers more flexibility for dynamic graph problems.

Number of provinces explained in one sentence: it is connected components on a graph given as an adjacency matrix instead of a grid. That single difference from Number of Islands tests whether you can adapt your traversal to a different input format, which is exactly the kind of flexibility interviewers look for.

This problem also serves as a gateway to harder graph problems. Once you are comfortable counting components with both DFS and Union-Find, you are ready for problems like Redundant Connection (finding the extra edge in a graph), Accounts Merge (Union-Find on strings), and Graph Valid Tree (checking connectivity plus cycle detection).

If you want to build long-term recall for these patterns, practice with YeetCode flashcards. Spaced repetition helps you internalize the DFS-on-adjacency-matrix template and the Union-Find boilerplate so that when a connected components problem appears in an interview, the approach comes to you automatically.