Longest Special Path II - Practice Coding Problems

Longest Special Path II - Problem

Array Hash Table Tree Depth-First Search Prefix Sum Hard

You're exploring a tree structure where each node has a unique value. Your mission is to find the longest special path - a downward journey from any ancestor to its descendant with an interesting twist!

Given an undirected tree rooted at node 0 with n nodes (numbered 0 to n-1), represented by edges and node values, you need to find special paths where:

All node values are distinct, OR
At most one value appears exactly twice

Input:

edges: 2D array where edges[i] = [u_i, v_i, length_i] represents an edge between nodes u_i and v_i with given length
nums: Array where nums[i] is the value at node i

Output: Return [maxLength, minNodes] where:

maxLength: Length of the longest special path
minNodes: Minimum number of nodes among all longest special paths

Input & Output

example_1.py — Basic Tree

$ Input: edges = [[0,1,5], [1,2,3]], nums = [1,2,1]

› Output: [8, 3]

💡 Note: The longest special path is 0→1→2 with values [1,2,1]. Since value 1 appears twice (allowed), this path has length 5+3=8 and uses 3 nodes.

example_2.py — Complex Tree

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

› Output: [6, 3]

💡 Note: The longest special path is 0→1→3 with values [1,1,3]. The first duplicate is allowed, giving length 2+4=6 with 3 nodes. Path 0→2 has length 3 but only 2 nodes.

example_3.py — Single Node

$ Input: edges = [], nums = [5]

› Output: [0, 1]

💡 Note: With only one node, the longest path has length 0 (no edges) and uses 1 node.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i] = [u_i, v_i, length_i]
0 ≤ u_i, v_i < n
1 ≤ length_i ≤ 10⁹
1 ≤ nums[i] ≤ 10⁵
The graph forms a valid tree

Visualization

Tap to expand

Understanding the Visualization

Build Trail Map

Create adjacency list representation of the tree structure

Start Exploration

Begin DFS from each possible starting checkpoint

Track Landmarks

Maintain frequency count of landmarks seen on current trail

Handle Duplicates

Allow exactly one landmark to be seen twice during exploration

Record Best Trail

Update maximum trail length and minimum checkpoints used

Key Takeaway

🎯 Key Insight: Use DFS with frequency tracking to efficiently explore all paths while respecting the 'at most one duplicate' constraint through smart backtracking.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

The optimal approach uses DFS with frequency tracking to explore all possible paths efficiently. Key insights: maintain a frequency map during traversal, allow at most one duplicate value per path, and use proper backtracking to restore state. Time complexity: O(n²), Space complexity: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Paths)	O(n³)	O(n²)	Try every possible downward path and check if it's special
DFS with Frequency Tracking (Optimal)	O(n²)	O(n)	Single DFS traversal with smart frequency tracking and backtracking

Brute Force (Try All Paths) — Algorithm Steps

Build adjacency list from edges
For each node, start DFS to explore all downward paths
For each path, track value frequencies using a hash map
Check if path is special (≤1 value appears twice)
Track maximum path length and minimum nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from Node

Begin DFS from each node as potential starting point

Explore Paths

For each starting node, explore all possible downward paths

Track Frequencies

Maintain frequency map of node values along current path

Validate Path

Check if current path is special (≤1 duplicate value)

Update Results

Update maximum length and minimum nodes if better path found

Code -

solution.c — C

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

#define MAX_NODES 1000

typedef struct {
    int neighbor;
    int length;
} Edge;

typedef struct {
    Edge edges[MAX_NODES];
    int count;
} AdjList;

int maxLength = 0;
int minNodes = INT_MAX;

void dfs(AdjList graph[], int nums[], int n, int node, int parent, 
         int pathLength, int nodeCount, int freqMap[], int maxVal) {
    // Count duplicates
    int duplicates = 0;
    for (int i = 0; i <= maxVal; i++) {
        if (freqMap[i] == 2) duplicates++;
    }
    
    // Check if current path is special
    if (duplicates <= 1) {
        if (pathLength > maxLength) {
            maxLength = pathLength;
            minNodes = nodeCount;
        } else if (pathLength == maxLength) {
            if (nodeCount < minNodes) {
                minNodes = nodeCount;
            }
        }
    }
    
    // Continue DFS to children
    for (int i = 0; i < graph[node].count; i++) {
        int neighbor = graph[node].edges[i].neighbor;
        int edgeLength = graph[node].edges[i].length;
        
        if (neighbor != parent) {
            freqMap[nums[neighbor]]++;
            dfs(graph, nums, n, neighbor, node, pathLength + edgeLength, nodeCount + 1, freqMap, maxVal);
            // Backtrack
            freqMap[nums[neighbor]]--;
        }
    }
}

int* longestSpecialPath(int** edges, int edgesSize, int* edgesColSize, int* nums, int numsSize, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    AdjList graph[MAX_NODES];
    for (int i = 0; i < numsSize; i++) {
        graph[i].count = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1], length = edges[i][2];
        graph[u].edges[graph[u].count++] = (Edge){v, length};
        graph[v].edges[graph[v].count++] = (Edge){u, length};
    }
    
    // Find max value for frequency array size
    int maxVal = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    
    int* freqMap = (int*)calloc(maxVal + 1, sizeof(int));
    
    // Try starting from each node
    for (int start = 0; start < numsSize; start++) {
        memset(freqMap, 0, (maxVal + 1) * sizeof(int));
        freqMap[nums[start]] = 1;
        dfs(graph, nums, numsSize, start, -1, 0, 1, freqMap, maxVal);
    }
    
    result[0] = maxLength;
    result[1] = minNodes == INT_MAX ? 1 : minNodes;
    
    free(freqMap);
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n nodes, we explore up to n paths, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n²)

Recursion stack and frequency maps for each path exploration

⚠ Quadratic Space

32.4K Views

Medium-High Frequency

~25 min Avg. Time

1.2K 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

Brute Force (Try All Paths) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler