Number of Provinces

📋

Problem

Imagine a country with several cities connected by roads. We want to find out how many distinct groups of cities are connected directly or indirectly, representing provinces.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and 0 otherwise. A province is a group of directly or indirectly connected cities and no other cities outside of the group. Return the total number of provinces.

1 ≤ n ≤ 10^5isConnected[i][j] is either 0 or 1isConnected[i][i] = 1 for all iisConnected[i][j] = isConnected[j][i]

Edge cases: n = 1 → output 1 (single city is one province)All cities connected → output 1 (one big province)No cities connected except self → output n (each city is its own province)

</>

IDE

def findCircleNum(isConnected: List[List[int]]) -> int:public int findCircleNum(int[][] isConnected)int findCircleNum(vector<vector<int>>& isConnected)function findCircleNum(isConnected)

def findCircleNum(isConnected):
    # Write your solution here
    pass

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findCircleNum(vector<vector<int>>& isConnected) {
    // Write your solution here
    return 0;
}

function findCircleNum(isConnected) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Incorrectly merging all cities into one province regardless of connectivity.✅ Ensure union/find or DFS only merges cities with direct or indirect connections, not all nodes blindly.

Wrong: nFailing to merge connected cities, treating all as isolated.✅ Implement proper DFS or Union-Find to merge connected components.

Wrong: 0Not counting any provinces due to incorrect visited initialization or loop conditions.✅ Initialize visited array correctly and count provinces when visiting unvisited nodes.

Wrong: 3Off-by-one or incomplete traversal causing extra province count.✅ Check loop boundaries and ensure DFS/Union-Find visits all connected nodes.

Wrong: 3Asymmetric handling of adjacency matrix causing incorrect province count.✅ Ensure symmetric checks or union both directions for isConnected[i][j] and isConnected[j][i].

✓

Test Cases

Focus on handling minimal and maximal connectivity edge cases.

Check your traversal logic for subtle bugs like off-by-one and symmetry.

Optimize your solution to avoid timeouts on large inputs using Union-Find.

t1_01basic

Input{"isConnected":[[1,1,0],[1,1,0],[0,0,1]]}

Expected2

⏱ Performance - must finish in 2000ms

Cities 0 and 1 are connected, forming one province. City 2 is isolated, forming another province.

💡 Think about how to find connected components in a graph.

💡 Use DFS or Union-Find to group connected cities.

💡 Count how many distinct groups you can form from the adjacency matrix.

Why it failed: Incorrect province count: likely missed indirect connections or did not mark visited cities properly. Fix by ensuring DFS or Union-Find merges all connected nodes.

✓ Correctly identified 2 provinces by grouping connected cities.

t1_02basic

Input{"isConnected":[[1,0,0],[0,1,0],[0,0,1]]}

Expected3

⏱ Performance - must finish in 2000ms

No cities are connected except themselves, so each city forms its own province.

💡 Check if your code handles isolated nodes correctly.

💡 Each city with no connections to others should count as a separate province.

💡 Ensure your visited tracking does not skip isolated nodes.

Why it failed: Returned fewer provinces than expected: likely failed to count isolated cities as separate provinces. Fix by initializing visited array and counting unvisited nodes properly.

✓ Correctly counted 3 provinces for isolated cities.

t2_01edge

Input{"isConnected":[[1]]}

Expected1

⏱ Performance - must finish in 2000ms

Single city forms exactly one province.

💡 Consider the smallest input size possible.

💡 A single node with a self-loop is one province.

💡 Make sure your code handles n=1 without errors.

Why it failed: Returned 0 or error on single city input: likely did not handle base case n=1. Fix by ensuring loop and visited initialization handle single element.

✓ Correctly returned 1 province for single city.

t2_02edge

Input{"isConnected":[[1,1,1],[1,1,1],[1,1,1]]}

Expected1

⏱ Performance - must finish in 2000ms

All cities are connected directly or indirectly, forming one big province.

💡 Test the case where all nodes are connected.

💡 Your algorithm should merge all nodes into one group.

💡 Check if your union or DFS merges all connected nodes.

Why it failed: Returned more than 1 province: likely failed to merge all connected nodes. Fix by ensuring union/find or DFS visits all reachable nodes.

✓ Correctly identified one big province.

t2_03edge

Input{"isConnected":[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]}

Expected4

⏱ Performance - must finish in 2000ms

No cities connected except self, so each city is its own province.

💡 Test multiple isolated nodes.

💡 Each isolated node should count as a separate province.

💡 Verify your visited array marks each node separately.

Why it failed: Returned fewer than 4 provinces: likely missed counting isolated nodes. Fix by counting all unvisited nodes as separate provinces.

✓ Correctly counted 4 provinces for isolated cities.

t3_01corner

Input{"isConnected":[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]}

Expected2

⏱ Performance - must finish in 2000ms

Cities 0,1,2 form one province; city 3 is isolated forming another.

💡 Beware of off-by-one errors in loops.

💡 Check if your DFS or union includes all connected nodes, not just immediate neighbors.

💡 Ensure you do not stop early and miss indirect connections.

Why it failed: Returned 3 provinces instead of 2: likely off-by-one or incomplete traversal. Fix by ensuring DFS/union visits all reachable nodes.

✓ Correctly identified 2 provinces including indirect connections.

t3_02corner

Input{"isConnected":[[1,0,1,0],[0,1,0,0],[1,0,1,0],[0,0,0,1]]}

Expected2

⏱ Performance - must finish in 2000ms

Cities 0 and 2 connected forming one province; cities 1 and 3 isolated forming separate provinces, but city 1 isolated so total 2 provinces.

💡 Watch out for symmetric matrix assumptions.

💡 Check if your code treats isConnected[i][j] and isConnected[j][i] consistently.

💡 Make sure union/find merges both directions.

Why it failed: Returned 3 provinces instead of 2: likely asymmetric handling of connections. Fix by ensuring symmetric checks or union both ways.

✓ Correctly handled symmetric connections and counted 2 provinces.

t3_03corner

Input{"isConnected":[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,1,0],[0,0,1,1,0],[0,0,0,0,1]]}

Expected3

⏱ Performance - must finish in 2000ms

Two pairs of connected cities (0-1 and 2-3) plus one isolated city (4) form three provinces.

💡 Test multiple disconnected groups.

💡 Ensure your union/find merges all connected nodes in each group.

💡 Count all distinct connected components correctly.

Why it failed: Returned fewer than 3 provinces: likely merged disconnected groups incorrectly. Fix by careful union/find or DFS per group.

✓ Correctly counted 3 distinct provinces.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n^2) brute force will time out; efficient Union-Find or DFS with pruning required.

💡 Consider time complexity of your approach.

💡 Union-Find with path compression runs efficiently here.

💡 Avoid nested loops over all pairs; use efficient data structures.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing Union-Find with path compression or optimized DFS.

✓ Efficient O(n^2 * α(n)) or better solution passed within time limit.

Practice

1. Examine the following buggy Union-Find code snippet for the network connectivity problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with 'return self.find(self.parent[x])' in find method

B. Line 'self.count = n' in __init__ method

C. Line 'self.rank[rootX] += 1' in union method

D. Line 'self.parent[rootX] = rootY' in union method

Solution

1. Step 1: Identify path compression implementation

   The find method should assign the parent during recursion: self.parent[x] = self.find(self.parent[x]) to flatten the tree.

2. Step 2: Understand impact of missing assignment

   Without path compression, find operations become slower and can cause TLE or incorrect component counts on large inputs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing path compression assignment is a classic subtle bug [OK]

Hint: Path compression requires assignment to parent during find [OK]

Common Mistakes:

• Forgetting path compression assignment
• Misplacing rank increment
• Incorrectly decrementing count

2. What is the time complexity of the optimal union-find based solution that sorts edges and processes them to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob?

medium

A. O(n^2) due to checking connectivity repeatedly for each edge

B. O(m log m + m α(n)) where m is number of edges and α is inverse Ackermann function

C. O(m n) because union-find operations can be linear in worst case

D. O(m + n) since union-find operations are almost constant time

Solution

1. Step 1: Identify sorting cost

   Sorting edges costs O(m log m) where m is number of edges.

2. Step 2: Analyze union-find operations

   Union-find operations take O(α(n)) amortized per operation, so total O(m α(n)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting dominates, union-find nearly constant -> O(m log m + m α(n)) [OK]

Hint: Sorting edges dominates complexity, union-find nearly constant [OK]

Common Mistakes:

• Assuming union-find is O(n) per operation
• Ignoring sorting cost
• Confusing n and m in complexity

3. What is the time complexity of the optimal union-find + priority queue approach to the smallest string with swaps problem, where n is the length of the string and m is the number of pairs?

medium

A. O(n log n + m α(n)) where α(n) is the inverse Ackermann function from union-find operations

B. O(n * m) due to iterating over all pairs for each character

C. O(n²) because sorting characters in each connected component can be quadratic in worst case

D. O(m log n) because union-find operations dominate the runtime

Solution

1. Step 1: Analyze union-find operations

   Union-find performs m union/find operations in O(m α(n)) time, where α(n) is very slow growing and almost constant.

2. Step 2: Analyze sorting step

   Sorting characters in all connected components combined takes O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find plus sorting dominates runtime as O(n log n + m α(n)) [OK]

Hint: Union-find nearly linear; sorting dominates with n log n [OK]

Common Mistakes:

• Assuming O(n*m) due to nested loops
• Confusing sorting cost as O(n²)
• Ignoring inverse Ackermann factor

4. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order

5. Suppose the Swim in Rising Water problem is modified so that you can revisit cells multiple times (cycles allowed), and the grid elevations can be negative. Which modification to the union-find approach is necessary to correctly solve this variant?

hard

A. Sort cells by absolute elevation and union in that order to handle negative values.

B. Add a visited set to union-find to prevent cycles during union operations.

C. Use a priority queue (min-heap) to process cells by elevation dynamically instead of sorting all upfront.

D. No change needed; the original union-find with sorting by elevation works as is.

Solution

1. Step 1: Understand impact of negative elevations and revisits

   Negative elevations break sorting assumption; revisiting cells means connectivity can change dynamically.

2. Step 2: Identify suitable data structure

   A priority queue allows processing cells in order of elevation dynamically, handling negative values and revisits correctly.

3. Step 3: Why other options fail

   Sorting by absolute elevation loses ordering semantics; visited sets don't apply to union-find; original approach assumes non-negative elevations and no revisits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Priority queue enables dynamic elevation processing [OK]

Hint: Dynamic processing needed for negative elevations and revisits [OK]

Common Mistakes:

• Sorting by absolute elevation breaks ordering
• Assuming union-find alone handles cycles
• Ignoring negative elevation impact on sorting