Find the Maximum Sum of Node Values - Leetcode 3068 - Python
Vložit
- čas přidán 9. 06. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-th...
0:00 - Read the problem
0:30 - Drawing Explanation
14:32 - Coding Explanation
leetcode 3068
#neetcode #leetcode #python
Thanks to you, my daily challenge streak is alive.
Thank you for the consistent speedy solutions 🙌
Watched so many solutions. Yours was the only one that I understood.
other people videos were really confusing, you were straight to the point.. thanks!!
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.
your approach and explanation for this question is absolutely superb, nailed it down
love your videos mann!!! you make them look so easy. thank you!!
Brilliant explanation!
I really liked the thought process you explained in this video. Thank you for the effort!
Great explanation as always. Thanks for your efforts
yeah you helped me solve the problem by giving hints. Thanks :)
Brilliant! Save my day!
You are the best, hands down 🙌
Nice approach 🎉
After I watched your second hint, this question became a piece of cake. Thx
Bro you are great!
Bro your way of teaching and the way you solve the problems are really good 🔥
man you make hard problems easy!
you can take range(1, len(nums), 2): path_delta =delta[i-1] + delta[i], and the first if isn't needed
beautiful problem
Thanks for the simple and concise explanation, If possible can you share the O(n) approach which you mentioned existed for this problem?
My mentor!
The one nitpick I have with your code is the first break statement. instead, loop through len(nums) -1.
Thank you.
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.
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?
brilliant
thank you :-)
Gah, I was so close to figuring this out on my own. Thank you so much for the explanation, it saved me many hours of banging my head against the wall!
Neetcode saved me from unemployment
Wow you work at amazon
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.
No that won't work because lets say my delta values are like [6, 4, 3, -1]. Based on your logic if I have to count only positive values and add it up it'll be 6 + 4 + 3 = 13 and since number of +ve delta values is odd, we deduct 3 (the minimum value) from it and hence the answer will be 13 -3 = 10. However, if I were to consider 3, -1 as well, then the new result would be 6 + 4 + 3 + -1 = 12. 12 > 10
Hence we need to check upon the pair sum values and then do it.
@@ruthviks No, he is correct, what he meant by keeping track of max non-positive delta is that he will keep a track of a sum of postives, a maximum negative delta and minimum positive delta, after running through array in O(n) and O(1) memory.
In your example: [6, 4, 3, -1], after going through array he has:
- maximum negative is: -1
- minimum positive is: 3
- count of 3 positive deltas with sum 6 + 4 + 3 = 13
Steps are:
- deduct minimum_positive (because we have an odd count of positives) -> 13 - 3= 10
- decide whether we should add (minimum_positive + maximum_negative), we might be adding minimum_positive back but with maximum negative so that the added sum is maximal
-> (3 + -1) = 2, It's positive so we add it to total -> 10 + 2 = 12
@@jankes433 Yes this can be done. I didn't think of the part where we can keep track of the negative as well. Thanks for the perspective!!
Nice explanation. It's really strange that this problem can be found without using the edges argument.
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)
If anyone wants to see a step by step walk-through, you can check out approach 4 in the editorial of this question
I don't think you need to store the count and delta, you can just store the sum and a variable "min_delta" that stores the minimum difference to the sum between doing a xor operation on a certain node or not, it includes the negative delta inside of it. Am I missing something?
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!
He explains why. Mathematically/geometrically if it is a tree (connected) then every edge is a part of a path. That’s what the problem kind of confuses you with. So you don’t really need to care about the edges, the fact that every node has a path to every other one because it’s a tree means you can do some combination of XOR that will edit just that node and one other node. It just has to be a total of 2 nodes that XOR
@@SunsetofMana yep, probably missed that in the video. Now I get it, thanks)
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)
nice thinking. here's a shorter code.
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
odd, impact = 0, float('inf')
for i, n in enumerate(nums):
xored = n ^ k
if xored > n:
nums[i] = xored
odd += 1
impact = min(impact, nums[i] - (nums[i] ^ k))
return sum(nums)-impact if odd % 2 != 0 else sum(nums)
you can iterate till len(nums) - 1, instead of writing this if and break in the for loop
i have little bit confusion in the for loop why we can iterate through step if we do normally add the elements we get maximum that this and i experience this
nums =
[24,78,1,97,44]
k =
6
edges =
[[0,2],[1,2],[4,2],[3,4]]
Use Testcase
Output
262
Expected
260
could you explain this why we put for loop like this....
Hey,
I was wondering if someone could explain the expected value for the following test case?
nums = [78,43,92,97,95,94], k= 6 and edges = [[1,2],[3,0],[4,0],[0,1],[1,5]]
I am getting the value as 499, as no edges can be selected to increase the sum of values in nums post operations.
I just came up with O(2^n ) Solution .
But I was able to notice this XOR property .
Thanks NeetCode for your efforts.
Please explain leetcode 3143 - asked in contest
You deserve more reach❤ but kindly slow down a bit😅
O(n) solution, XOR all the numbers that needs to be XOR'ed to increase the total value, if we XOR'ed even times, all is good and we can return sum of all the numbers. If we XOR'ed odd times, we need to XOR one number back to its lower value. So we XOR the number which has the smallest delta (absolute difference) with its XOR'ed value, then update the result accordingly.
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
bad = 0 # no.of bad nodes. bad nodes == nodes who should be XOR'ed to increase its value
res = 0
smallest_diff = [float('inf'),None] # [ diff, index ] to keep track of which node has the smallest delta
for i,n in enumerate(nums):
diff = (n^k) - n
if smallest_diff[0] > abs(diff):
smallest_diff = [abs(diff),i]
if diff > 0:
nums[i] = n^k
bad += 1
res += nums[i]
if bad%2: # if odd no.of bad nodes, we must leave 1 bad node. if even, we can convert all to good nodes
res = res - nums[smallest_diff[1]] + (nums[smallest_diff[1]]^k)
return res
12:03 that looks more like amongus
I simply used a heap to achieve a time complexity of O(n) although my solution was slower than yours XD
At 12.45 mark, why are we picking 2 values at a time? Any logic behind that?
pretty much what i explained about how instead of choosing edges in this problem, we are choosing a path between two nodes. we must include both of those nodes, i.e. we have to choose 2 nodes at a time. its impossible to only XOR a single node.
@@NeetCodeIO yes sir. But let’s say array looks like [ 9,6,2,-8]
The first 2 nodes may not be adjacent?
But because in between for all other nodes due to double XOR won’t change value I guess.
@@StellasAdi18 You may like to re view the video. Adjacency is not a question when we know having path is sufficient.
First🎉🎉
🥇
You didn't even use the edge parameter at all. Could that have been useful to make the approach more efficient?
edges array be like : Am i a joke to you ??? 😡 after left unused in the nlogn solution. 😅
I couldn't solve anything for this problem. But at least I did the O(n) solution:
solution in rust
impl Solution {
pub fn maximum_value_sum(nums: Vec, k: i32, _edges: Vec) -> i64 {
let mut sum = 0;
let mut max_negative = i32::MIN;
let mut min_positive = i32::MAX;
let mut count_positives = 0;
for num in nums {
let delta = (num ^ k) - num;
if delta.is_positive() {
count_positives += 1;
min_positive = min_positive.min(delta);
} else {
max_negative = max_negative.max(delta);
}
sum += if delta.is_positive() {
num + delta
} else {
num
} as i64;
}
if count_positives % 2 != 0 {
if min_positive + max_negative > 0 {
sum += max_negative as i64;
} else {
sum -= min_positive as i64;
}
}
sum
}
}
They said not to do it twice! Say wht? Screw it