FastPrep
Problem · Graph

Largest Tree Size in a Forest

Learn this problem
● MediumGoldman Sachs logoGoldman SachsFULLTIMEPHONE SCREEN

Problem statement

Each row [child, parent] in relations is a directed edge in a forest. A node may be a parent, a child, or both, but every child has at most one parent and the edges contain no cycle.

Return the number of distinct nodes in the largest tree. Return 0 when relations is empty.

Function

largestTreeSize(relations: int[][]) → int

Examples

Example 1

relations = [[2,1],[3,1],[5,4]]return = 3

Nodes 1, 2, and 3 form the largest tree.

Example 2

relations = [[2,1],[3,2],[4,3],[6,5]]return = 4

The chain containing nodes 1 through 4 has four nodes.

Constraints

  • 0 <= relations.length <= 200000
  • Every row contains two signed 32-bit integer node labels.
  • Pairs are distinct, every child has at most one parent, and the graph is acyclic.

More Goldman Sachs problems

drafts saved locally
public int largestTreeSize(int[][] relations) {
  // write your code here
}
relations[[2,1],[3,1],[5,4]]
expected3
checking account