Number of Provinces - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Graphs, Depth-First Search (DFS), Connected Components

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What is a province?

  • A province is a group of cities that are directly or indirectly connected.

• How does the input matrix represent connections?

  • is_connected[i][j] = 1 indicates that city i is directly connected to city j.

• Can the matrix have self-loops?

  • Yes, is_connected[i][i] = 1 indicates that a city is connected to itself.

HAPPY CASE
Input: is_connected = [1,1,0],[1,1,0],[0,0,1](/codepath/compsci_guides/wiki/1,1,0],[1,1,0],[0,0,1)
Output: 2
Explanation: The first two cities are connected to each other, forming one province. The third city is isolated, forming another province.

Input: is_connected = [1,0,0],[0,1,0],[0,0,1](/codepath/compsci_guides/wiki/1,0,0],[0,1,0],[0,0,1)
Output: 3
Explanation: Each city is isolated, so there are 3 provinces.

EDGE CASE
Input: is_connected = [1](/codepath/compsci_guides/wiki/1)
Output: 1
Explanation: A single city is its own province.

Input: is_connected = [1,1],[1,1](/codepath/compsci_guides/wiki/1,1],[1,1)
Output: 1
Explanation: Both cities are connected, forming one province.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal Problems, we can consider the following approaches:

• DFS (Depth-First Search): Explore all connected cities from a starting city.
• Union-Find (Disjoint Set): Group cities into provinces based on their connections.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Treat the given matrix as an adjacency matrix representing a graph. Use DFS to explore all connected cities starting from each unvisited city. Every time we start a new DFS, it corresponds to discovering a new province.

1) Initialize a `visited` list to keep track of cities we have explored.
2) Define a DFS helper function:
   a) Mark the current city as visited.
   b) Explore all other cities that are connected to the current city and not visited.
3) Iterate through all cities. If a city is unvisited, call DFS on it and increment the province count.
4) Return the total number of provinces.

⚠️ Common Mistakes

• Not marking cities as visited, leading to infinite loops.
• Not handling isolated cities correctly.

4: I-mplement

Implement the code to solve the algorithm.

def num_provinces(is_connected):
    def dfs(city):
        # Mark the city as visited
        visited[city] = True
        # Explore all other cities connected to the current city
        for neighbor in range(n):
            if is_connected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)
    
    n = len(is_connected)  # Number of cities
    visited = [False] * n  # Keep track of visited cities
    province_count = 0
    
    # Perform DFS for each unvisited city
    for city in range(n):
        if not visited[city]:
            dfs(city)
            province_count += 1  # Each DFS call represents a new province
    
    return province_count

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: is_connected = [1,1,0],[1,1,0],0,0,1

  • Province 1: Visit cities 0 and 1.
  • Province 2: Visit city 2.
  • Output: 2

• Input: is_connected = [1,0,0],[0,1,0],0,0,1

  • Province 1: Visit city 0.
  • Province 2: Visit city 1.
  • Province 3: Visit city 2.
  • Output: 3

• Input: is_connected = 1

  • Output: 1 (A single city forms its own province.)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of cities.

• Time Complexity: O(N^2) because we potentially visit every element in the adjacency matrix.
• Space Complexity: O(N) due to the recursion stack in DFS and the visited list.