algoadvance

The problem is taken from LeetCode and is defined as follows:

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.

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

Return the total number of provinces.

Example:

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

Clarifying Questions

1. Question: Can the cities be represented as a fully connected graph? Answer: No, the cities are not necessarily fully connected. Some cities might be isolated, and some might form different connected components.

2. Question: Can there be self-loops, i.e., isConnected[i][i] = 1? Answer: Yes, since each city is considered directly connected to itself.

3. Question: Are all values in isConnected either 0 or 1? Answer: Yes, each element is strictly 0 or 1.

Strategy

This problem is essentially about finding the number of connected components in an undirected graph. We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all cities that are part of the same component.

Steps:

1. Initialize a visited list to keep track of cities we have already visited.
2. Iterate over all cities, and for each city, if it has not been visited, start a DFS/BFS to mark all cities in the same province.
3. Each time we start a new DFS/BFS, increment the province count.
4. Return the total number of provinces.

Code

def findCircleNum(isConnected):
    def dfs(city):
        # Mark the city as visited
        visited[city] = True
        # Visit all connected cities
        for connected_city in range(n):
            if isConnected[city][connected_city] == 1 and not visited[connected_city]:
                dfs(connected_city)
    
    n = len(isConnected)
    visited = [False] * n
    province_count = 0
    
    for city in range(n):
        if not visited[city]:
            dfs(city)
            province_count += 1
    
    return province_count

Time Complexity

• Time Complexity: O(n^2)
  • We iterate through each cell in the n x n matrix.
  • Each cell is visited once during DFS, thus visiting each cell leads to O(n^2) complexity.
• Space Complexity: O(n)
  • We use a visited list of size n to keep track of which cities have been visited.
  • The recursion stack for DFS will also potentially go up to n in depth in the worst case (but not more than that).

This solution effectively finds all the provinces by exploring the connectivity graph using DFS. Each time a new DFS is initiated, a new province is counted, ensuring we correctly count all the distinct provinces.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?