Count Visited Nodes in a Directed Graph
01 · Problem
You are given a directed graph with n nodes labelled 0 to n - 1, described by an array edges of length n: node i has exactly one outgoing edge, to edges[i]. No node points to itself.
For each starting node i, walk along the outgoing edges and stop as soon as you are about to step onto a node you have already visited during this walk. Count how many distinct nodes the walk visited, including node i itself.
Return an array answer of length n where answer[i] is that count for starting node i.
02 · Examples
edges = [1,2,3,1,3]
[4,3,3,3,4]
Nodes 1, 2, 3 form a cycle, so starting from any of them visits 3 nodes. From 0 the walk is 0 -> 1 -> 2 -> 3, visiting 4 nodes. From 4 the walk is 4 -> 3 -> 1 -> 2, also 4 nodes.
edges = [1,0,1]
[2,2,3]
Nodes 0 and 1 form a 2-cycle. Starting at 2 visits 2 -> 1 -> 0 before returning to 1, which is 3 nodes.
edges = [3,6,1,0,5,4,4]
[2,4,5,2,2,2,3]
Nodes 0 and 3 form a 2-cycle, as do nodes 4 and 5, so each of them visits 2 nodes. From 6 the walk is 6 -> 4 -> 5 (3 nodes), from 1 it is 1 -> 6 -> 4 -> 5 (4 nodes), and from 2 it is 2 -> 1 -> 6 -> 4 -> 5 (5 nodes).
03 · Constraints
- 01n == edges.length
- 022 <= n <= 105
- 030 <= edges[i] <= n - 1
- 04edges[i] != i
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.