547. Number of Provinces

At a Glance

Topic: graphs
Pattern: Union-Find or DFS on adjacency matrix
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 547

Problem (one-liner)

isConnected is n x n adjacency matrix for undirected friend graph (1 edge). Return number of connected components (provinces).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Matrix adjacency for undirected graph
Same as component counting with dense storage

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Scan rows DFS — visit row row, flood through 1s — O(n^2).
Union-Find over edges implied by matrix — also O(n^2).

Optimal Solution

Go

func findCircleNum(isConnected [][]int) int {
	nodeCount := len(isConnected)
	visited := make([]bool, nodeCount)
	components := 0

	var dfs func(start int)
	dfs = func(start int) {
		visited[start] = true
		for neighbor := 0; neighbor < nodeCount; neighbor++ {
			if isConnected[start][neighbor] == 1 && !visited[neighbor] {
				dfs(neighbor)
			}
		}
	}

	for node := 0; node < nodeCount; node++ {
		if !visited[node] {
			components++
			dfs(node)
		}
	}
	return components
}

JavaScript

function findCircleNum(isConnected) {
  const nodeCount = isConnected.length;
  const visited = new Array(nodeCount).fill(false);
  let components = 0;

  function dfs(start) {
    visited[start] = true;
    for (let neighbor = 0; neighbor < nodeCount; neighbor += 1) {
      if (isConnected[start][neighbor] === 1 && !visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }

  for (let node = 0; node < nodeCount; node += 1) {
    if (!visited[node]) {
      components += 1;
      dfs(node);
    }
  }
  return components;
}