Number of Provinces
Your company has n offices. isConnected is an n x n matrix: isConnected[i][j] is 1 when a cable runs straight between office i and office j, and 0 when it does not. Every office is cabled to itself, and the matrix reads the same in both directions. Offices that can reach each other through any chain of cables are on the same network. Return how many separate networks there are. Limits: 1 <= n <= 1400, and every entry is 0 or 1. Heads-up: one network can hold hundreds of offices, so a recursive walk can go hundreds of calls deep. Python stops at 1000 calls by default, so a loop with your own stack or queue is the safer choice. Example (5 offices): cables: 0-1, 1-2, 3-4 isConnected = [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]] offices 0 and 2 share no cable, but both reach office 1 networks: {0, 1, 2} and {3, 4} => 2
You're handed a table of which offices are cabled straight to which, and you need to count the separate networks, where a link through a middle office still counts. Interviewers love it because the graph hides inside a plain matrix, and you have to see that the matrix is the graph. The classic trap is counting one network twice because you lost track of which offices you've already reached. Expect 1 to 1,400 offices in a square matrix of zeros and ones.
Examples
You write
find_circle_num(is_connected: List[List[int]])
Example 1
- Input
- isConnected = [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]]
- returns
- 2
Example 2
- Input
- isConnected = [[1]]
- returns
- 1
Save this for your laptop
The editor and Run need a bigger screen. The link opens Number of Provinces ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.