547. Number of Provinces Solution & Explanation

Q: Is Number of Provinces easy or hard?

Number of Provinces is categorized as a Medium problem on LeetCode. The core idea—counting connected components in a graph—is straightforward once you recognize the adjacency matrix representation, but it requires familiarity with DFS, BFS, or Union-Find.

Q: How to solve Number of Provinces in O(n^2)?

Iterate through each city and run a DFS or BFS if it has not been visited. During traversal, mark all directly or indirectly connected cities as visited. Each traversal corresponds to one connected component, so increment the province count after each new traversal.

Q: What is the best approach for Number of Provinces?

Depth-First Search is the most common approach. Treat each city as a node and run DFS whenever you encounter an unvisited city to mark all connected cities. Each DFS traversal represents one province. The overall time complexity is O(n^2) because the adjacency matrix requires scanning all neighbors.

Q: What data structure is used in Number of Provinces?

The problem uses a graph represented as an adjacency matrix. Solutions typically rely on DFS or BFS traversal with a visited array, or the Union-Find (Disjoint Set) data structure to merge and track connected components.

Q: What is the time complexity of Number of Provinces?

The standard DFS or BFS solution runs in O(n^2) time because the algorithm scans every entry of the n x n adjacency matrix. Union-Find also requires iterating through the matrix, resulting in O(n^2 · α(n)) time where α(n) is the inverse Ackermann function.

Q: Number of Provinces Python or Java solution approach?

Both Python and Java implementations typically use DFS or Union-Find. The DFS version recursively visits neighbors using the adjacency matrix and tracks visited cities, achieving O(n^2) time and O(n) space complexity.

Q: Is Number of Provinces asked at Google, Amazon, or Meta?

Number of Provinces is a common graph connectivity problem frequently asked in technical interviews. Variants of this problem have appeared at companies like Amazon, Google, Meta, and Microsoft because it tests understanding of graphs, traversal algorithms, and connected components.

The problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

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

Constraints:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Approach overview

Problem Overview: You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. The task is to count how many such provinces exist.

Approach 1: Depth-First Search (DFS) (Time: O(n²), Space: O(n))

Treat the matrix as a graph where each city is a node and isConnected[i][j] = 1 represents an undirected edge. Iterate through every city. When you encounter a city that hasn’t been visited, start a DFS traversal and mark all reachable cities as visited. That traversal covers exactly one connected component, which corresponds to a province. Since the adjacency matrix requires scanning all n neighbors for each node, the traversal costs O(n²). This approach directly applies classic Depth-First Search on a graph and is usually the most intuitive way to reason about connected components.

Approach 2: Union-Find (Disjoint Set) (Time: O(n² · α(n)), Space: O(n))

Union-Find models each city as part of a disjoint set. Initially every city is its own parent. Scan the adjacency matrix and whenever isConnected[i][j] = 1, perform a union operation to merge the sets containing i and j. Path compression and union-by-rank keep operations nearly constant time, giving an amortized O(α(n)) cost per union. After processing the matrix, the number of unique roots represents the number of provinces. This approach works well when you repeatedly merge components or when connectivity queries appear in larger systems using Union Find.

Recommended for interviews: DFS (or BFS) is the most expected explanation because the problem maps directly to counting connected components in a graph. Interviewers want to see that you recognize the adjacency matrix as a graph representation and run a traversal to mark visited nodes. Union-Find is equally valid and demonstrates deeper familiarity with graph connectivity techniques. Start with DFS to show clear reasoning, then mention Union-Find as an alternative optimization pattern.

Approach 1: Approach 1: Depth-First Search (DFS)

This approach uses Depth-First Search (DFS) to count the number of provinces. The core idea is to treat the connected cities as a graph and perform a DFS traversal starting from each city. During traversal, mark all reachable cities from the starting city. Each starting city for a DFS that visits new cities indicates the discovery of a new province.

Python

def findCircleNum(isConnected: List[List[int]]) -> int:
    def dfs(node):
        visited.add(node)
        for i in range(len(isConnected)):
            if isConnected[node][i] == 1 and i not in visited:
                dfs(i)
    
    n = len(isConnected)
    visited = set()
    provinces = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            provinces += 1
    return provinces

Java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        return provinces;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int node) {
        visited[node] = true;
        for (int i = 0; i < isConnected.length; i++) {
            if (isConnected[node][i] == 1 && !visited[i]) {
                dfs(isConnected, visited, i);
            }
        }
    }
}

C++

#include <vector>

void dfs(int node, std::vector<std::vector<int>>& isConnected, std::vector<bool>& visited) {
    visited[node] = true;
    for (int i = 0; i < isConnected.size(); i++) {
        if (isConnected[node][i] == 1 && !visited[i]) {
            dfs(i, isConnected, visited);
        }
    }
}

