Find max node-value range across components
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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:
\[
\text{range(component)} = \max(\text{node labels in component}) - \min(\text{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.
Quick Answer: This question evaluates understanding of undirected graph connectivity and component-wise aggregation, specifically the ability to identify connected components and compute min/max node labels to derive component ranges.
For each connected component in an undirected graph, compute max node label minus min node label and return the maximum range.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (4, [1,2,3], [2,3,1])
Expected Output: 2
Explanation: Component {1,2,3} has range 2.
Input: (5, [1,4], [2,5])
Expected Output: 1
Explanation: The component {4,5} and {1,2} both have range 1.
Input: (1, [], [])
Expected Output: 0
Explanation: An isolated node has range 0.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.