Find the Maximum Sum of Node Values solution and explanation
Google
9 more videos on this problem
Find the Maximum Sum of Node Values - Leetcode 3068 - PythonNeetCodeIO · 17:50 · 17K views
Find the Maximum Sum of Node Values | Two Approaches | Detailed | Leetcode 3068 | codestorywithMIKcodestorywithMIK · 45:48 · 13K views
3068. Find the Maximum Sum of Node Values | Bit Manipulation | Tree | GraphsAryan Mittal · 28:49 · 8K views
3068. Find the Maximum Sum of Node Values | Leetcode Biweekly 125codingMohan · 41:26 · 1K views
3068. Find the Maximum Sum of Node Values (Leetcode Hard)Programming Live with Larry · 23:13 · 599 views
Leetcode 3068 Find the Maximum Sum of Node ValuesJeevan Kumar - Cracckify · 10:16 · 592 views
3068. Find the Maximum Sum of Node Values | Bit Manipulation | Tree | GraphsComprehensive Code · 9:36 · 569 views
LeetCode 3068 - Find the Maximum Sum of Node Values - JavaAlpha-Code · 12:14 · 199 views
3068. Find the Maximum Sum of Node Values | Leetcode Daily - PythonLeetcode Daily · 10:14 · 160 views
LeetCode 3068 - Find the Maximum Sum of Node Values - JavaAlpha-Code · 22:18 · 106 views
The problem
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree. You are also given a positive integer k, and a 0-indexed array of non-negative integers nums of length n, where nums[i] represents the value of the node numbered i.
Alice wants the sum of values of tree nodes to be maximum, for which Alice can perform the following operation any number of times (including zero) on the tree:
- Choose any edge
[u, v]connecting the nodesuandv, and update their values as follows:nums[u] = nums[u] XOR knums[v] = nums[v] XOR k
Return the maximum possible sum of the values Alice can achieve by performing the operation any number of times.
Example 1:
Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]] Output: 6 Explanation: Alice can achieve the maximum sum of 6 using a single operation: - Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2]. The total sum of values is 2 + 2 + 2 = 6. It can be shown that 6 is the maximum achievable sum of values.
Example 2:
Input: nums = [2,3], k = 7, edges = [[0,1]] Output: 9 Explanation: Alice can achieve the maximum sum of 9 using a single operation: - Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4]. The total sum of values is 5 + 4 = 9. It can be shown that 9 is the maximum achievable sum of values.
Example 3:
Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]] Output: 42 Explanation: The maximum achievable sum is 42 which can be achieved by Alice performing no operations.
Constraints:
2 <= n == nums.length <= 2 * 1041 <= k <= 1090 <= nums[i] <= 109edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1- The input is generated such that
edgesrepresent a valid tree.
Approach overview
Problem Overview: You are given a tree where each node has a value. An operation selects an edge and XORs both endpoint values with k. Perform any number of operations to maximize the total sum of node values. The key constraint is that every operation affects two nodes simultaneously.
Approach 1: Brute Force Edge Operation Simulation (Exponential Time)
The most direct way is to try every possible combination of XOR operations on edges. Each operation flips two node values using value ^ k, so different sequences of operations produce different states. A brute-force solution explores these states recursively or via bitmask simulation and computes the resulting sum for each configuration. The state space grows exponentially because each edge can be toggled multiple times. This leads to roughly O(2^n) time in the worst case with O(n) space for recursion or state tracking. It demonstrates the operation behavior but becomes infeasible for large trees.
Approach 2: Greedy Gain Selection with Parity Constraint (O(n) time)
The key observation: applying the XOR operation on edges effectively toggles node values in pairs. That means the number of nodes whose value changes must always be even. For each node, compute the gain if XOR is applied: gain = (nums[i] ^ k) - nums[i]. This transforms the problem into choosing a subset of nodes to flip such that the total gain is maximized while the number of chosen nodes remains even.
Iterate through the array and add all positive gains because they increase the total sum. Track the count of chosen nodes and also keep the smallest absolute gain difference. If the count of positive gains is even, the result is simply the base sum plus all positive gains. If the count is odd, adjust by either removing the smallest positive gain or including the least harmful negative gain. This greedy evaluation works because each node decision is independent except for the global even-parity constraint.
The algorithm runs in O(n) time and O(1) extra space while scanning the array once. Although the input includes a tree, the structure does not affect the final decision because any pair of nodes can effectively be toggled through edge operations. The reasoning combines bit manipulation (using XOR) with a parity-style dynamic programming insight.
Recommended for interviews: The greedy parity approach is what interviewers expect. It shows you recognized the hidden constraint that operations affect nodes in pairs and converted the tree problem into a gain-selection problem. Mentioning the brute-force idea first demonstrates understanding of the operation mechanics, while deriving the O(n) greedy solution shows strong problem-solving skills.
Approach 1: Brute Force Approach
This approach involves checking all possible operations on each edge and calculating the resulting sum by applying the XOR operation. We must continuously update and evaluate for every operation on each pair of nodes linked by an edge to see if the resulting sum after the operation is beneficial.
This naive strategy will consider 2^n operations (since each edge can have 2 XOR states per pair), making it inefficient for larger datasets. Ideal for understanding XOR effects but not recommended for large n.
def getMaxSum(nums, k, edges):
sum_val = sum(nums)
max_sum = sum_val
for u, v in edges:
new_sum = sum_val - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k))
max_sum = max(max_sum, new_sum)
return max_sum
nums = [1, 2, 1]
k = 3
edges = [[0, 1], [0, 2]]
print(getMaxSum(nums, k, edges))import java.util.List;
public class Solution {
public static int getMaxSum(int[] nums, int k, int[][] edges) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int maxSum = sum;
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
int newSum = sum - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k));
maxSum = Math.max(maxSum, newSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1};
int k = 3;
int[][] edges = {{0, 1}, {0, 2}};
System.out.println(getMaxSum(nums, k, edges));
}
}#include <iostream>
#include <vector>
using namespace std;
int getMaxSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxSum = sum;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
int newSum = sum - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k));
maxSum = max(maxSum, newSum);
}
return maxSum;
}
int main() {
vector<int> nums = {1, 2, 1};
int k = 3;
vector<vector<int>> edges = {{0, 1}, {0, 2}};
cout << getMaxSum(nums, k, edges) << endl;
return 0;
}function getMaxSum(nums, k, edges) {
let sum = nums.reduce((a, b) => a + b, 0);
let maxSum = sum;
edges.forEach(([u, v]) => {
let newSum = sum - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k));
if (newSum > maxSum) {
maxSum = newSum;
}
});
return maxSum;
}
const nums = [1, 2, 1];
const k = 3;
const edges = [[0, 1], [0, 2]];
console.log(getMaxSum(nums, k, edges));#include <stdio.h>
int getMaxSum(int* nums, int numsSize, int k, int edges[][2], int edgesSize) {
int sum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0], v = edges[i][1];
int newSum = sum - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k));
if (newSum > maxSum) {
maxSum = newSum;
}
}
return maxSum;
}
int main() {
int nums[] = {1, 2, 1};
int k = 3;
int edges[2][2] = {{0, 1}, {0, 2}};
int result = getMaxSum(nums, 3, k, edges, 2);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int GetMaxSum(int[] nums, int k, int[][] edges) {
int sum = 0;
foreach (int num in nums) {
sum += num;
}
int maxSum = sum;
foreach (int[] edge in edges) {
int u = edge[0], v = edge[1];
int newSum = sum - (nums[u] + nums[v]) + ((nums[u] ^ k) + (nums[v] ^ k));
if (newSum > maxSum) {
maxSum = newSum;
}
}
return maxSum;
}
public static void Main() {
int[] nums = {1, 2, 1};
int k = 3;
int[][] edges = new int[][] { new int[] {0, 1}, new int[] {0, 2} };
Console.WriteLine(GetMaxSum(nums, k, edges));
}
}This Python solution follows the same pattern of evaluating each edge and attempting an XOR operation, checking for the highest achievable sum.
Time Complexity: O(n), as each pairwise evaluation takes constant time.
Space Complexity: O(1), requires only a few variables beyond input data.
Approach 2: Optimized Evaluation
Instead of brute checking each edge operation individually, observe that XOR operation symmetry allows flipping of node values to be optimal only when advantageous. Analyze and preprocess which nodes when XOR'd with k will increase their value and prioritize these changes globally without redundant individual edge checks.
This idea is crucially about observing which nodes independently contribute more value when toggled and using the tree structure to apply XOR operations optimally.
def getMaxSumOptimized(nums, k):
sum_val = sum(nums)
xor_sum = sum(num ^ k for num in nums)
return max(sum_val, xor_sum)
nums = [1, 2, 1]
k = 3
print(getMaxSumOptimized(nums, k))public class Solution {
public static int getMaxSumOptimized(int[] nums, int k) {
int sum = 0, xor_sum = 0;
for (int num : nums) {
sum += num;
xor_sum += (num ^ k);
}
return Math.max(sum, xor_sum);
}
public static void main(String[] args) {
int[] nums = {1, 2, 1};
int k = 3;
System.out.println(getMaxSumOptimized(nums, k));
}
}#include <iostream>
#include <vector>
int getMaxSumOptimized(std::vector<int>& nums, int k) {
int sum = 0, xor_sum = 0;
for (int num : nums) {
sum += num;
xor_sum += (num ^ k);
}
return std::max(sum, xor_sum);
}
int main() {
std::vector<int> nums = {1, 2, 1};
int k = 3;
std::cout << getMaxSumOptimized(nums, k) << std::endl;
return 0;
}function getMaxSumOptimized(nums, k) {
let sum = nums.reduce((a, b) => a + b, 0);
let xorSum = nums.reduce((a, b) => a + (b ^ k), 0);
return Math.max(sum, xorSum);
}
const nums = [1, 2, 1];
const k = 3;
console.log(getMaxSumOptimized(nums, k));#include <stdio.h>
#include <stdlib.h>
int getMaxSumOptimized(int* nums, int numsSize, int k) {
int sum = 0, xor_sum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += nums[i];
xor_sum += (nums[i] ^ k);
}
return (sum > xor_sum) ? sum : xor_sum;
}
int main() {
int nums[] = {1, 2, 1};
int k = 3;
int result = getMaxSumOptimized(nums, 3, k);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int GetMaxSumOptimized(int[] nums, int k) {
int sum = 0, xor_sum = 0;
foreach (var num in nums) {
sum += num;
xor_sum += (num ^ k);
}
return Math.Max(sum, xor_sum);
}
public static void Main() {
int[] nums = {1, 2, 1};
int k = 3;
Console.WriteLine(GetMaxSumOptimized(nums, k));
}
}The Python approach aligns with other languages; succinctly tabulating whether summing XOR-tweaked values improves upon their original combined total.
Time Complexity: O(n), iterates nums once.
Space Complexity: O(1), uses trivial extra space.
Approach 3: Dynamic Programming
For any number x, its value remains unchanged after being XORed with k an even number of times. Therefore, for any path in a tree, if we perform the operation on all edges in the path, the values of all nodes on the path except the start and end nodes will not change.
Additionally, no matter how many operations are performed, there will always be an even number of elements XORed with k, and the remaining elements will remain unchanged.
Thus, the problem is transformed into: for the array nums, select an even number of elements to XOR with k to maximize the sum.
We can use dynamic programming to solve this problem. Let f_0 represent the maximum sum when an even number of elements have been XORed with k, and f_1 represent the maximum sum when an odd number of elements have been XORed with k. The state transition equations are:
$
\begin{aligned}
f_0 &= max(f_0 + x, f_1 + (x \oplus k)) \
f_1 &= max(f_1 + x, f_0 + (x \oplus k))
\end{aligned}
where x represents the current element's value.
We traverse the array nums and update f_0 and f_1 according to the above state transition equations. Finally, we return f_0.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
function maximumValueSum(nums: number[], k: number, edges: number[][]): number {
let [f0, f1] = [0, -Infinity];
for (const x of nums) {
[f0, f1] = [Math.max(f0 + x, f1 + (x ^ k)), Math.max(f1 + x, f0 + (x ^ k))];
}
return f0;
}func maximumValueSum(nums []int, k int, edges [][]int) int64 {
f0, f1 := 0, -0x3f3f3f3f
for _, x := range nums {
f0, f1 = max(f0+x, f1+(x^k)), max(f1+x, f0+(x^k))
}
return int64(f0)
}impl Solution {
pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
let mut f0: i64 = 0;
let mut f1: i64 = i64::MIN;
for &x in &nums {
let tmp = f0;
f0 = std::cmp::max(f0 + x as i64, f1 + (x ^ k) as i64);
f1 = std::cmp::max(f1 + x as i64, tmp + (x ^ k) as i64);
}
f0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n), as each pairwise evaluation takes constant time. |
| Optimized Evaluation | Time Complexity: O(n), iterates nums once. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Edge Simulation | O(2^n) | O(n) | Conceptual understanding of how edge XOR operations affect node states |
| Greedy Gain Selection with Parity Constraint | O(n) | O(1) | Optimal solution for large inputs; handles the even-toggle constraint efficiently |
Frequently asked questions
Is Find the Maximum Sum of Node Values easy or hard?
The problem is rated Hard because the tree structure can mislead you into thinking complex traversal or dynamic programming is required. The real challenge is recognizing that XOR operations affect nodes in pairs, creating an even-parity constraint that leads to a greedy O(n) solution.
Find the Maximum Sum of Node Values Python/Java solution
Python and Java implementations follow the same logic: compute the base sum, calculate gain = (nums[i] ^ k) - nums[i], accumulate positive gains, and track the minimum absolute gain adjustment. The algorithm uses a single loop and constant extra memory, giving O(n) time complexity.
How to solve Find the Maximum Sum of Node Values in O(n)?
Compute the base sum of all node values. For each node, calculate the gain from applying XOR with k. Add every positive gain while counting how many nodes are flipped. If the count is even, keep the sum. If the count is odd, subtract the smallest absolute gain difference to restore even parity. This single pass achieves O(n) time.
What is the best approach for Find the Maximum Sum of Node Values?
The optimal approach uses a greedy gain calculation with an even-parity constraint. Compute the gain for flipping each node using (nums[i] ^ k) - nums[i], add all positive gains, and ensure the number of flipped nodes is even. If it becomes odd, adjust by removing the smallest positive gain or adding the least negative gain. This runs in O(n) time and O(1) space.
Is Find the Maximum Sum of Node Values asked at Google/Amazon/Meta?
Problems combining XOR operations, greedy selection, and tree reasoning frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether candidates recognize parity constraints or convert structural problems into simpler array optimizations.
What data structure is used in Find the Maximum Sum of Node Values?
The main data structure is a simple array storing node values. The tree structure is provided through edges but does not require traversal in the optimal solution. The logic focuses on XOR bit manipulation and greedy gain selection rather than traditional tree traversal.
What is the time complexity of Find the Maximum Sum of Node Values?
The optimal solution runs in O(n) time because it scans the node values once to compute XOR gains and track parity adjustments. Space complexity is O(1) since only a few variables are required. Brute-force approaches that simulate operations can grow exponentially and are not practical for large inputs.