Leetcode: Number of Provinces

 

This is an extremely common question asked at Amazon, Goldman Sachs, Dropbox, and Two Sigma. There is a solution using Depth-First search, Breadth-First search and Union Find algorithms, and I will explain each of them here in detail. 

There are n cities and some of them are connected, while others are not. If city a is connected with city b and city b is connected 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. I am given an nxn matrix isConnected where isConnected[i][j] = 1 if the ith and jth city are directly connected, and isConnected [i][j] = 0 otherwise. Return the number of provinces.

For example, if city 1 is connected to city 2, but nothing to city 3, then the number of provinces will be equivalent to 2.  Here are the examples and constraints:

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]

The first solution I want to suggest is a depth-first search which basically marks certain nodes as visited and figures out what isn't visited, to run depth-first search on each node, and if a node doesn't have anything visited, add it as a province. It's pretty simple, really. 

Here's the initial solution: 

public class Solution {

    public void dfs(int[][] M, int[] visited, int i){(

        for(int j = 0; j < M.length; i++){

           //if the node isn't visited for each particular neighbor, mark node as visited

            //and recursively  visit all of the other nodes. 

            if(M[i][j] == 1 && visited[j] == 0){

                visited[j] = 1;

                dfs(M, visited, j);

            }

        }

    }

    public int findCircleNum(int[][] M){

        int[] visited = new int[M.length]; 

        int count = 0;

        //visit all the neighbors of all nodes

        for(int i = 0; i < M.length; i++){

            //if a node is not visited, visit the node and all its neighbors, then increment the count. 

            if(visited[i] == 0) {

                dfs(M, visited, i);

                count++;

            }

        }

    }

}

The next thing to go on is the Breadth-First Search Solution. 

public class Solution {

    public int findCircleNum(int[][] M){

        //keep track of all the visited nodes and number of provinces.

        int[] visited = new int[M.length];

        int count = 0;

        //initialize queue of nodes

        Queue <Integer> queue = new LinkedList<>();

        for(int i = 0; i < M.length; i++){

            //if a node is not visited, add it

            if(visited[i] == 0){

                queue.add(i);

                //add all the children of the node if the child is not visited and is actually a child of the suspected "parent node" 

                while(!queue.isEmpty()){

                    int s = queue.remove();

                    visited[s] = 1; 

                    for(int j = 0; j < M.length; j++) {

                        if (visited[j] == 0 && M[s][j] == 1) {

                            queue.add(j);

                        }

                    }

                    count++;

                }

            }

        //return number of provinces.

        return count;

        }

    }

This has the same time (n^2) and space complexity as the depth-first search solution. 

The last method is through Union find, where we unite the parent and child node together, and we count the number of nodes without the parent node. The time complexity for this algorithm is O(n^3) and the space complexity is O(n). For a pair of nodes we are finding the farthest ancestor parent, and joining other parents.

Here's the implementation:

public class Solution {

    int find(int parent[], int i){

        //find the parent of a parent, until we find one without a parent. Basically go all backtrack on this thing.

        if(parent[i] == -1) return i;

        return find(parent, parent[i]);

    }

    void union(int parent[], int x, int y) {

        //There is an x and y parent. Set the parent of X to Y set, which are both denoted by numbers. 

        int xset = find(parent, x);

        int yset = find(parent, y)

        if(xset != yset) parent[xset] = yset;

    }

    public int findCircleNum(int[][] M) {

        int[] parent = new int[M.length];

        //all the parent array start with no parent

        Arrays.fill(parent, -1);

        for(int i = 0; i < M.length; i++) {

            for(int j = 0; j < M.length; j++){

                //for each element i,j see to find a parent node, assuming each node has a parent, and reset the parent of this node to its farthest ancestor, indicated by the index on the parent array

                if(M[i][j] == 1 && i != j) union(parent, i, j);

            }

        }

        int count = 0;

        //after which find the nodes with no parents. Return the number of nodes with no parents. 

        for(int i = 0; i < parent.length; i++){

            if(parent[i] == -1) count++;

        }

        return count;

    }

}