Number of Good Paths - Practice Coding Problems

Number of Good Paths - Problem

Array Hash Table Tree Union Find Graph Sorting Hard

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: 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.

Input & Output

Example 1 — Basic Tree Structure

$ Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]

› Output: 7

💡 Note: Good paths are: single nodes (5) + path 0→2→3 (nodes 0,3 both have value 1) + path 1→2→4 (nodes 1,4 both have value 3) = 5 + 1 + 1 = 7 total paths

Example 2 — All Same Values

$ Input: vals = [1,1,2,1,1], edges = [[0,1],[1,2],[2,3],[3,4]]

› Output: 10

💡 Note: Many good paths exist between nodes with value 1: all single nodes (5) + pairs of nodes with value 1 that can connect through node 2 (value 2) = 5 + 5 = 10 paths

Example 3 — Simple Path

$ Input: vals = [1], edges = []

› Output: 1

💡 Note: Single node forms a valid good path by itself

Constraints

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
The given edges represent a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with node values: [1,3,2,1,3]

Find Good Paths

Paths where endpoints have same value, intermediate ≤ endpoint

Count Paths

Single nodes (5) + valid pairs (2) = 7 total

Key Takeaway

🎯 Key Insight: Process nodes by ascending values to ensure path validity constraints

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to process nodes in ascending order of their values and use Union-Find to efficiently group connected components. Best approach is Union-Find with Sorting. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS for All Pairs	O(n³)	O(n)	For each pair of nodes with same value, check if a valid path exists using DFS
Union-Find with Sorting	O(n log n)	O(n)	Sort nodes by value and use Union-Find to efficiently count good paths

DFS for All Pairs — Algorithm Steps

Group nodes by their values
For each value, try all pairs of nodes with that value
Use DFS to check if valid path exists between each pair
Count all valid paths plus single nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Same Values

Group nodes by their values

Check Pairs

For each pair, use DFS to find valid path

Count Paths

Count all valid paths found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 30000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int vals[MAX_N];
int n;

bool dfs(int start, int end, int current, bool* visited, int maxVal) {
    if (current == end) {
        return true;
    }
    
    visited[current] = true;
    
    for (int i = 0; i < graphSize[current]; i++) {
        int neighbor = graph[current][i];
        if (!visited[neighbor] && vals[neighbor] <= maxVal) {
            if (dfs(start, end, neighbor, visited, maxVal)) {
                return true;
            }
        }
    }
    
    visited[current] = false;
    return false;
}

int solution(int* valsInput, int valsSize, int** edges, int edgesSize, int* edgesColSize) {
    n = valsSize;
    memcpy(vals, valsInput, sizeof(int) * n);
    memset(graphSize, 0, sizeof(graphSize));
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    int count = n; // Single node paths
    
    // Try all pairs of nodes
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (vals[i] == vals[j]) {
                bool visited[MAX_N] = {false};
                if (dfs(i, j, i, visited, vals[i])) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    // Simple parsing for demo purposes
    int valsInput[] = {1, 3, 2, 1, 3};
    int valsSize = 5;
    
    int edge0[] = {0, 1};
    int edge1[] = {0, 2};
    int edge2[] = {2, 3};
    int edge3[] = {2, 4};
    int* edges[] = {edge0, edge1, edge2, edge3};
    int edgesSize = 4;
    int edgesColSize[] = {2, 2, 2, 2};
    
    int result = solution(valsInput, valsSize, edges, edgesSize, edgesColSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of O(n²) node pairs, we perform O(n) DFS traversal

⚠ Quadratic Growth

Space Complexity

O(n)

DFS recursion stack and adjacency list storage

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS for All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler