Number of Provinces problem in Javascript

September 8th, 2021

Problem

Link to leetcode

There are n cities. Some of them are connected, while some are not. If city a is connected directly with the city b, and city b is connected directly with the 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 is directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Solution

To find the total number of provinces, we need to find all the cities connected to a particular city i to do this, we will loop n times that is the size of the matrix. Technically we call it as an adjacent list

Let us consider an example as shown here in figure

Here 1 and 2 cities are connected while city 3 is not, so in this example we can say we have 2 provinces since there are two groups of cities

The adjacent list will look like this

Now we know that city 3 is not connected with either 2 or 1

whenever there is a break in the connection we need to increment the number of province.

we will be having a loop over the adjacent list and at each point, we will add all the cities in the adjacent list in a queue.

when the queue is empty which indicates we have visited all the connections that are direct or indirect from each city. So that next unvisited site tells us this is a new province

Here is the full code in javascript

const findCircleNum = (isConnected) => {
  const size = isConnected.length;
  const adjList = new Array(size).fill(0).map(() => []);
  let provinceCount = 0;
  let isVisited = new Array(size).fill(false);
  // make a adjacent list visits from each node.
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (i !== j && isConnected[i][j]) {
        adjList[i].push(j);
      }
    }
  }
  const queue = []; // initialising a queue that takes all the cities in a province
  for (let a = 0; a < adjList.length; a++) {
    if (!isVisited[a]) {
      // if not visited then this is a new provinces so count ++
      provinceCount++;
    } else {
      continue;
    }
    queue.push(adjList[a]); // push the adjacent list at the current province
    while (queue.length > 0) {
      // we will visit all the places that is directly and indirectly connected with a by utilising the queue
      const curr = queue.shift();
      for (let i = 0; i < curr.length; i++) {
        // here we visit all the place directly connected with city a
        if (isVisited[curr[i]]) {
          // we have alread visited here either its in the queue or its direct connections are already iterated
          continue;
        } else {
          queue.push(adjList[curr[i]]);
          isVisited[curr[i]] = true; // store all the places that we visited
        }
      }
    }
  }
  return provinceCount;
};