Number of Provinces

MediumDepth-first searchLeetCode 547 ↗World 6-2

0:00 / 0:00

Count groups of connected cities: pick an unvisited city, flood its whole province with a search, and count how many floods it takes.

▼

The problem

LeetCode 547 (Medium). There are n cities and an n × n matrix isConnected where isConnected[i][j] = 1 if cities i and j are directly connected (the matrix is symmetric and isConnected[i][i] = 1). A province is a group of cities connected directly or indirectly, with no other city outside the group. Return the number of provinces.

Examples (LeetCode's): [[1,1,0],[1,1,0],[0,0,1]] → 2 (0 and 1 share a road, 2 stands alone) and [[1,0,0],[0,1,0],[0,0,1]] → 3.

TRY IT ON LEETCODE ▶

The solution

def find_circle_num(isConnected):
    n = len(isConnected)
    seen = [False] * n
    def visit(i):
        seen[i] = True
        for j in range(n):
            if isConnected[i][j] and not seen[j]:
                visit(j)
    provinces = 0
    for i in range(n):
        if not seen[i]:
            visit(i)
            provinces += 1
    return provinces

Transcript

Number of Provinces. n cities, and a matrix marks which pairs are directly connected. A province is a group of cities linked directly or through others. Count the provinces.

In the first example, zero and one share a road and two stands alone: two provinces. In the second, nothing is connected, so every city is its own province: three.

The slow way: for every pair of cities, search the map for a path between them, then group them. That's n squared searches, each reading the whole matrix: n to the fourth.

The better idea: count flood fills. Walk the cities in order. When a city has no banner yet, a herald rides out from it, a depth-first search that plants one colour on every city he can reach. Each ride is one new province. Union find would also work.

In code, keep a seen list. Visit marks a city, then scans its row and visits every connected city not yet seen. The main loop starts a visit at each unseen city and adds one.

Walking the first example: city zero has no banner, so count one. The herald reads row zero, finds one, and flags it. Row one only points back. City one is already flagged: skip it. City two is new: count two. Its row links only itself. Answer: two.

Every row is read once: O of n squared time, and O of n space for the seen list and the stack.

Find an unflagged city, flag its whole province, count the rides. That's Number of Provinces.