The O(n) Club: Counting Socially Awkward Provinces (LeetCode 547, With Less Anxiety)

The O(n) Club: Counting Socially Awkward Provinces (LeetCode 547, With Less Anxiety)

⚡ TL;DR

Stuck with a matrix where isConnected[i][j] tells you which cities (or people dodging the group chat) are directly friends? You want to count how many totally-connected clusters (“provinces”) exist, even if Bob only knows Alice via Carol, who friended everyone like it was 2007. TL;DR: DFS from every unvisited city — every new run finds a new friend group.

// DFS the introverts!
int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(isConnected, visited, i);
            provinces++;
        }
    }
    return provinces;
}
void dfs(int[][] isConnected, boolean[] visited, int city) {
    visited[city] = true;
    for (int friend = 0; friend < isConnected.length; friend++) {
        if (isConnected[city][friend] == 1 && !visited[friend]) {
            dfs(isConnected, visited, friend);
        }
    }
}

🧠 How Devs Usually Mess This Up

If you just count direct 1’s in the matrix, you’ll get the number of high fives, not provinces. (Nice try, but Susan knows Todd through Sally — it counts!) Also, don’t treat the matrix as one-way: it’s undirected, so isConnected[i][j] is always equal to isConnected[j][i]. And please — don’t forget to check ALL indirect links. Friend-of-friend-of-friend… it’s LinkedIn, but sadder.

🔍 What’s Actually Going On

Imagine a party so awkward, only some people speak, but if you can chain enough “Oh, you know her too?” connections, the whole group can (in theory) communicate. Each group you can’t escape from forms a “province.” DFS here is you, forced to introduce yourself to everyone remotely tied to your first acquaintance, then finding another corner and repeating. Union-Find also works, but unless there are 10,000 partygoers, just use DFS — it’s less paperwork.

🛠️ PseudoCode

• Set your answer and check-in list:
  

  int provinces = 0;
  boolean[] visited = new boolean[n];

• Loop through each city:
  

  for (int i = 0; i < n; i++)

  If unvisited, it’s a brand new group.
• DFS from the new city:
  

  if (!visited[i]) {
      dfs(isConnected, visited, i);
      provinces++;
  }

  This colors in the entire group. Count increases only at the start.
• DFS logic in Java:
  

  void dfs(int[][] M, boolean[] visited, int i) {
      visited[i] = true;
      for (int j = 0; j < M.length; j++) {
          if (M[i][j] == 1 && !visited[j]) {
              dfs(M, visited, j);
          }
      }
  }

  Recursively drag everyone out of the corner into the conversation.

💻 The Code

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        return provinces;
    }
    private void dfs(int[][] isConnected, boolean[] visited, int city) {
        visited[city] = true;
        for (int friend = 0; friend < isConnected.length; friend++) {
            if (isConnected[city][friend] == 1 && !visited[friend]) {
                dfs(isConnected, visited, friend);
            }
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Everybody’s Their Own Friend: Ignore isConnected[i][i] — that’s just existential confirmation, not another group.
• Direct != Only: Groups aren’t just direct friends; it’s all those “friend-of-a-friend” connections.
• Matrix is Symmetric: Save time — don’t check both [i][j] and [j][i]. It’s undirected, not passive-aggressive.
• Big-O Reality Check: Time is O(n^2): you’ll look at most pairs. Space is O(n), barely enough to fill your debug console.

🧠 Interviewer Brain-Tattoo

Counting only direct friends? That’s like only reading emails addressed to you. Provinces = the full distribution list. Don’t be that dev.