How should I practice Maximum Label Difference in a Connected Component?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Akuna Capital online assessment problems in FastPrep.

Is Maximum Label Difference in a Connected Component associated with Akuna Capital?

FastPrep tags this as a Akuna Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Maximum Label Difference in a Connected Component

Learn this problem

● Medium

Akuna 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.