Show problems as
Classic problem #2421HardArrayHash TableTreeUnion-FindGraph TheorySorting

Number of Good Paths

Real-world version: Level Treks Through the Huts
Tracked in this browser only
Read Number of Good Paths on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A reserve has n shelter huts numbered 0 to n - 1. Hut i stands at height heights[i].

The huts are linked by n - 1 trails, handed over as an edge list trails, where trails[i] = [u, v] is a trail joining hut u and hut v. The trails link the whole reserve together and contain no loop, so between any two huts there is exactly one route that never visits a hut twice. That route is the trek between them.

A trek is level when both of the following hold:

  • the two huts at its ends stand at exactly the same height;
  • no hut along the route stands higher than that height.

Return how many level treks the reserve has. A single hut on its own counts as a level trek. A trek walked in one direction and the same trek walked back are one trek, counted once.

Examples

Example 1

Input
heights = [4, 9, 4], trails = [[1, 0], [1, 2]]
Output
3

Each of the three huts on its own is a level trek. The trek between hut 0 and hut 2 has matching ends at height 4, but it runs through hut 1, which stands at height 9, so it is not level.

Example 2

Input
heights = [2, 2, 2, 2], trails = [[0, 2], [0, 1], [3, 0]]
Output
10

Every hut stands at height 2, so no route can pass a higher hut. The four single-hut treks and the six treks between different huts are all level.

Example 3

Input
heights = [1, 1, 5, 1, 1], trails = [[0, 1], [2, 1], [2, 3], [4, 3]]
Output
7

The five single-hut treks are level, and so are the trek from hut 0 to hut 1 and the trek from hut 3 to hut 4, both of which stay at height 1. Every other trek between two huts of height 1 runs through hut 2 at height 5.

Constraints

  • n == heights.length
  • 1 <= heights.length <= 3 * 10^4
  • 0 <= heights[i] <= 10^5
  • trails.length == heights.length - 1
  • trails[i].length == 2
  • 0 <= trails[i][j] < heights.length, and the two huts of a trail are different
  • The trails form a tree: the reserve is connected and has no loop.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_level_treks(heights: list[int], trails: list[list[int]]) -> int:
Java
public int countLevelTreks(int[] heights, int[][] trails)

More on the same topics