Find max node-value range across components

Q: Find max node-value range across components

This is a Coding & Algorithms interview question from Snapchat for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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.

Find max node-value range across components

Problem

Example

Requirements

Comments (0)