Level Value Frequencies
MediumGraph · Bloomberg
You are given an undirected graph with n nodes labeled 0 to n - 1, a list edges where each [a, b] is an edge between a and b, and a list values where values[i] is the integer value stored on node i.
The level of a node is the number of edges on a shortest path from start to that node (so start itself is at level 0). Nodes that cannot be reached from start have no level.
Consider the nodes whose level is exactly level. Return a list of [value, count] pairs, one for each distinct value among those nodes, where count is how many of those nodes hold that value. Sort the pairs by value in ascending order. Return an empty list if no node is at that level.
The graph may contain cycles, self-loops and repeated edges.
Example 1
- Input:
- n = 6, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [0, 5]], start = 0, level = 2, values = [7, 1, 1, 4, 9, 7]
- Output:
- [[4, 1], [9, 1]]
- Explanation
- Nodes 1, 2 and 5 are one edge from node 0. Node 3 is two edges away, and so is node 4 via node 5, even though the path through node 3 is longer. Their values 4 and 9 each appear once.
Example 2
- Input:
- n = 5, edges = [[0, 1], [0, 2], [1, 3], [1, 4]], start = 0, level = 2, values = [1, 2, 2, 3, 3]
- Output:
- [[3, 2]]
- Explanation
- Nodes 3 and 4 are both at level 2 and both hold the value 3, so it is reported with a count of 2.
Example 3
- Input:
- n = 3, edges = [[0, 1]], start = 0, level = 2, values = [5, 5, 6]
- Output:
- []
- Explanation
- Node 2 is unreachable and node 1 is only one edge away, so nothing is at level 2.
Constraints
1 <= n <= 10^50 <= edges.length <= 2 * 10^5, with0 <= a, b < nvalues.length == nand-10^9 <= values[i] <= 10^90 <= start < nand0 <= level <= n