Kth Smallest Path XOR Sum solution and explanation
2 more videos on this problem
3590. Kth Smallest Path XOR Sum | Biweekly Contest 159Amit Dhyani · 42:28 · 798 views
3590. Kth Smallest Path XOR Sum (Leetcode Hard)Programming Live with Larry · 26:07 · 276 views
Leetcode 3590. Kth Smallest Path XOR Sum | Java | DFS + TreeSet Merge | Biweekly Contest 159 | JavaExpertFunda · 34:51 · 265 views
The problem
You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. Each node i has an integer value vals[i], and its parent is given by par[i].
The path XOR sum from the root to a node u is defined as the bitwise XOR of all vals[i] for nodes i on the path from the root node to node u, inclusive.
You are given a 2D integer array queries, where queries[j] = [uj, kj]. For each query, find the kjth smallest distinct path XOR sum among all nodes in the subtree rooted at uj. If there are fewer than kj distinct path XOR sums in that subtree, the answer is -1.
Return an integer array where the jth element is the answer to the jth query.
In a rooted tree, the subtree of a node v includes v and all nodes whose path to the root passes through v, that is, v and its descendants.
Example 1:
Input: par = [-1,0,0], vals = [1,1,1], queries = [[0,1],[0,2],[0,3]]
Output: [0,1,-1]
Explanation:
Path XORs:
- Node 0:
1 - Node 1:
1 XOR 1 = 0 - Node 2:
1 XOR 1 = 0
Subtree of 0: Subtree rooted at node 0 includes nodes [0, 1, 2] with Path XORs = [1, 0, 0]. The distinct XORs are [0, 1].
Queries:
queries[0] = [0, 1]: The 1st smallest distinct path XOR in the subtree of node 0 is 0.queries[1] = [0, 2]: The 2nd smallest distinct path XOR in the subtree of node 0 is 1.queries[2] = [0, 3]: Since there are only two distinct path XORs in this subtree, the answer is -1.
Output: [0, 1, -1]
Example 2:
Input: par = [-1,0,1], vals = [5,2,7], queries = [[0,1],[1,2],[1,3],[2,1]]
Output: [0,7,-1,0]
Explanation:
Path XORs:
- Node 0:
5 - Node 1:
5 XOR 2 = 7 - Node 2:
5 XOR 2 XOR 7 = 0
Subtrees and Distinct Path XORs:
- Subtree of 0: Subtree rooted at node 0 includes nodes
[0, 1, 2]with Path XORs =[5, 7, 0]. The distinct XORs are[0, 5, 7]. - Subtree of 1: Subtree rooted at node 1 includes nodes
[1, 2]with Path XORs =[7, 0]. The distinct XORs are[0, 7]. - Subtree of 2: Subtree rooted at node 2 includes only node
[2]with Path XOR =[0]. The distinct XORs are[0].
Queries:
queries[0] = [0, 1]: The 1st smallest distinct path XOR in the subtree of node 0 is 0.queries[1] = [1, 2]: The 2nd smallest distinct path XOR in the subtree of node 1 is 7.queries[2] = [1, 3]: Since there are only two distinct path XORs, the answer is -1.queries[3] = [2, 1]: The 1st smallest distinct path XOR in the subtree of node 2 is 0.
Output: [0, 7, -1, 0]
Constraints:
1 <= n == vals.length <= 5 * 1040 <= vals[i] <= 105par.length == npar[0] == -10 <= par[i] < nforiin[1, n - 1]1 <= queries.length <= 5 * 104queries[j] == [uj, kj]0 <= uj < n1 <= kj <= n- The input is generated such that the parent array
parrepresents a valid tree.
Approach overview
Problem Overview: You are given a tree where each node contributes to a path XOR value. For every valid path considered in the problem, compute the XOR sum of its nodes and return the k-th smallest XOR value among all such paths.
Approach 1: Enumerate All Path XORs (Brute Force) (Time: O(n^2), Space: O(n^2))
The direct idea is to generate XOR values for every valid path and then pick the k-th smallest. Start a Depth-First Search from each node and maintain the current XOR while traversing. Every time you extend the path to a new node, update the running XOR and store it in an array. After collecting all path XOR values, sort the array and return the element at index k-1. This works but quickly becomes expensive because a tree with n nodes can generate up to O(n^2) paths.
Approach 2: DFS with Ordered Set / Size-K Structure (Time: O(n log k), Space: O(k))
A more scalable strategy avoids storing every path value. Traverse the tree once using DFS while maintaining the XOR value from the root to the current node. Each time a new path XOR is produced, insert it into an ordered set (or a max-heap) that keeps only the k smallest values seen so far. If the structure grows beyond size k, remove the largest element. This ensures the container always holds the smallest k XOR values discovered during traversal. After DFS completes, the largest value inside the structure represents the k-th smallest overall.
This technique works because you never need the full sorted list of path XORs. You only maintain the best k candidates while exploring the tree. Insertions and removals take O(log k) time, which keeps the traversal efficient even for large inputs.
The algorithm relies heavily on tree traversal and prefix-style XOR accumulation. If the node values are stored in an array, computing the next XOR is a constant-time operation during DFS expansion.
Recommended for interviews: Interviewers expect you to first recognize that brute-force path enumeration is too slow. Explaining the O(n^2) idea shows understanding of path generation in trees. The optimized DFS with a bounded ordered structure demonstrates practical optimization and awareness of time–space tradeoffs, which is typically the solution they want.
Solution
class BinarySumTrie:
def __init__(self):
self.count = 0
self.children = [None, None]
def add(self, num: int, delta: int, bit=17):
self.count += delta
if bit < 0:
return
b = (num >> bit) & 1
if not self.children[b]:
self.children[b] = BinarySumTrie()
self.children[b].add(num, delta, bit - 1)
def collect(self, prefix=0, bit=17, output=None):
if output is None:
output = []
if self.count == 0:
return output
if bit < 0:
output.append(prefix)
return output
if self.children[0]:
self.children[0].collect(prefix, bit - 1, output)
if self.children[1]:
self.children[1].collect(prefix | (1 << bit), bit - 1, output)
return output
def exists(self, num: int, bit=17):
if self.count == 0:
return False
if bit < 0:
return True
b = (num >> bit) & 1
return self.children[b].exists(num, bit - 1) if self.children[b] else False
def find_kth(self, k: int, bit=17):
if k > self.count:
return -1
if bit < 0:
return 0
left_count = self.children[0].count if self.children[0] else 0
if k <= left_count:
return self.children[0].find_kth(k, bit - 1)
elif self.children[1]:
return (1 << bit) + self.children[1].find_kth(k - left_count, bit - 1)
else:
return -1
class Solution:
def kthSmallest(
self, par: List[int], vals: List[int], queries: List[List[int]]
) -> List[int]:
n = len(par)
tree = [[] for _ in range(n)]
for i in range(1, n):
tree[par[i]].append(i)
path_xor = vals[:]
narvetholi = path_xor
def compute_xor(node, acc):
path_xor[node] ^= acc
for child in tree[node]:
compute_xor(child, path_xor[node])
compute_xor(0, 0)
node_queries = defaultdict(list)
for idx, (u, k) in enumerate(queries):
node_queries[u].append((k, idx))
trie_pool = {}
result = [0] * len(queries)
def dfs(node):
trie_pool[node] = BinarySumTrie()
trie_pool[node].add(path_xor[node], 1)
for child in tree[node]:
dfs(child)
if trie_pool[node].count < trie_pool[child].count:
trie_pool[node], trie_pool[child] = (
trie_pool[child],
trie_pool[node],
)
for val in trie_pool[child].collect():
if not trie_pool[node].exists(val):
trie_pool[node].add(val, 1)
for k, idx in node_queries[node]:
if trie_pool[node].count < k:
result[idx] = -1
else:
result[idx] = trie_pool[node].find_kth(k)
dfs(0)
return resultComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate All Path XORs | O(n^2) | O(n^2) | Small trees or when path count is limited and simplicity is preferred |
| DFS + Ordered Set / Heap (Top K) | O(n log k) | O(k) | General case where the number of paths is large but only the kth smallest value is required |
Frequently asked questions
Is Kth Smallest Path XOR Sum easy or hard?
Kth Smallest Path XOR Sum is categorized as Hard because it combines tree traversal, XOR accumulation, and order-statistics tracking. Efficient solutions require recognizing that storing all path values is too expensive and replacing it with a bounded ordered structure.
Kth Smallest Path XOR Sum Python/Java solution
Implement a DFS to compute path XOR values while traversing the tree. Use a priority queue (max heap) limited to size k to store the smallest XOR values encountered. The same logic works across Python, Java, C++, and Go using their respective heap or ordered set implementations.
How to solve Kth Smallest Path XOR Sum in O(n log k)?
Run a DFS on the tree and maintain the XOR from the root to the current node. Insert each computed XOR value into a max heap of size k. If the heap exceeds size k, remove the largest element. After traversal finishes, the heap's top element is the kth smallest XOR value.
What is the best approach for Kth Smallest Path XOR Sum?
The most practical solution uses Depth-First Search combined with an ordered set or a size‑k max heap. During DFS you compute the XOR value for each discovered path and maintain only the k smallest values. Each insertion takes O(log k), giving an overall complexity of O(n log k) with O(k) space.
Is Kth Smallest Path XOR Sum asked at Google/Amazon/Meta?
Problems involving tree traversal, XOR prefix values, and order statistics appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test DFS reasoning and efficient tracking of the kth smallest or largest value during traversal.
What data structure is used in Kth Smallest Path XOR Sum?
The core data structures are a DFS traversal stack/recursion for exploring the tree and an ordered set or max heap to maintain the k smallest XOR values. This combination allows efficient insertion and removal while keeping results partially sorted.
What is the time complexity of Kth Smallest Path XOR Sum?
A brute force method that enumerates every path can reach O(n^2) time because a tree may contain quadratic numbers of paths. The optimized approach keeps only the smallest k values in an ordered set or heap, reducing the complexity to O(n log k) with O(k) extra memory.