Number of Provinces Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Audible Bloomberg DoorDash Dropbox eBay Facebook Goldman Sachs Google Microsoft PayPal Snapchat Twitter Two Sigma Uber
ByteDancViews 246

Problem Statement

Number of Provinces Leetcode Solution – We are given an adjacency matrix representation of a graph and need to find the number of provinces. Here province is a group of directly or indirectly connected cities and no other cities outside of the group.

Example

Example 1:

Number of Provinces Leetcode Solution

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Number of Provinces Leetcode Solution

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Explanation for Number of Provinces Leetcode Solution

  • In the first eg. we can see there is an edge between 1 & 2, hence they are directly connected and counted as a single province. Node 3 is isolated and counted as a separate province. Therefore, there are 2 provinces.
  • In the 2nd eg. None of them have any edge and hence 3 provinces

Approach

We can use the DFS algorithm to traverse all the nodes directly or indirectly connected to a specific node. We will run DFS only on the nodes that are not visited. Hence, this question boils down to finding the number of disconnected components in a graph. The number of times DFS runs will give us the number of provinces.

Code

C++ code for Number of Provinces

class Solution {
    void dfs(vector<vector<int>> &isConnected, vector<int> &vis, int u, int nodes) {
        // cout<<u<<" ";
        vis[u]=1;
        for(int v=0; v<nodes; v++) {
            if(u!=v && isConnected[u][v]==1) {
                if(!vis[v]) {
                    dfs(isConnected, vis, v, nodes);
                }
            }
        }
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int nodes = isConnected.size();
        vector<int> vis(nodes, 0);
        int cnt=0;
        for(int i=0; i<nodes; i++) {
            if(!vis[i]) {
                cnt++;
                dfs(isConnected, vis, i, nodes);
            }
            
        }
        
        return cnt;
    }
};

Java code for Number of Provinces

class Solution {
    public void dfs(int[][] isConnected, boolean[] vis, int u, int nodes) {
        vis[u]=true;
        for(int v=0; v<nodes; v++) {
            if(u!=v && isConnected[u][v]==1) {
                if(!vis[v]) {
                    dfs(isConnected, vis, v, nodes);
                }
            }
        }
        
    }
    public int findCircleNum(int[][] isConnected) {
        int nodes = isConnected.length;
        boolean [] vis = new boolean[nodes];
        int cnt = 0;
        for(int i=0; i<nodes; i++) {
            if(!vis[i]) {
                cnt++;
                dfs(isConnected, vis, i, nodes);
            }
            
        } 
        return cnt;
    }
}

Complexity Analysis for Number of Provinces LeetCode Solution

  • Time complexity: O(n^2)
    • The complete matrix (isConnected) of size n^2 is traversed.
  • Space complexity: O(n)
    • a visited array (vis) of size n is used.

Reference: https://en.wikipedia.org/wiki/Depth-first_search

Translate »