Find the Maximum Sum of Node Values - Leetcode 3068 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
14:32 - Coding Explanation

leetcode 3068

#neetcode #leetcode #python

[ParodyCSEDept]

Thanks to you, my daily challenge streak is alive.

[amoghghadge]

Thank you for the consistent speedy solutions 🙌

[supremoluminary]

Wow. I couldn’t even make sense of the problem.

I like your walk-through and approach to these problems.

Most of these problems are not practical, useful, or relevant to front end engineering. But they are relevant to passing the interview. In 2009, I failed my google interview when I couldn’t solve “product of array except self“.

You don’t even need the edges array. Wow.

[MP-nyep]

Watched so many solutions. Yours was the only one that I understood.

[hkleiser]

you can take range(1, len(nums), 2): path_delta =delta[i-1] + delta[i], and the first if isn't needed

[KADOfficial]

other people videos were really confusing, you were straight to the point.. thanks!!

[PegasusKr]

I really liked the thought process you explained in this video. Thank you for the effort!

[grantpeterson]

A solution I found is O(n) time complexity and O(1) space. Basically, considering that each value is either "flipped" or "not flipped", and we need to ensure the number of "flips" we make is even (flipped in pairs of 2), that means that *at most* we will need to give up 1 of the larger values and instead take the smaller value to make it even (we can take ALL the larger values if the flips are even). Obviously, we'll want to flip back the value that has the smallest difference between being XORed vs not XORed. So, we go through the values, tracking these pieces of information: the total sum of all values (adding greedily whichever value is larger, XOR or not XOR), a boolean value `oddFlips` which starts as false and toggles every time we add an XOR value to the sum, and then absolute value of the smallest difference between the XOR and not XORed value. Then, at the end, if we have an odd number of flips, we just subtract that smallest difference to effectively "flip back" that node to remove the extra value it gave.

[abhinavkumar]

Speechless superb approach thank you so much

[supremoluminary]

The one nitpick I have with your code is the first break statement. instead, loop through len(nums) -1.

Thank you.

[NS-qoze]

Instead of sorting, we can keep track of sum_of_delta, count_of_delta, min_delta for delta >= 0, max_neg_delta for delta < 0. Now if count is even then answer is sum(nums)+sum_delta else we need to either remove the min delta or add a neg delta from delta < 0. answer looks something like this sum(nums)+sum_delta+ max(-min_delta, max_neg_delta). This will be O(n)

[swanv]

I find it difficult to convince myself that this works, but then sorting can be eliminated easily: count number of positive deltas; if you have even number of them then take all of them, otherwise take all but the min positive delta; then decide whether to include or discard min positive and max non-positive delta (if it exists) pair. So you need to track number of positive deltas, min positive delta and max non-positive delta values - no sorting required. This also eliminates need for delta[] array.

[slizverg]

I'm pretty sure that problem's description says that we can only peek two nodes that have EDGE between them, not a PATH. And you don't use "edges" array in your soltion. But your solutions works and that's what matters) Thanks!

[michael._.]

your approach and explanation for this question is absolutely superb, nailed it down

[IlaiShoshani]

Nice Problem, I wonder if a similar question where we xor and sum the actual values of the nodes (the indexes) rather than the numbers in the "nums" array would have a more efficient solution (because all the values are sorted from 0 to n-1).

Also, can't you get an O(n) solution easily by just doing XOR on all the values that will increase from it and saving the smallest difference caused by this action (or caused by not doing this action) in a variable, and if the final amount of XOR operations is odd subtracting that amount from the total sum?

[btrskts]

I just came up with O(2^n ) Solution .
But I was able to notice this XOR property .
Thanks NeetCode for your efforts.

[guruprasath]

Thanks Beats 100 % by time and Memory, if odd changes where made think of minimum impact value and take XOR on that value

count = 0
small_impact = None
for x in range(len(nums)):
if (nums[x] ^ k) > nums[x]:
nums[x] = nums[x] ^ k
count += 1
if small_impact is None:
small_impact = x
else:
if (nums[x] - (nums[x] ^ k)) < (nums[small_impact] - (nums[small_impact] ^ k)):
small_impact = x

if count%2 == 0:
return sum(nums)
else:
nums[small_impact] = nums[small_impact] ^ k
return sum(nums)

[Yogesh-D]

Bro your way of teaching and the way you solve the problems are really good 🔥

[hoyinli]

After I watched your second hint, this question became a piece of cake. Thx

[vikram--krishna]

Thanks for the simple and concise explanation, If possible can you share the O(n) approach which you mentioned existed for this problem?