Number of Provinces - Practice Coding Problems

Number of Provinces - Problem

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 i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Input & Output

Example 1 — Two Separate Provinces

$ Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

› Output: 2

💡 Note: Cities 0 and 1 are connected (province 1). City 2 is isolated (province 2). Total: 2 provinces.

Example 2 — All Connected

$ Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

› Output: 3

💡 Note: No connections between cities. Each city is its own province: 0, 1, 2. Total: 3 provinces.

Example 3 — Chain Connection

$ Input: isConnected = [[1,1,0],[1,1,1],[0,1,1]]

› Output: 1

💡 Note: City 0↔1, City 1↔2, so all cities are in one connected province. Total: 1 province.

Constraints

1 ≤ n ≤ 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Adjacency matrix showing city connections

Find Components

Group connected cities using DFS/BFS

Count Provinces

Number of separate connected components

Key Takeaway

🎯 Key Insight: Count connected components by starting DFS from each unvisited city

Asked in

A Amazon 45 f Facebook 32 G Google 28 M Microsoft 22

The key insight is that provinces are connected components in an undirected graph. Each unvisited city starts a new DFS traversal, representing a new province. Best approach uses DFS for simplicity or Union-Find for efficiency. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set)	O(n² α(n))	O(n)	Use Union-Find data structure to efficiently group connected cities
Brute Force DFS	O(n²)	O(n)	For each unvisited city, perform DFS to mark all connected cities
Breadth-First Search	O(n²)	O(n)	Use BFS with queue to explore each province level by level

Union-Find (Disjoint Set) — Algorithm Steps

Initialize each city as its own parent
For each connection, union the two cities
Use path compression in find operation
Count unique root parents

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each city points to itself

Union Connected

Merge cities that are connected

Count Roots

Count unique parent nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* parent;
    int* rank;
    int n;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x), py = find(uf, y);
    if (px == py) return;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

int solution(int** isConnected, int n) {
    UnionFind* uf = createUnionFind(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                unionSets(uf, i, j);
            }
        }
    }
    
    int* roots = (int*)calloc(n, sizeof(int));
    int count = 0;
    for (int i = 0; i < n; i++) {
        int root = find(uf, i);
        if (roots[root] == 0) {
            roots[root] = 1;
            count++;
        }
    }
    
    free(uf->parent);
    free(uf->rank);
    free(uf);
    free(roots);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int n = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && line[i+1] != '[') n++;
    }
    
    int** isConnected = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        isConnected[i] = (int*)malloc(n * sizeof(int));
    }
    
    int row = 0, col = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] >= '0' && line[i] <= '9') {
            isConnected[row][col] = line[i] - '0';
            col++;
            if (col == n) {
                col = 0;
                row++;
            }
        }
    }
    
    int result = solution(isConnected, n);
    printf("%d\n", result);
    
    for (int i = 0; i < n; i++) {
        free(isConnected[i]);
    }
    free(isConnected);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² α(n))

Check all n² connections with inverse Ackermann function overhead

⚠ Quadratic Growth

Space Complexity

O(n)

Parent and rank arrays of size n

⚡ Linearithmic Space

67.0K Views

High Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Disjoint Set) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler