Skip to main content
Talentd

Number of Good Paths - Solution & Explanation

HardArrayHash TableTreeUnion Find15 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.

You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

A good path is a simple path that satisfies the following conditions:

  1. The starting node and the ending node have the same value.
  2. All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node's value should be the maximum value along the path).

Return the number of distinct good paths.

Note that a path and its reverse are counted as the same path. For example, 0 -> 1 is considered to be the same as 1 -> 0. A single node is also considered as a valid path.

 

Example 1:

Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
Explanation: There are 5 good paths consisting of a single node.
There is 1 additional good path: 1 -> 0 -> 2 -> 4.
(The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.)
Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].

Example 2:

Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 7
Explanation: There are 5 good paths consisting of a single node.
There are 2 additional good paths: 0 -> 1 and 2 -> 3.

Example 3:

Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.

 

Constraints:

  • n == vals.length
  • 1 <= n <= 3 * 104
  • 0 <= vals[i] <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.

Approach Overview

Problem Overview: You are given a tree where each node has a value. A path is considered good if the maximum value along the path is equal to the values of both endpoints. The task is to count all such valid paths, including single-node paths.

Approach 1: DFS with Path Tracking (O(n^2) time, O(n) space)

This approach treats every node as a potential starting point and explores reachable nodes using depth‑first search. While traversing, maintain the maximum value encountered along the current path and check whether the endpoint satisfies the good path condition. Because the graph is a tree, each DFS explores unique paths without cycles, but repeating the search from every node leads to many redundant traversals. A small optimization is pruning branches when a node value exceeds the starting node’s value since that path can never form a valid good path. Despite pruning, the worst case still reaches O(n^2) time when many nodes share similar values.

This method helps you reason about the definition of a good path and understand the constraints of the problem, but it does not scale well for large inputs.

Approach 2: Union-Find with Value Grouping (O(n log n) time, O(n) space)

The optimal strategy processes nodes in increasing order of their values. First sort nodes by value. Then gradually connect nodes using a Union-Find structure while only merging neighbors whose values are less than or equal to the current node value. This ensures that when two nodes are connected, all nodes in that component have values not exceeding the current threshold.

For each value group, count how many nodes with that value exist inside each connected component. If a component contains k nodes with the same value, it contributes k * (k - 1) / 2 additional good paths because every pair can form a valid path whose maximum equals that value. Union-Find operations such as find and union run in near constant time with path compression. Sorting the nodes dominates the runtime, giving overall complexity O(n log n).

This technique combines graph connectivity with sorting. The key insight is that processing values in ascending order guarantees that newly formed components never introduce invalid higher values on the path.

Recommended for interviews: The Union-Find approach is what most interviewers expect. The DFS approach shows you understand the definition of a valid path, but recognizing that the problem can be converted into incremental connectivity with Union-Find demonstrates stronger algorithmic insight.

Approach 1: Union-Find with Value Grouping

We can use a union-find (disjoint-set) data structure to solve the problem efficiently. The key idea is to process nodes in order of their values and use the union-find structure to keep track of connected components where nodes can potentially form good paths.

Steps:

  1. Sort the nodes based on their values.
  2. Initialize a union-find data structure.
  3. Process each node, connecting it with its neighbors (using edges) if those neighbors have the same or smaller values.
  4. Keep track of the size of each component formed by nodes with the same value and calculate the number of good paths within each component.

The solution initializes a union-find structure to track connected nodes. Nodes are sorted by their values so that processing happens in a value-based order. The union-find data structure helps recognize connected components efficiently and handle their size calculations to find the number of good paths effectively.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(E log V + V log V), where E is the number of edges and V is the number of vertices, due to sorting and union-find operations.

Space Complexity: O(V), for storing parent ranks and counts in the union-find structure.

Try this approach in the editor →

Approach 2: DFS with Path Tracking

Another way to solve the problem is by using Depth-First Search (DFS) to explore available paths and check if they satisfy the good path conditions. This approach typically involves building the graph from edges and recursively checking paths using DFS while keeping track of the path max value.

Steps:

  1. Convert the edge list into an adjacency list for navigation through DFS.
  2. Try every pair of nodes as end points for potential good paths, and use DFS to determine reachable, valid paths that satisfy the good path conditions.

This approach can become computationally expensive for large graphs but serves as a brute force method to ensure all paths are checked.

In this solution, the adjacency list representation allows for easy traversal of nodes. The DFS method visits nodes to form paths and checks conditions for being a good path when visiting from node to node.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(V + E) per path exploration, but can be exponential (potentially O(V^2)) if exploring all node pairs for paths.

Space Complexity: O(V), as it uses recursion stack and storage for unique paths.

Try this approach in the editor →

Approach 3: Sorting + Union Find

To ensure that the starting point (or endpoint) of the path is greater than or equal to all points on the path, we can consider sorting all points from small to large first, then traverse and add them to the connected component, specifically as follows:

When traversing to point a, for the adjacent point b that is less than or equal to vals[a], if they are not in the same connected component, they can be merged. And we can use all points in the connected component where point a is located with a value of vals[a] as the starting point, and all points in the connected component where point b is located with a value of vals[a] as the endpoint. The product of the number of the two types of points is the contribution to the answer when adding point a.

The time complexity is O(n times log n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find with Value Grouping

Time Complexity: O(E log V + V log V), where E is the number of edges and V is the number of vertices, due to sorting and union-find operations.

Space Complexity: O(V), for storing parent ranks and counts in the union-find structure.

DFS with Path Tracking

Time Complexity: O(V + E) per path exploration, but can be exponential (potentially O(V^2)) if exploring all node pairs for paths.

Space Complexity: O(V), as it uses recursion stack and storage for unique paths.

Sorting + Union Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Path TrackingO(n^2)O(n)Useful for understanding the definition of good paths or when constraints are small.
Union-Find with Value GroupingO(n log n)O(n)Best general solution for large inputs. Efficiently tracks connected components while processing node values in sorted order.

Video Solution

Number of Good Paths - Leetcode 2421 - Python • NeetCodeIO • 19,939 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Good Paths easy or hard?
Number of Good Paths is labeled Hard because the brute-force interpretation leads to quadratic traversal. The challenge is recognizing that processing nodes by value and merging components with Union-Find transforms the problem into an efficient connectivity counting task.
How to solve Number of Good Paths in O(n)?
A strict O(n) solution is difficult because the algorithm typically requires sorting node values. The common optimized solution achieves O(n log n) by sorting nodes and using Union-Find to merge components incrementally. After sorting, component counting determines how many valid endpoint pairs form good paths.
Number of Good Paths Python or Java solution
Typical implementations use Union-Find with path compression and union by rank. Python and C++ are commonly used due to concise DSU implementations, while Java and JavaScript versions follow the same logic with adjacency lists and component counting after unions.
What is the best approach for Number of Good Paths?
The most efficient solution uses Union-Find combined with sorting node values. Nodes are processed in increasing order, and neighbors with smaller or equal values are merged into components. Within each component, nodes sharing the same value generate combinations of valid paths. This approach runs in O(n log n) time and O(n) space.
What data structure is used in Number of Good Paths?
The key data structure is Union-Find (Disjoint Set Union). It efficiently tracks connected components while edges are added. The solution also uses adjacency lists to represent the tree and sorting to process nodes by increasing value.
What is the time complexity of Number of Good Paths?
The optimal solution runs in O(n log n) time due to sorting the nodes by value. Union-Find operations such as find and union are nearly constant time with path compression, so they do not significantly increase the overall complexity. Space complexity is O(n) for the parent and component tracking arrays.
Is Number of Good Paths asked at Google Amazon or Meta?
Graph and Union-Find problems similar to Number of Good Paths frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of disjoint set data structures, graph traversal, and recognizing when incremental connectivity can replace brute-force path enumeration.

Ready to solve this problem?

Practice Number of Good Paths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Checking Existence of Edge Length Limited Paths

Next

Checking Existence of Edge Length Limited Paths II