int findCircleNum(std::vector<std::vector<int>>& isConnected) {
    int n = isConnected.size();
    std::vector<bool> visited(n, false);
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, isConnected, visited);
            provinces++;
        }
    }
    return provinces;
}

JavaScript

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);
    let provinces = 0;

    const dfs = (node) => {
        visited[node] = true;
        for (let i = 0; i < n; i++) {
            if (isConnected[node][i] === 1 && !visited[i]) {
                dfs(i);
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            provinces++;
        }
    }
    return provinces;
};

#include <stdbool.h>

void dfs(int n, int node, int isConnected[n][n], bool visited[n]) {
    visited[node] = true;
    for (int i = 0; i < n; i++) {
        if (isConnected[node][i] == 1 && !visited[i]) {
            dfs(n, i, isConnected, visited);
        }
    }
}

int findCircleNum(int isConnected[200][200], int n) {
    bool visited[n];
    for (int i = 0; i < n; i++) visited[i] = false;
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(n, i, isConnected, visited);
            provinces++;
        }
    }
    return provinces;
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        bool[] visited = new bool[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Dfs(isConnected, visited, i);
                provinces++;
            }
        }
        return provinces;
    }

    private void Dfs(int[][] isConnected, bool[] visited, int node) {
        visited[node] = true;
        for (int i = 0; i < isConnected.Length; i++) {
            if (isConnected[node][i] == 1 && !visited[i]) {
                Dfs(isConnected, visited, i);
            }
        }
    }
}

The Python solution also leverages DFS. A set is used to keep track of visited nodes (cities). For each city, if it is not in the visited set, a DFS is triggered marking all reachable cities along with counting a new province.

Complexity

Time Complexity: O(n^2) since we may check every pair of cities.
Space Complexity: O(n) for the visited set.

Try this approach in the editor

Approach 2: Approach 2: Union-Find

This approach employs the Union-Find (Disjoint Set Union) algorithm to find the number of provinces. This algorithm efficiently handles dynamic connectivity queries. By iteratively checking connections and performing unions, we can identify distinct connected components (provinces).

Python

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1


def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                uf.union(i, j)

    provinces = sum(1 for i in range(n) if uf.find(i) == i)
    return provinces

Java

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

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

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }
}

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == i) {
                provinces++;
            }
        }
        return provinces;
    }
}

C++

#include <vector>

class UnionFind {
public:
    std::vector<int> parent, rank;
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int findCircleNum(std::vector<std::vector<int>>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.unionSet(i, j);
            }
        }
    }
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (uf.find(i) == i) provinces++;
    }
    return provinces;
}

JavaScript

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, idx) => idx);
        this.rank = new Array(size).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
        }
    }
}

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const uf = new UnionFind(n);
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] === 1) {
                uf.union(i, j);
            }
        }
    }

    let provinces = 0;
    for (let i = 0; i < n; i++) {
        if (uf.find(i) === i) provinces++;
    }
    return provinces;
};

#include <stdbool.h>

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

void unionSet(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int findCircleNum(int isConnected[200][200], int n) {
    int parent[n];
    int rank[n];

    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                unionSet(parent, rank, i, j);
            }
        }
    }
    
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (find(parent, i) == i) {
            provinces++;
        }
    }
    return provinces;
}

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.Union(i, j);
                }
            }
        }

        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (uf.Find(i) == i) {
                provinces++;
            }
        }
        return provinces;
    }
}

The Union-Find pattern in Python involves creating groups and minimizing tree depth by union by rank. The final province count is derived by checking how many root nodes exist within the parent array.

Complexity

Time Complexity: O(n^2 * α(n)), largely optimal due to path compression.
Space Complexity: O(n) for the union-find's internal data structures.

Try this approach in the editor

Approach 3: DFS

We create an array vis to record whether each city has been visited.

Next, we traverse each city i. If the city has not been visited, we start a depth-first search from that city. Using the matrix isConnected, we find the cities directly connected to this city. These cities and the current city belong to the same province. We continue the depth-first search for these cities until all cities in the same province have been visited. This counts as one province, so we increment the answer ans by 1. Then, we move to the next unvisited city and repeat the process until all cities have been traversed.

Finally, return the answer.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the number of cities.

TypeScript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const vis: boolean[] = new Array(n).fill(false);
    const dfs = (i: number) => {
        vis[i] = true;
        for (let j = 0; j < n; ++j) {
            if (!vis[j] && isConnected[i][j]) {
                dfs(j);
            }
        }
    };
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (!vis[i]) {
            dfs(i);
            ++ans;
        }
    }
    return ans;
}

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		vis[i] = true
		for j, x := range isConnected[i] {
			if !vis[j] && x == 1 {
				dfs(j)
			}
		}
	}
	for i, v := range vis {
		if !v {
			ans++
			dfs(i)
		}
	}
	return
}

