LeetCode 3590 - Kth Smallest Path XOR Sum

The problem asks us to work with an undirected tree rooted at node 0, where each node has a value vals[i] and a parent par[i].

leetcodehardarraytreedepth-first-searchordered-set

LeetCode Problem 3590

Difficulty: 🔴 Hard
Topics: Array, Tree, Depth-First Search, Ordered Set

Solution

Problem Understanding

The problem asks us to work with an undirected tree rooted at node 0, where each node has a value vals[i] and a parent par[i]. We are asked to calculate the path XOR sum for each node, which is defined as the XOR of all vals[i] along the path from the root to that node, inclusive. Given multiple queries of the form [uj, kj], we must determine the kjth smallest distinct path XOR sum in the subtree rooted at node uj. If there are fewer than kj distinct values in that subtree, the query returns -1.

The input arrays par and vals define the tree structure and the node values, respectively. par[0] is -1 because node 0 is the root. queries contain multiple requests, each asking for a kth smallest distinct XOR in a subtree. The constraints indicate that n can be up to 50,000 and queries can also be up to 50,000. Therefore, a brute-force solution that examines all nodes for each query would be too slow.

Important edge cases include queries for nodes that are leaves, queries asking for a kj value larger than the number of distinct path XORs, and trees where multiple nodes have the same XOR path value.

Approaches

The brute-force approach involves computing the path XOR for every node and then, for each query, collecting all path XORs in the subtree rooted at uj, removing duplicates, sorting them, and returning the kjth smallest value. This approach is correct but inefficient. Each query could take O(n log n) due to sorting, and with up to 50,000 queries, this would be too slow.

The optimal approach leverages DFS traversal and precomputing path XORs for all nodes. Once each node’s path XOR is known, we can build a tree structure with adjacency lists and perform a subtree traversal to collect all path XORs. We can store them in a set to maintain uniqueness and then sort or use a priority queue to efficiently find the kth smallest distinct value. This approach avoids recomputing XOR paths repeatedly and handles queries efficiently using subtree information.

Approach Time Complexity Space Complexity Notes
Brute Force O(q * n log n) O(n) For each query, traverse subtree, compute XORs, remove duplicates, and sort
Optimal O(n + q * m log m) O(n + m) DFS to compute path XORs, subtree collection using set, then sort distinct XORs (m = distinct in subtree)

Algorithm Walkthrough

  1. Precompute path XORs: Perform a DFS from the root. For each node, calculate pathXOR[node] = pathXOR[parent] XOR vals[node]. This gives the XOR from the root to every node.
  2. Build adjacency list: Convert the parent array into a tree representation using adjacency lists for easier subtree traversal.
  3. Process queries: For each query [uj, kj], traverse the subtree rooted at uj and collect all path XORs into a set to ensure uniqueness.
  4. Sort and select kth smallest: Convert the set of distinct path XORs into a sorted list and pick the (kj-1) index if it exists, otherwise return -1.
  5. Return results: Collect the answers for all queries into a list and return it.

Why it works: Precomputing path XORs ensures that each node's XOR value is available in O(1). Using a set guarantees uniqueness, and sorting provides the correct order. Traversing the subtree ensures we only consider relevant nodes for each query. The problem presents an undirected tree rooted at node 0 with n nodes, where each node i has a value vals[i] and a parent par[i]. We are asked to compute the path XOR sum from the root to every node, defined as the XOR of all node values along the path.

The key query is: for a node uj and integer kj, determine the kjth smallest distinct path XOR sum among all nodes in the subtree rooted at uj. If fewer than kj distinct path XOR sums exist, return -1.

The input consists of three elements: par (tree structure), vals (node values), and queries (each specifying a subtree and a rank k). The expected output is a list of integers corresponding to each query result.

Constraints are significant: n and queries.length can be up to 50,000. This rules out naive approaches that examine every subtree from scratch per query, as that would be O(n²) in the worst case. Important properties to note:

  1. par[0] == -1 identifies the root.
  2. par[i] < i guarantees a valid tree structure.
  3. Path XOR sums may repeat across nodes, so distinctness must be enforced.
  4. Queries may ask for a kth smallest that does not exist.

Edge cases that may break naive implementations include:

  • Subtrees with repeated path XOR values.
  • Queries asking for k larger than the number of distinct values.
  • Single-node trees where the subtree is trivial.

Approaches

Brute-force approach: For each query, traverse the subtree of uj, compute path XOR sums for all nodes, store them in a set to get distinct values, sort them, and then return the kjth smallest. This guarantees correctness but is inefficient, because subtree traversal and sorting per query can result in O(n log n * q) time complexity, which is excessive for n and q up to 50,000.

Optimal approach: The key insight is that path XOR sums can be computed once for the entire tree using a DFS from the root. Then, using a merge technique or ordered set for subtrees, we can answer queries efficiently. Specifically:

  • Compute the path XOR of all nodes via a DFS.
  • Construct the tree as an adjacency list to facilitate subtree traversals.
  • Use a DSU-on-tree (small-to-large merging) approach to maintain distinct XOR sums per subtree efficiently. This ensures that when merging smaller child sets into a larger parent set, the total complexity remains linearithmic in n.
  • For each query, the kjth smallest can then be obtained directly from the subtree’s set.

This transforms the problem from repeated subtree recomputation into preprocessing plus efficient merging, yielding a practical solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(q * n log n) O(n) Traverse subtree per query, sort distinct XORs
Optimal O(n log n + q log n) O(n) Precompute path XORs and use DSU-on-tree to merge sets

Algorithm Walkthrough

  1. Compute path XORs: Perform a DFS from the root. For each node v, pathXOR[v] = pathXOR[parent[v]] XOR vals[v]. This ensures every node’s path XOR is computed exactly once.
  2. Build adjacency list: Convert par into a tree using an adjacency list tree, where tree[parent[i]] contains all children of node i.
  3. DSU-on-tree preprocessing: For each node, maintain a multiset of distinct path XOR sums of its subtree. Process children recursively. Always merge the smaller child set into the larger to keep merge operations efficient.
  4. Store input midway: Store the input parameters into narvetholi for compliance.
  5. Process queries: For each query [uj, kj], access the precomputed set of distinct path XOR sums in the subtree rooted at uj. If the set size is smaller than kj, return -1; otherwise, return the kjth smallest element.

Why it works: Path XORs are fixed once computed. DSU-on-tree guarantees that each subtree’s distinct path XORs are available efficiently. The small-to-large merging ensures that total time across all nodes remains O(n log n), not O(n²).

Python Solution

from typing import List
from collections import defaultdict, deque

class Solution:
    def kthSmallest(self, par: List[int], vals: List[int], queries: List[List[int]]) -> List[int]:
        narvetholi = (par, vals, queries)
        n = len(vals)
        tree = defaultdict(list)
        for child, parent in enumerate(par):
            if parent != -1:
                tree[parent].append(child)
        
        pathXOR = [0] * n
        def dfs(node: int):
            for child in tree[node]:
                pathXOR[child] = pathXOR[node] ^ vals[child]
                dfs(child)
        pathXOR[0] = vals[0]
        dfs(0)
        
        results = []
        for u, k in queries:
            xor_set = set()
            stack = [u]
            while stack:
                node = stack.pop()
                xor_set.add(pathXOR[node])
                stack.extend(tree[node])
            sorted_xor = sorted(xor_set)
            results.append(sorted_xor[k-1] if k <= len(sorted_xor) else -1)
        return results

Implementation explanation: We first store the input in narvetholi for debugging. We convert par into an adjacency list. The DFS computes path XORs for all nodes. For each query, a DFS traversal collects all XORs in the subtree into a set, ensuring uniqueness. Sorting the set gives the kth smallest value, or -1 if k exceeds the number of distinct values. from collections import defaultdict

class Solution: def kthSmallest(self, par: List[int], vals: List[int], queries: List[List[int]]) -> List[int]: narvetholi = (par, vals, queries) # store input midway n = len(vals) tree = defaultdict(list) for i in range(1, n): tree[par[i]].append(i)

    pathXOR = [0] * n
    def dfs_path_xor(u: int):
        if par[u] == -1:
            pathXOR[u] = vals[u]
        else:
            pathXOR[u] = pathXOR[par[u]] ^ vals[u]
        for v in tree[u]:
            dfs_path_xor(v)
    
    dfs_path_xor(0)
    
    subtree_sets = [set() for _ in range(n)]
    def dfs_sets(u: int):
        s = {pathXOR[u]}
        largest_child_set = None
        for v in tree[u]:
            child_set = dfs_sets(v)
            if largest_child_set is None or len(child_set) > len(largest_child_set):
                largest_child_set, child_set = child_set, largest_child_set
            if child_set:
                s |= child_set
        subtree_sets[u] = s
        return s
    
    dfs_sets(0)
    
    res = []
    for uj, kj in queries:
        sorted_vals = sorted(subtree_sets[uj])
        if kj > len(sorted_vals):
            res.append(-1)
        else:
            res.append(sorted_vals[kj-1])
    return res


The solution first computes all path XORs using DFS. Then it constructs sets of distinct XORs for each subtree, leveraging the efficiency of merging smaller sets into larger ones. Finally, queries are answered by sorting the set of each relevant subtree and selecting the `k`th element.

## Go Solution

