Scale Engineer

Count Visited Nodes in a Directed Graph

Hard
#2573Time: O(n^2) - For each of the `n` starting nodes, the traversal can take up to O(n) steps in the worst case (a single long path). This results in a quadratic time complexity.Space: O(n) - In each simulation, the `HashSet` can store up to `n` nodes in the worst-case scenario where the path traverses all nodes before repeating.1 company
Patterns
Dynamic ProgrammingMemoization
Data structures
Graph
Companies
BNY Mellon

Prompt

There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.

You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].

Consider the following process on the graph:

  • You start from a node x and keep visiting other nodes through edges until you reach a node that you have already visited before on this same process.

Return an array answer where answer[i] is the number of different nodes that you will visit if you perform the process starting from node i.

 

Example 1:

Input: edges = [1,2,0,0]
Output: [3,3,3,4]
Explanation: We perform the process starting from each node in the following way:
- Starting from node 0, we visit the nodes 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 3.
- Starting from node 1, we visit the nodes 1 -> 2 -> 0 -> 1. The number of different nodes we visit is 3.
- Starting from node 2, we visit the nodes 2 -> 0 -> 1 -> 2. The number of different nodes we visit is 3.
- Starting from node 3, we visit the nodes 3 -> 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 4.

Example 2:

Input: edges = [1,2,3,4,0]
Output: [5,5,5,5,5]
Explanation: Starting from any node we can visit every node in the graph in the process.

 

Constraints:

  • n == edges.length
  • 2 <= n <= 105
  • 0 <= edges[i] <= n - 1
  • edges[i] != i

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem for each starting node. For every node from 0 to n-1, we traverse the graph, keeping track of the nodes visited in the current path using a HashSet. The traversal stops when we encounter a node that has already been seen in this specific traversal. The number of nodes collected in the HashSet gives us the answer for the starting node.

Algorithm

  • Create an integer array answer of size n.
  • For each node i from 0 to n-1:
    • Create a HashSet<Integer> pathVisited to keep track of nodes visited in the current traversal.
    • Initialize currentNode = i.
    • In a loop, continue as long as currentNode can be added to pathVisited (meaning it's a new node for this path).
      • In each iteration, update currentNode to edges[currentNode].
    • The size of pathVisited is the number of unique nodes visited. Store this in answer[i].
  • Return the answer array.

Walkthrough

We initialize an answer array of size n. We then iterate through each node i from 0 to n-1 to calculate answer[i]. For each i, we begin a simulation. A HashSet called visited_in_path is used to store nodes visited in the current traversal, which starts from node i. We also use a counter, count, initialized to 0. We start with currentNode = i. In a loop, as long as currentNode is not in visited_in_path, we add it to the set, increment our count, and move to the next node by setting currentNode = edges[currentNode]. When the loop terminates, it means we've encountered a node that was already in visited_in_path. The final value of count (or the size of the set) is the number of different nodes visited, which we store in answer[i]. After iterating through all possible starting nodes, the answer array is complete and returned.

import java.util.HashSet;import java.util.Set; class Solution {    public int[] countVisitedNodes(int[] edges) {        int n = edges.length;        int[] answer = new int[n];         for (int i = 0; i < n; i++) {            Set<Integer> visitedInPath = new HashSet<>();            int currentNode = i;            while (visitedInPath.add(currentNode)) {                currentNode = edges[currentNode];            }            answer[i] = visitedInPath.size();        }         return answer;    }}

Complexity

Time

O(n^2) - For each of the `n` starting nodes, the traversal can take up to O(n) steps in the worst case (a single long path). This results in a quadratic time complexity.

Space

O(n) - In each simulation, the `HashSet` can store up to `n` nodes in the worst-case scenario where the path traverses all nodes before repeating.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the logic described in the problem statement.

Cons

  • Highly inefficient due to redundant computations. The traversal from one node might largely overlap with the traversal from another, but this work is repeated.

  • The time complexity is too high for the given constraints, which will likely result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution { public int [] countVisitedNodes ( List < Integer > edges ) { int n = edges . size (); int [] ans = new int [ n ]; int [] vis = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { if ( ans [ i ] == 0 ) { int cnt = 0 , j = i ; while ( vis [ j ] == 0 ) { vis [ j ] = ++ cnt ; j = edges . get ( j ); } int cycle = 0 , total = cnt + ans [ j ]; if ( ans [ j ] == 0 ) { cycle = cnt - vis [ j ] + 1 ; } j = i ; while ( ans [ j ] == 0 ) { ans [ j ] = Math . max ( total --, cycle ); j = edges . get ( j ); } } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem