FastPrep
Problem · Graph

Maximum Label Difference in a Connected Component

Learn this problem
● MediumAkuna Capital logoAkuna CapitalOA

Problem statement

You are given an undirected graph with gNodes vertices labeled from 1 through gNodes. For every index i, gFrom[i] and gTo[i] are the endpoints of one undirected edge.

For each connected component, find the difference between its largest and smallest vertex labels. Return the maximum such difference across all connected components. An isolated vertex is a connected component whose difference is 0.

Function

maximumDifference(gNodes: int, gFrom: List<Integer>, gTo: List<Integer>) → int

Examples

Example 1

gNodes = 7gFrom = [1,2,3,5,6]gTo = [2,4,5,7,7]return = 4

The components are {1, 2, 4} and {3, 5, 6, 7}. Their label differences are 4 - 1 = 3 and 7 - 3 = 4, so the answer is 4.

Example 2

gNodes = 4gFrom = []gTo = []return = 0

All four vertices are isolated, so every component has equal minimum and maximum labels and contributes a difference of 0.

Example 3

gNodes = 9gFrom = [1,6,2,3,4]gTo = [6,9,3,4,2]return = 8

The component {1, 6, 9} has label difference 9 - 1 = 8. The cycle {2, 3, 4} has difference 2, and all remaining vertices are isolated.

Constraints

  • gNodes is nonnegative.
  • gFrom.length == gTo.length.
  • Every endpoint is between 1 and gNodes, inclusive.
  • Parallel edges and self-loops are allowed.

More Akuna Capital problems

drafts saved locally
public int maximumDifference(int gNodes, List<Integer> gFrom, List<Integer> gTo) {
  // write your code here
}
gNodes7
gFrom[1,2,3,5,6]
gTo[2,4,5,7,7]
expected4
checking account