How do you solve Number of Provinces on LeetCode?

Number of Provinces (LeetCode #547) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding graph representation is crucial.

What is the brute force solution for Number of Provinces?

The brute force approach for Number of Provinces is Brute Force, with O(n²) time complexity and O(1) space complexity. We can treat the cities as nodes in a graph and use a simple Depth-First Search (DFS) to explore all connected cities. Each time we initiate a DFS from an unvisited city, we can count it as a new province. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Number of Provinces?

Explain your thought process clearly. Consider edge cases, like a single city. Practice both DFS/BFS and Union-Find approaches.

What are common mistakes when solving Number of Provinces?

Forgetting to mark cities as visited in DFS. Not handling the union operation correctly.

#547

Number of Provinces

Medium

Depth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph TraversalUnion-Find

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

Using the Union-Find (Disjoint Set Union) approach allows us to efficiently group connected cities and count the number of unique provinces by merging sets of connected cities.

⚙️

Algorithm

3 steps

1Step 1: Initialize a parent array where each city is its own parent.
2Step 2: For each pair of directly connected cities, union their sets.
3Step 3: Count the number of unique roots in the parent array to determine the number of provinces.

solution.py23 lines

1# Full working Python code
2
3def findCircleNum(isConnected):
4    parent = list(range(len(isConnected)))
5
6    def find(city):
7        if parent[city] != city:
8            parent[city] = find(parent[city])
9        return parent[city]
10
11    def union(city1, city2):
12        root1 = find(city1)
13        root2 = find(city2)
14        if root1 != root2:
15            parent[root1] = root2
16
17    for i in range(len(isConnected)):
18        for j in range(i + 1, len(isConnected)):
19            if isConnected[i][j] == 1:
20                union(i, j)
21
22    provinces = len(set(find(i) for i in range(len(isConnected))))
23    return provinces

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops checking connections, but we use O(n) space for the parent array to track connected components.

1Understanding graph representation is crucial.
2Union-Find is efficient for connectivity problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.