Last updated on February 2nd, 2025 at 06:24 am

Here, we see a Number of Provinces LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Union-Find

Companies

Bloomberg, Twosigma

Level of Question

Medium

Number of Provinces LeetCode Solution

1. Problem Statement

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 ith city and the jth 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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Islands”. This pattern is commonly used to solve problems where you need to find connected components in a graph or grid. The problem here is to find the number of connected components (provinces) in a graph represented by the adjacency matrix isConnected.

3. Code Implementation in Different Languages

3.1 Number of Provinces C++

class Solution {
public:
void soln(vector<int>adj[],int node,vector<bool>&vis){
    vis[node] = 1;
    for(auto i:adj[node]){
        if(!vis[i]){
            soln(adj,i,vis);
        }
    }
}
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int>adj[n];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(isConnected[i][j]){
                adj[i].push_back(j);
                adj[j].push_back(i);
                }
            }
        }
        vector<bool>vis(n,0);
        int ans= 0;
        for(int i = 0;i<n;i++){
            if(!vis[i]){
                soln(adj,i,vis);
                ans++;
            }
        }
        return ans;
    }
};

3.2 Number of Provinces Java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        boolean[]visited = new boolean[N];
        int count = 0;
        for(int i = 0; i < N ;i++){
            if(!visited[i]){
                count++;
                dfs(isConnected,i,visited);
            }
        }
      return count;  
    }
    private void dfs(int[][]isConnected,int i,boolean[]visited){
        for(int j = 0 ; j < isConnected[i].length ; j++){
            if(!visited[j] && isConnected[i][j] != 0){
                visited[j] = true;
                dfs(isConnected,j,visited);
            }
        }
    }
    
}

3.3 Number of Provinces JavaScript

var findCircleNum = function(isConnected) {
    class UnionFind {
        constructor(n) {
            this.graph = [...Array(n)].map((_, i) => i);
            this.groups = n;
        }
        find(id) {
            if(this.graph[id] === id) return id;
            this.graph[id] = this.find(this.graph[id]);
            return this.graph[id];
        }
        union(x, y) {
            const rootX = this.find(x);
            const rootY = this.find(y);
            if(rootX !== rootY) {
                this.graph[rootY] = rootX;
                this.groups--;
            }
        }
    }
    const N = isConnected.length, unionfind = new UnionFind(N);
    for(let r = 0; r < N; r++) {
        for(let c = 0; c < N; c++) {
            if(isConnected[r][c]) unionfind.union(r, c);
        }
    }
    return unionfind.groups;
};

3.4 Number of Provinces Python

class Solution(object):
    def findCircleNum(self, isConnected):
        if not isConnected: return 0
        s = len(isConnected)
        seen = set()
        def dfs(p):
            for q, adj in enumerate(isConnected[p]):
                if (adj == 1) and (q not in seen):
                    seen.add(q)
                    dfs(q)
        cnt = 0
        for i in range(s):
            if i not in seen: 
                dfs(i)
                cnt += 1
        return cnt

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N²)	O(N²) + O(N)
Java	O(N²)	O(N)
JavaScript	O(N²)	O(N)
Python	O(N²)	O(N)