LeetCode #2421 — HARD

Number of Good Paths

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The 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 i^th node. You are also given a 2D integer array edges where edges[i] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

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

The starting node and the ending node have the same value.
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 * 10⁴
0 <= vals[i] <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges represents a valid tree.

Step 01

Brute Force Baseline

Problem summary: 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: The starting node and the ending node have the same value. 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map · Tree · Union-Find

Example 1

[1,3,2,1,3]
[[0,1],[0,2],[2,3],[2,4]]

Example 2

[1,1,2,2,3]
[[0,1],[1,2],[2,3],[2,4]]

Example 3

[1]
[]

Core Insight

What unlocks the optimal approach

Can you process nodes from smallest to largest value?
Try to build the graph from nodes with the smallest value to the largest value.
May union find help?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2421: Number of Good Paths
class Solution {
    private int[] p;

    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        int n = vals.length;
        p = new int[n];
        int[][] arr = new int[n][2];
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        Map<Integer, Map<Integer, Integer>> size = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            arr[i] = new int[] {vals[i], i};
            size.computeIfAbsent(i, k -> new HashMap<>()).put(vals[i], 1);
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        int ans = n;
        for (var e : arr) {
            int v = e[0], a = e[1];
            for (int b : g[a]) {
                if (vals[b] > v) {
                    continue;
                }
                int pa = find(a), pb = find(b);
                if (pa != pb) {
                    ans += size.get(pa).getOrDefault(v, 0) * size.get(pb).getOrDefault(v, 0);
                    p[pa] = pb;
                    size.get(pb).put(
                        v, size.get(pb).getOrDefault(v, 0) + size.get(pa).getOrDefault(v, 0));
                }
            }
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

// Accepted solution for LeetCode #2421: Number of Good Paths
func numberOfGoodPaths(vals []int, edges [][]int) int {
	n := len(vals)
	p := make([]int, n)
	size := map[int]map[int]int{}
	type pair struct{ v, i int }
	arr := make([]pair, n)
	for i, v := range vals {
		p[i] = i
		if size[i] == nil {
			size[i] = map[int]int{}
		}
		size[i][v] = 1
		arr[i] = pair{v, i}
	}

	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}

	sort.Slice(arr, func(i, j int) bool { return arr[i].v < arr[j].v })
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ans := n
	for _, e := range arr {
		v, a := e.v, e.i
		for _, b := range g[a] {
			if vals[b] > v {
				continue
			}
			pa, pb := find(a), find(b)
			if pa != pb {
				ans += size[pb][v] * size[pa][v]
				p[pa] = pb
				size[pb][v] += size[pa][v]
			}
		}
	}
	return ans
}

# Accepted solution for LeetCode #2421: Number of Good Paths
class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        n = len(vals)
        p = list(range(n))
        size = defaultdict(Counter)
        for i, v in enumerate(vals):
            size[i][v] = 1

        ans = n
        for v, a in sorted(zip(vals, range(n))):
            for b in g[a]:
                if vals[b] > v:
                    continue
                pa, pb = find(a), find(b)
                if pa != pb:
                    ans += size[pa][v] * size[pb][v]
                    p[pa] = pb
                    size[pb][v] += size[pa][v]
        return ans

// Accepted solution for LeetCode #2421: Number of Good Paths
use std::{cmp::Ordering, collections::HashMap};

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<i32>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, mut i: usize) -> usize {
        while i != self.parent[i] {
            self.parent[i] = self.parent[self.parent[i]];
            i = self.parent[i];
        }
        i
    }

    fn union(&mut self, a: usize, b: usize) -> bool {
        let a_root = self.find(a);
        let b_root = self.find(b);

        if a_root == b_root {
            return false;
        }
        match self.rank[a_root].cmp(&self.rank[b_root]) {
            Ordering::Less => {
                self.parent[a_root] = b_root;
                self.rank[b_root] += self.rank[a_root];
            }
            _ => {
                self.parent[b_root] = a_root;
                self.rank[a_root] = self.rank[b_root];
            }
        }
        true
    }
}

