547. Number of Provinces (Medium)

Problem

There are n cities. isConnected[i][j] == 1 if city i and city j are directly connected, else 0. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example

• isConnected = [[1,1,0],[1,1,0],[0,0,1]] → 2
• isConnected = [[1,0,0],[0,1,0],[0,0,1]] → 3

LeetCode 547 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: DFS, count connected components

Mark each city as visited when first reached. Each unvisited city that triggers a new DFS is a new province.

Python

def find_circle_num_dfs(isConnected):
    n = len(isConnected)                                    # L1: number of cities
    visited = [False] * n                                   # L2: O(n) visited array
    provinces = 0                                           # L3: O(1)

    def dfs(city):
        visited[city] = True                                # L4: O(1) mark visited
        for neighbor in range(n):                           # L5: scan all potential neighbors
            if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)                               # L6: O(1) per call, recurse

    for city in range(n):                                   # L7: outer scan
        if not visited[city]:
            provinces += 1                                  # L8: O(1) new province
            dfs(city)                                       # L9: DFS from unvisited city

    return provinces

TypeScript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;                           // L1: number of cities
    const visited = new Array(n).fill(false);               // L2: O(n) visited array
    let provinces = 0;                                      // L3: O(1)

    function dfs(city: number): void {
        visited[city] = true;                               // L4: O(1) mark visited
        for (let neighbor = 0; neighbor < n; neighbor++) {  // L5: scan all potential neighbors
            if (isConnected[city][neighbor] === 1 && !visited[neighbor]) {
                dfs(neighbor);                              // L6: O(1) per call, recurse
            }
        }
    }

    for (let city = 0; city < n; city++) {                  // L7: outer scan
        if (!visited[city]) {
            provinces++;                                    // L8: O(1) new province
            dfs(city);                                      // L9: DFS from unvisited city
        }
    }
    return provinces;
}

Swift

final class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        var seen = Set<Int>(), provinces = 0
        func visit(_ city: Int) {
            if !seen.insert(city).inserted { return }
            for next in 0..<n where isConnected[city][next] == 1 { visit(next) }
        }
        for city in 0..<n where !seen.contains(city) { provinces += 1; visit(city) }
        return provinces
    }
}

Where the time goes, line by line

Variables: n = number of cities.

Line	Per-call cost	Times executed	Contribution
L2 (init visited)	$O(1)$ per city	n	$O(n)$
L7 (outer scan)	$O(1)$	n	$O(n)$
L5 (neighbor scan inside DFS)	$O(n)$	once per city visited	$O(n^2)$ ← dominates
L6 (recurse)	$O(1)$	at most n total	$O(n)$

The DFS for each city scans its entire row in isConnected (L5). Every city is visited at most once (L4 prevents re-entry), so L5 executes at most n times for a total of n * n = n^2 operations. This is unavoidable: we must read every entry in the n * n matrix.

Complexity

• Time: $O(n^2)$, driven by L5 (reading the full adjacency matrix).
• Space: $O(n)$ visited array plus $O(n)$ recursion stack.

Approach 2: Union-Find

Union the pairs of directly connected cities. Count distinct root nodes at the end.

Python

def find_circle_num_uf(isConnected):
    n = len(isConnected)                                    # L1: number of cities
    parent = list(range(n))                                 # L2: O(n) init, each city is its own root

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]                  # L3: path halving
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)                          # L4: O(alpha) each
        if ra != rb:
            parent[ra] = rb                                 # L5: O(1) link roots

    for i in range(n):                                      # L6: scan upper triangle
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                union(i, j)                                 # L7: O(alpha) union

    return sum(1 for i in range(n) if find(i) == i)        # L8: count distinct roots

