547. Number of Provinces

How to solve Number of Provinces (LeetCode 547): the approach in brief

The 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.

Pattern

Number of Provinces is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph DFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Approach outline

1. Consider modeling the cities and their direct connections as a graph where nodes represent cities and edges represent connections.
2. Think about how to identify groups of directly or indirectly connected cities; what graph traversal methods can help you explore connected components?
3. Implement a traversal method such as DFS or BFS starting from an unvisited city to mark all cities in the same province as visited.

Complexity

The reference solution runs in O(n^2) time and O(n) space.

Asked at

Number of Provinces has been reported in interviews at Amazon, Two Sigma, Goldman Sachs, Dropbox, Facebook, Audible.