impl Solution {
    pub fn number_of_good_paths(vals: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
        let adj = Self::create_adj_list(&edges);
        let val_to_index = Self::create_val_to_index(&vals);

        let mut res = 0;
        let mut uf = UnionFind::new(vals.len());

        let mut keys: Vec<i32> = val_to_index.keys().cloned().collect();
        keys.sort();

        for val in keys {
            for i in val_to_index.get(&val).unwrap_or(&vec![]) {
                for nei in adj.get(&(*i as i32)).unwrap_or(&vec![]) {
                    if vals[*nei as usize] <= vals[*i] {
                        uf.union(*nei as usize, *i);
                    }
                }
            }
            let mut count = HashMap::new();
            for i in val_to_index.get(&val).unwrap() {
                *count.entry(uf.find(*i)).or_insert(0) += 1;
                res += count.get(&uf.find(*i)).unwrap();
            }
        }
        
        res
    }

    pub fn create_adj_list(edges: &Vec<Vec<i32>>) -> HashMap<i32, Vec<i32>> {
        let mut adj = HashMap::new();

        for edge in edges {
            let a = edge[0];
            let b = edge[1];

            adj.entry(a).or_insert(vec![]).push(b);
            adj.entry(b).or_insert(vec![]).push(a);
        }

        adj
    }

    pub fn create_val_to_index(vals: &Vec<i32>) -> HashMap<i32, Vec<usize>> {
        let mut val_to_index = HashMap::new();

        for (i, val) in vals.iter().enumerate() {
            val_to_index.entry(*val).or_insert(vec![]).push(i);
        }

        val_to_index
    }
}

// Accepted solution for LeetCode #2421: Number of Good Paths
class UnionFind {
    parent: number[];
    rank: number[];

    constructor(n: number) {
        this.parent = new Array(n).fill(0).map((_, i) => i);
        this.rank = new Array(n).fill(0);
    }

    find(i: number): number {
        while (i !== this.parent[i]) {
            this.parent[i] = this.parent[this.parent[i]];
            i = this.parent[i];
        }
        return i;
    }

    union(a: number, b: number): boolean {
        let [aRoot, bRoot] = [this.find(a), this.find(b)];

        if (aRoot == bRoot) return false;

        if (this.rank[aRoot] < this.rank[bRoot]) {
            this.parent[aRoot] = bRoot;
            this.rank[bRoot] += this.rank[aRoot];
        } else {
            this.parent[bRoot] = aRoot;
            this.rank[aRoot] += this.rank[bRoot];
        }

        return true;
    }
}

function getAdjList(edges: number[][]): Map<number, number[]> {
    let adj = new Map();

    for (let e of edges) {
        let [a, b] = [e[0], e[1]];

        let [adjA, adjB] = [adj.get(a) || [], adj.get(b) || []];

        adjA.push(b);
        adjB.push(a);

        adj.set(a, adjA);
        adj.set(b, adjB);
    }

    return adj;
}

function getValToIndex(vals: number[]): Map<number, number[]> {
    let valToIndex = new Map();

    for (let i in vals) {
        let val = vals[i];
        let arr = valToIndex.get(val) || [];
        arr.push(+i);
        valToIndex.set(val, arr);
    }

    return valToIndex;
}

function numberOfGoodPaths(vals: number[], edges: number[][]): number {
    let adj = getAdjList(edges);
    let valToIndex = getValToIndex(vals);

    let res = 0;
    let uf = new UnionFind(vals.length);

    let keys = Array.from(valToIndex.keys());
    keys.sort((a, b) => a - b);

    for (let val of keys) {
        for (let i of valToIndex.get(val)!) {
            for (let nei of adj.get(i) || []) {
                if (vals[nei] <= vals[i]) {
                    uf.union(nei, i);
                }
            }
        }
        let count = new Map();

        for (let i of valToIndex.get(val)!) {
            let c = count.get(uf.find(i)) || 0;
            count.set(uf.find(i), c + 1);
            res += count.get(uf.find(i));
        }
    }

    return res;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(h)

Approach Breakdown

LEVEL ORDER

O(n) time

O(n) space

BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.

DFS TRAVERSAL

O(n) time

O(h) space

Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.

Shortcut: Visit every node once → O(n) time. Recursion depth = tree height → O(h) space.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Forgetting null/base-case handling

Wrong move: Recursive traversal assumes children always exist.

Usually fails on: Leaf nodes throw errors or create wrong depth/path values.

Fix: Handle null/base cases before recursive transitions.