Katkat
Back

Find max node-value range across components

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to traverse an undirected graph to identify connected components and perform aggregations over the nodes within each component.

Problem Statement

You are given an undirected graph represented as an adjacency list, where each node has a unique integer label. A 'connected component' is a subgraph where every pair of vertices is connected by a path. Your task is to find the maximum 'range' among all connected components in the graph. The range of a component is defined as the difference between the maximum node label and the minimum node label within that component.

Function Signature

def max_component_range(n: int, edges: list[list[int]]) -> int:
    # n: number of nodes labeled 0 to n-1
    # edges: list of [u, v] pairs representing undirected edges

Examples

Example 1:

  • Input: n = 4, edges = [[0, 1], [2, 3]]
  • Output: 1
  • Explanation: Two components: {0, 1} with range 1-0=1, and {2, 3} with range 3-2=1. Max range is 1.

Example 2:

  • Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
  • Output: 2
  • Explanation: Two components: {0, 1, 2} with range 2-0=2, and {3, 4} with range 4-3=1. Max range is 2.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 10^5
  • Node labels are integers from 0 to n-1.

Edge Cases

  • A graph with no edges (each node is its own component; range is 0).
  • A fully connected graph (all nodes in one component).
  • Disconnected nodes.

Hints

Hint 1

Represent the graph using an adjacency list to allow for efficient traversal.

Hint 2

Use Depth First Search (DFS) or Breadth First Search (BFS) to visit all nodes in a component while keeping track of the minimum and maximum node labels encountered.

Hint 3

Maintain a boolean array to track visited nodes to ensure each node is processed exactly once.

Follow-up questions

  • How would you modify your solution if the nodes were not labeled 0 to n-1, but were arbitrary integers (e.g., non-consecutive IDs)?
  • What is the time and space complexity of your solution in terms of nodes (V) and edges (E)?
  • How would you approach this problem if the graph was so large it could not fit entirely into memory, requiring a distributed graph processing approach?