FastPrep
Problem · Graph

Maximum Difference

Learn this problem
● EasyAkuna CapitalFULLTIMEOA

Problem statement

Given a set of nodes and a set of edges between pairs of nodes, first identify the connected components in the graph. A connected component is a group of nodes that are all linked, either directly or through other nodes in the group.

For each connected component, calculate the difference between its largest and smallest node values, and return the maximum of these differences.

Function

maximumDifference(g_nodes: int, g_from: int[], g_to: int[]) → int

Complete the function maximumDifference in the editor below.

maximumDifference has the following parameters:

  1. int g_nodes: the number of nodes in the graph
  2. int g_from[g_edges]: one endpoint of each edge
  3. int g_to[g_edges]: the other endpoint of each edge

Returns:

  • int: the maximum difference between the largest and smallest node value within any connected component

Examples

Example 1

g_nodes = 4g_from = [1, 2]g_to = [2, 3]return = 2
Nodes 1, 2, and 3 form one connected component, whose difference is 3 - 1 = 2. Node 4 is isolated, so its component difference is 0. The maximum difference is 2.

Example 2

g_nodes = 6g_from = [1, 2, 4]g_to = [2, 3, 6]return = 2
The connected components are {1, 2, 3}, {4, 6}, and {5}. Their differences are 2, 2, and 0, so the result is 2.

Example 3

g_nodes = 5g_from = [1, 4]g_to = [5, 2]return = 4
The components are {1, 5}, {2, 4}, and {3}. Their differences are 4, 2, and 0, so the maximum difference is 4.

Constraints

  • 1 ≤ g_nodes ≤ 105
  • 1 ≤ g_edges ≤ min(105, (g_nodes × (g_nodes - 1)) / 2)

More Akuna Capital problems

drafts saved locally
public int maximumDifference(int g_nodes, int[] g_from, int[] g_to) {
    // write your code here
}
g_nodes4
g_from[1, 2]
g_to[2, 3]
expected2
checking account