TypeScript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;                           // L1: number of cities
    const parent = Array.from({ length: n }, (_, i) => i); // L2: O(n) init

    function find(x: number): number {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];                 // L3: path halving
            x = parent[x];
        }
        return x;
    }

    function union(a: number, b: number): void {
        const ra = find(a), rb = find(b);                   // L4: O(alpha) each
        if (ra !== rb) parent[ra] = rb;                     // L5: O(1) link roots
    }

    for (let i = 0; i < n; i++) {                           // L6: scan upper triangle
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] === 1) union(i, j);       // L7: O(alpha) union
        }
    }

    return Array.from({ length: n }, (_, i) => i).filter(i => find(i) === i).length;  // L8
}

Swift

struct UnionFind {
    var parent: [Int]
    var rank: [Int]
    init(_ count: Int) { parent = Array(0..<count); rank = Array(repeating: 0, count: count) }
    mutating func find(_ value: Int) -> Int {
        if parent[value] != value { parent[value] = find(parent[value]) }
        return parent[value]
    }
    mutating func union(_ left: Int, _ right: Int) -> Bool {
        var a = find(left), b = find(right)
        if a == b { return false }
        if rank[a] < rank[b] { swap(&a, &b) }
        parent[b] = a
        if rank[a] == rank[b] { rank[a] += 1 }
        return true
    }
}

final class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        var unionFind = UnionFind(n), provinces = n
        for row in 0..<n { for col in (row + 1)..<n where isConnected[row][col] == 1 && unionFind.union(row, col) { provinces -= 1 } }
        return provinces
    }
}

Complexity

• Time: $O(n^2 * alpha(n)$), effectively $O(n^2)$, driven by L6/L7.
• Space: $O(n)$ parent array.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
DFS	$O(n^2)$	$O(n)$	Simple, canonical
Union-Find	$O(n^2 * alpha)$	$O(n)$	Useful when adding connections online

Both approaches are bounded by $O(n^2)$ because you must read the adjacency matrix. Use DFS/BFS for a one-shot query; use Union-Find when connections are added incrementally.

Test cases

Python

def find_circle_num(isConnected):
    n = len(isConnected)
    visited = [False] * n
    provinces = 0

    def dfs(city):
        visited[city] = True
        for neighbor in range(n):
            if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)

    for city in range(n):
        if not visited[city]:
            provinces += 1
            dfs(city)
    return provinces

def _run_tests():
    # Example 1: two provinces
    assert find_circle_num([[1,1,0],[1,1,0],[0,0,1]]) == 2

    # Example 2: three isolated cities
    assert find_circle_num([[1,0,0],[0,1,0],[0,0,1]]) == 3

    # All connected: one province
    assert find_circle_num([[1,1,1],[1,1,1],[1,1,1]]) == 1

    # Single city
    assert find_circle_num([[1]]) == 1

    # Chain: 1-2-3 all one province
    assert find_circle_num([[1,1,0],[1,1,1],[0,1,1]]) == 1

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);
    let provinces = 0;

    function dfs(city: number): void {
        visited[city] = true;
        for (let nb = 0; nb < n; nb++)
            if (isConnected[city][nb] === 1 && !visited[nb]) dfs(nb);
    }

    for (let city = 0; city < n; city++) {
        if (!visited[city]) { provinces++; dfs(city); }
    }
    return provinces;
}

console.assert(findCircleNum([[1,1,0],[1,1,0],[0,0,1]]) === 2);
console.assert(findCircleNum([[1,0,0],[0,1,0],[0,0,1]]) === 3);
console.assert(findCircleNum([[1,1,1],[1,1,1],[1,1,1]]) === 1);
console.assert(findCircleNum([[1]]) === 1);
console.assert(findCircleNum([[1,1,0],[1,1,1],[0,1,1]]) === 1);
console.log("all tests pass");

Related topics

• Number of Islands, same connected-components pattern on a grid
• Graph Valid Tree, Union-Find to check single component with no cycle
• Number of Connected Components in an Undirected Graph, edge-list version of the same problem

Related concepts

• Graph Traversal, the visited set model for exploring nodes and edges without repetition.
• Union Find, the component tracking structure for connectivity as edges are processed.