Problem
You are given an undirected graph with:
-
n
: number of nodes (assume nodes are labeled
1..n
)
-
from[]
: list of edge start nodes
-
to[]
: list of edge end nodes
Each pair (from[i], to[i]) represents an undirected edge.
For each connected component, compute the difference:
range(component)=max(node labels in component)−min(node labels in component)
Return the maximum range across all connected components. (An isolated node has range 0.)
Example
Input:
-
n = 4
-
from = [1, 2, 3]
-
to = [2, 3, 1]
The component {1,2,3} has range 3 - 1 = 2, node 4 alone has range 0, so return 2.
Requirements
-
Provide an efficient solution and state the
time and space complexity
.
-
Assume
from.length == to.length
and the graph may contain multiple components.