Rust

impl Solution {
    fn dfs(is_connected: &mut Vec<Vec<i32>>, vis: &mut Vec<bool>, i: usize) {
        vis[i] = true;
        for j in 0..is_connected.len() {
            if vis[j] || is_connected[i][j] == 0 {
                continue;
            }
            Self::dfs(is_connected, vis, j);
        }
    }

    pub fn find_circle_num(mut is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut vis = vec![false; n];
        let mut res = 0;
        for i in 0..n {
            if vis[i] {
                continue;
            }
            res += 1;
            Self::dfs(&mut is_connected, &mut vis, i);
        }
        res
    }
}

Try this approach in the editor

Approach 4: Union-Find

We can also use the union-find data structure to maintain each connected component. Initially, each city belongs to a different connected component, so the number of provinces is n.

Next, we traverse the matrix isConnected. If there is a connection between two cities (i, j) and they belong to two different connected components, they will be merged into one connected component, and the number of provinces is decremented by 1.

Finally, return the number of provinces.

The time complexity is O(n^2 times log n), and the space complexity is O(n). Here, n is the number of cities, and log n is the time complexity of path compression in the union-find data structure.

TypeScript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const p: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        if (p[x] !== x) {
            p[x] = find(p[x]);
        }
        return p[x];
    };
    let ans = n;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if (isConnected[i][j]) {
                const pa = find(i);
                const pb = find(j);
                if (pa !== pb) {
                    p[pa] = pb;
                    --ans;
                }
            }
        }
    }
    return ans;
}

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	ans = n
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if isConnected[i][j] == 1 {
				pa, pb := find(i), find(j)
				if pa != pb {
					p[pa] = pb
					ans--
				}
			}
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Depth-First Search (DFS)	Time Complexity: O(n^2) since we may check every pair of cities. Space Complexity: O(n) for the visited set.
Approach 2: Union-Find	Time Complexity: O(n^2 * α(n)), largely optimal due to path compression. Space Complexity: O(n) for the union-find's internal data structures.
DFS	–
Union-Find	–

Complexity analysis

Approach	Time	Space	When to Use
Depth-First Search (DFS)	O(n^2)	O(n)	Best general solution when treating the matrix as a graph and counting connected components.
Union-Find (Disjoint Set)	O(n^2 · α(n))	O(n)	Useful when repeatedly merging components or solving dynamic connectivity problems.

Frequently asked questions

Is Number of Provinces easy or hard?

Number of Provinces is categorized as a Medium problem on LeetCode. The core idea—counting connected components in a graph—is straightforward once you recognize the adjacency matrix representation, but it requires familiarity with DFS, BFS, or Union-Find.

How to solve Number of Provinces in O(n^2)?

Iterate through each city and run a DFS or BFS if it has not been visited. During traversal, mark all directly or indirectly connected cities as visited. Each traversal corresponds to one connected component, so increment the province count after each new traversal.

What is the best approach for Number of Provinces?

Depth-First Search is the most common approach. Treat each city as a node and run DFS whenever you encounter an unvisited city to mark all connected cities. Each DFS traversal represents one province. The overall time complexity is O(n^2) because the adjacency matrix requires scanning all neighbors.

What data structure is used in Number of Provinces?

The problem uses a graph represented as an adjacency matrix. Solutions typically rely on DFS or BFS traversal with a visited array, or the Union-Find (Disjoint Set) data structure to merge and track connected components.

What is the time complexity of Number of Provinces?

The standard DFS or BFS solution runs in O(n^2) time because the algorithm scans every entry of the n x n adjacency matrix. Union-Find also requires iterating through the matrix, resulting in O(n^2 · α(n)) time where α(n) is the inverse Ackermann function.

Number of Provinces Python or Java solution approach?

Both Python and Java implementations typically use DFS or Union-Find. The DFS version recursively visits neighbors using the adjacency matrix and tracks visited cities, achieving O(n^2) time and O(n) space complexity.

Is Number of Provinces asked at Google, Amazon, or Meta?

Number of Provinces is a common graph connectivity problem frequently asked in technical interviews. Variants of this problem have appeared at companies like Amazon, Google, Meta, and Microsoft because it tests understanding of graphs, traversal algorithms, and connected components.

Number of Provinces solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Depth-First Search (DFS)

Approach 2: Approach 2: Union-Find

Approach 3: DFS

Approach 4: Union-Find

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Provinces solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Depth-First Search (DFS)

Approach 2: Approach 2: Union-Find

Approach 3: DFS

Approach 4: Union-Find

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems