Number of Good Paths

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a tree with n nodes labeled 0 to n - 1, an array vals where vals[i] is the value of node i, and an array edges of n - 1 undirected edges [a, b]. A **good path** is a simple path whose two endpoints have the **same value**, and where every node on the path (including the endpoints) has a value **no greater than** that endpoint value. Return the number of distinct good paths. A path and its reverse count once, and a single node by itself is a good path.

Examples

Input: vals = [2,1,2,1,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 6
5 single-node paths, plus `0-1-2` (endpoints 2, middle 1). The path `1-2-3` fails because node 2 has value 2 > 1.
Input: vals = [1], edges = []
Output: 1
A single node is one good path.
Input: vals = [3,1,3,3], edges = [[0,1],[1,2],[1,3]]
Output: 7
4 single nodes plus the paths between each pair of the value-3 nodes 0, 2, 3, all passing through node 1 (value 1).

Constraints

  • `1 <= n <= 3 * 10^4`
  • `vals.length == n`
  • `0 <= vals[i] <= 10^5`
  • `edges.length == n - 1`
  • `edges` forms a valid tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems