[LeetCode] 841. Keys and Rooms

1. Question

Topics
Companies
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. Thoughts

3. Tips learned

4. My solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited = set()
        provinces = 0

        for city_index in range(len(isConnected)):
            if city_index in visited:
                continue
            need_visit = deque([city_index])
            provinces += 1
            while need_visit:
                visit_index = need_visit.pop()
                if visit_index not in visited:
                    visited.add(visit_index)
                    need_visit.extend(
                        i
                        for i, key in enumerate(isConnected[visit_index])
                        if key == 1 and i not in visited and i != visit_index
                    )

        return provinces

114/114 cases passed (193 ms)
Your runtime beats 97.99 % of python3 submissions
Your memory usage beats 49.47 % of python3 submissions (17.3 MB)

5. AI Solution and Improvements

Your solution for calculating the number of provinces based on the isConnected matrix is a good approach. It uses a Depth-First Search (DFS) algorithm to explore the connections between cities. Each time a new, unvisited city is found, it indicates the start of a new province, and the connected cities are marked as visited. This method is efficient for the problem at hand.

However, there are a few optimizations and improvements that can be made:

1. Use a Recursive DFS Approach: Instead of using a deque, you can implement DFS recursively, which can simplify the code. The recursive approach naturally follows the depth-first path without the need for an explicit data structure to track the cities to visit.

2. Simplify the Checking Condition: In the inner loop, the condition can be simplified. You don't need to check if i != visit_index because isConnected[i][i] will always be 1 and i will already be in visited when you're exploring its neighbors.

Here's an optimized version of your code using a recursive DFS approach:

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(city):
            for neighbor, connected in enumerate(isConnected[city]):
                if connected and neighbor not in visited:
                    visited.add(neighbor)
                    dfs(neighbor)

        visited = set()
        provinces = 0

        for city_index in range(len(isConnected)):
            if city_index not in visited:
                visited.add(city_index)
                dfs(city_index)
                provinces += 1

        return provinces

In this version, the dfs function is used to mark all cities connected to a given city as visited. When the dfs function is called, it means a new province has been found, so the province count is incremented. This version is more concise and arguably easier to understand, as it leverages the nature of recursive DFS to navigate through connected cities.