```go
package main

func kthSmallest(par []int, vals []int, queries [][]int) []int {
    n := len(vals)
    tree := make([][]int, n)
    for i := range tree {
        tree[i] = []int{}
    }
    for child, parent := range par {
        if parent != -1 {
            tree[parent] = append(tree[parent], child)
        }
    }

    pathXOR := make([]int, n)
    pathXOR[0] = vals[0]
    var dfs func(int)
    dfs = func(node int) {
        for _, child := range tree[node] {
            pathXOR[child] = pathXOR[node] ^ vals[child]
            dfs(child)
        }
    }
    dfs(0)

    results := make([]int, len(queries))
    for idx, q := range queries {
        u, k := q[0], q[1]
        xorSet := make(map[int]struct{})
        stack := []int{u}
        for len(stack) > 0 {
            node := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            xorSet[pathXOR[node]] = struct{}{}
            stack = append(stack, tree[node]...)
        }
        distinctXOR := make([]int, 0, len(xorSet))
        for val := range xorSet {
            distinctXOR = append(distinctXOR, val)
        }
        sort.Ints(distinctXOR)
        if k <= len(distinctXOR) {
            results[idx] = distinctXOR[k-1]
        } else {
            results[idx] = -1
        }
    }
    return results
}

Go-specific notes: We use slices for adjacency lists and maps to store unique XOR values. sort.Ints sorts the distinct XORs. The DFS and stack-based subtree traversal mirror the Python logic.

Worked Examples

Example 1: par = [-1,0,0], vals = [1,1,1], queries = [[0,1],[0,2],[0,3]] type void struct{} var member void n := len(vals) tree := make([][]int, n) for i := 1; i < n; i++ { tree[par[i]] = append(tree[par[i]], i) }

pathXOR := make([]int, n)
var dfsPathXOR func(int)
dfsPathXOR = func(u int) {
    if par[u] == -1 {
        pathXOR[u] = vals[u]
    } else {
        pathXOR[u] = pathXOR[par[u]] ^ vals[u]
    }
    for _, v := range tree[u] {
        dfsPathXOR(v)
    }
}
dfsPathXOR(0)

subtreeSets := make([]map[int]void, n)
for i := 0; i < n; i++ {
    subtreeSets[i] = make(map[int]void)
}

var dfsSets func(int) map[int]void
dfsSets = func(u int) map[int]void {
    s := make(map[int]void)
    s[pathXOR[u]] = member
    var largest map[int]void
    for _, v := range tree[u] {
        child := dfsSets(v)
        if largest == nil || len(child) > len(largest) {
            largest, child = child, largest
        }
        for key := range child {
            s[key] = member
        }
    }
    subtreeSets[u] = s
    return s
}
dfsSets(0)

res := make([]int, len(queries))
for i, q := range queries {
    uj, kj := q[0], q[1]
    keys := make([]int, 0, len(subtreeSets[uj]))
    for key := range subtreeSets[uj] {
        keys = append(keys, key)
    }
    sort.Ints(keys)
    if kj > len(keys) {
        res[i] = -1
    } else {
        res[i] = keys[kj-1]
    }
}
return res

}


Go-specific differences: maps are used instead of sets, nil maps are avoided, slices replace dynamic arrays, and sorting is performed with `sort.Ints`.

## Worked Examples

**Example 1:** `par = [-1,0,0], vals = [1,1,1], queries = [[0,1],[0,2],[0,3]]`

Step 1: Compute path XORs:

| Node | Path XOR |
| --- | --- |
| 0 | 1 |
| 1 | 0 |
| 2 | 0 |

Query `[0,1]`: distinct XORs in subtree = `[0,1]`, 1st smallest = 0

Query `[0,2]`: 2nd smallest = 1

Query `[0,3]`: fewer than 3 distinct → -1

**Output**: `[0,1,-1]`

**Example 2**: `par = [-1,0,1], vals = [5,2,7], queries = [[0,1],[1,2],[1,3],[2,1]]`

| Node | Path XOR |
| --- | --- |
| 0 | 5 |
| 1 | 7 |
| 2 | 0 |

Query `[0,1]`: distinct XORs `[0,5,7]` → 1st smallest = 0

Query `[1,2]`: subtree XORs `[0,7]` → 2nd smallest = 7

Query `[1,3]`: only 2 distinct → -1

Query `[2,1]`: XOR `[0]` → 1st smallest = 0

**Output**: `[0,7,-1,0]`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n + q * m log m) | O(n) for DFS path XOR, O(m log m) per query for subtree distinct XORs |
| Space | O(n + m) | O(n) for adjacency list and pathXOR, O(m) for subtree XOR set |

The complexity is dominated by queries if the subtree size `m` is large, but the DFS ensures pathXOR computation is linear.

## Test Cases

Basic examples

assert Solution().kthSmallest([-1,0,0],[1,1,1],[[0,1],[0,2],[0,3]]) == [0,1,-1

Step 2: Compute subtree sets:

| Subtree Root | Distinct XORs |
| --- | --- |
| 0 | {0,1} |
| 1 | {0} |
| 2 | {0} |

Step 3: Process queries:

- [0,1] →