Connected Graphs: Number Of Provinces
Photo by Oleg Laptev on Unsplash

Some coding problems are straightforward. Others?

Well, they look simple until you dive in and realize you’ve been swimming in circles.

LeetCode’s Number of Provinces feels like that to us at first.

It’s a classic graph problem disguised in the form of a matrix, and honestly, it’s one of those problems that teach you more about your problem-solving process than just the solution itself.

Let me take you through how to crack it, the mistakes that should be avoided, and why a simple Breadth-First Search (BFS) can turn out to be your best friend.

Not A Member? Read Here.

Understanding the Problem

Imagine a map of cities, where some are directly connected, and some aren’t. The challenge is to figure out how many distinct groups of connected cities (or “provinces”) exist. The connections are given as an adjacency matrix, like this:

[
 [1, 1, 0],
 [1, 1, 0],
 [0, 0, 1]
]

Here’s how it breaks down:

  • Cities 0 and 1 are directly connected, forming one province.
  • City 2 is isolated, forming its own province.

So, the answer is 2. Simple, right? Well… not quite at first.

Initial Thoughts

The first instinct? Maybe iterate through the matrix and count the direct connections. But then it hits— this isn’t about direct connections alone but also about indirect ones. If city A is connected to city B, and city B is connected to city C, then A and C are also part of the same province.

That’s when the light bulb switches on: this is a classic graph traversal problem, and you need to think in terms of connected components.

Why BFS?

I debate between DFS and BFS. Both are solid choices for graph traversal, but BFS felt more intuitive for this problem, especially with an adjacency matrix. Plus, BFS avoids the risk of hitting recursion depth limits, which can be a silent trap in Python for large graphs.

The Plan of Attack

  1. Track What’s Visited: We need a visited list to ensure we aren’t counting the same city twice.
  2. Start the Search: For every city that hasn’t been visited, trigger a BFS. This would explore all connected cities and mark them as visited.
  3. Count the Provinces: Every new BFS traversal meant you’d discovered a new province.

The Code That Works

class Solution:
    def __init__(self):
        self.count = 0  # Tracks the number of provinces
    def do_bfs(self, isConnected, visited, start):
        queue = [start]
        visited[start] = 1
        while queue:
            i = queue.pop(0)
            for j in range(len(isConnected)):
                if isConnected[i][j] == 1 and not visited[j]:
                    queue.append(j)
                    visited[j] = 1
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited = [0] * len(isConnected)
        
        for i in range(len(visited)):
            if visited[i] == 0:
                self.count += 1  # Found a new province
                self.do_bfs(isConnected, visited, i)
        return self.count

Why This Approach Feels Right

  • Simplicity Wins: The code is clean and easy to follow. No overcomplicate the logic, and that’s a win in itself.
  • Accurate Counting: Each time you discover an unvisited city, you know it’s the start of a new province, so incrementing the count at that exact point avoids any confusion.
  • Efficient Traversal: The BFS ensures that all directly and indirectly connected cities get marked as visited in one go.

What I Almost Got Wrong

Not gonna lie, I almost made a few mistakes here:

  • Forgetting to Mark Cities as Visited Immediately: There’s a temptation to mark cities as visited only after processing them, but doing it the moment they’re enqueued avoids redundant processing.
  • Confusing Direct vs. Indirect Connections: It’s easy to miss the fact that provinces aren’t just about direct links but chains of connections. BFS naturally handles this by exploring layer by layer.
  • Overthinking the Approach: Sometimes, we chase the “optimal” solution when the straightforward one is already efficient. BFS is simple, readable, and gets the job done.

Why Not DFS?

Honestly? No big reason. DFS would work just fine, and some prefer it for its elegance in recursive form. But I find BFS more straightforward when working with adjacency matrices, especially when avoiding stack overflows in larger datasets.

Plus, the iterative nature of BFS feels more controllable when thinking in terms of real-world connected cities.

What This Problem Taught Me

  1. Don’t Overcomplicate. The simplest solution is often the best one. Don’t look for clever tricks when a basic approach works.
  2. Think in Layers. Graph problems can feel abstract, but thinking in terms of real-world scenarios — like connected cities — can help clarify the logic.
  3. Details Matter. Missing small details like when to mark a node as visited can completely derail your solution.

How would you approach this problem? Did you prefer DFS over BFS? Or did you find a way to optimize it further? I’d love to hear your thoughts! Drop a comment and let’s geek out over algorithms together. 🚀

In case we are meeting for the first time, come over here, it’ll be worth the roller coaster of articles that are gonna come up in the next few weeks.

Use this to get to know more about me — https://linktr.ee/shashwat_writes

Liked the story? Coffee☕ And Code💚
Discover the stories that will make your 🤍 beat!

This article was published on March 18th, 2025 in Coffee☕ And Code💚publication.