Find the Maximum Sum of Node Values | Two Approaches | Detailed | Leetcode 3068 | codestorywithMIK

This is the 33rd Video of our Playlist "Greedy : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a good Greedy problem : Find the Maximum Sum of Node Values | Greedy | Two Approaches | Detailed | Leetcode 3068 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Find the Maximum Sum of Node Values | Greedy | Two Approaches | Detailed | Leetcode 3068 | codestorywithMIK
Company Tags : Google

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
**Approach-1 (Greedily picking nodes to XOR)**:
This approach iterates through the given list of numbers. For each number, it calculates the XOR value with a given constant 'k'. If the XOR value is greater than the original number, it adds this XOR value to the sum, otherwise, it adds the original number. Additionally, it keeps track of the minimum difference between each number and its XOR value. After iterating through all numbers, if the count of numbers with XOR values greater than themselves is even, it returns the sum. Otherwise, it subtracts the minimum difference from the sum before returning it.

**Time Complexity (T.C)**: O(n)
**Space Complexity (S.C)**: O(1)

**Approach-2 (Greedy + Sorting)**:
This approach also iterates through the given list of numbers. For each number, it calculates the potential gain (fayda) by XORing it with the given constant 'k' and subtracting the original number. It sums up the original numbers. Then, it sorts the potential gain values in descending order. It iterates through the sorted potential gain values in pairs and adds the sum of positive pairs to the original sum.

**Time Complexity (T.C)**: O(nlogn)
**Space Complexity (S.C)**: O(n)

✨ Timelines✨
00:00 - Introduction
00:16 - Problem Explanation
4:16 - Approach-1 Intuition
32:15 - Coding Approach-1
35:17 - Approach-2 Intuition
43:25 - Coding Approach-2

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[codestorywithMIK]

Hi everyone, so sorry i missed to explain a case which was crucial to Approach-1 . Thanks to all of you for such a keen observation and who commented about it ❤❤❤

The Case that I missed to explain is when we don’t xor any element . For example : [1, 7, 7] k=3,
If you notice, 7 reduces to 4 when xored with 3. So we only xor 1 and one of the 7.

As per the explanation if we do check minNuksaan in else condition then minNuksaan = 7-4 = 3.
So we think that result will be 16-3 = 13 which is not correct.
The better answer will be 1 + 7 + 7 = 15 (we don’t xor anyone)

Now, we can either check in the end that sum of all nodes is greater than our sum then, we return the sum of nodes’ original values.

[codestorywithMIK]

✨ Timelines✨
00:00 - Introduction
00:16 - Problem Explanation
4:16 - Approach-1 Intuition
32:15 - Coding Approach-1
35:17 - Approach-2 Intuition
43:25 - Coding Approach-2

[kondkartauqeer]

can you provide solution of contests questions when there is a POTD and you have already made the video solution to that POTD before

[Strawcontamination]

i had confusion for the test case nums={1, 1, 1}, k=3
but after dry running it worked for that too
as i thought nuksaan wouldnt get updated
but it did.
thank you for the video!!!

[CSERITIKSINGH]

Bhaiya aap se accha koi bhi nhi samjhata YouTube par kitna bhi hard questions ho aap se bahut easily samajh me aa jata hai thanks a lot bhaiya for providing so good videos 🙏

[JoyBoy_]

Such a detailed Explanation ! Thanks a lot brother .

[EB-otuu]

and congratulations on 48K.
Waiting for your video on 50K that you had promised us.

[learn_in_shorts]

Bhaiya 1st approach acha tha and samjh mey bhi aaya code apne se kiya explanation dekh kar but 2nd wala toha lengthy hai to mey usse nahi kiya😊

[RohitKumar-dzdh]

Thanks for your beautiful explanation 😊.

[DakshDua-bvdz]

You made this hard question easy fr us

[gauravbanerjee]

Thanks a lot bhaiya ❤❤ Congrats for 48k subs🥳🥳

[AjeetKumar-ttjr]

streak 448 days, really inspiring hats off 🔥🔥🔥🔥🔥🔥🔥🔥

[gui-codes]

Was waiting for your video only. finally it's here 🤩
And thank you so much, I was able to solve 3 qns in today's contest

[heenamittal]

Thanks a lot for the explaination, just had one doubt, why is minLoss in first approach not inside the else condition(as we need to calculate loss only when xored result is less than the number), when I add it in the else condition, this test case fails --> [67, 13, 79, 13, 75, 11, 0, 41, 94]

[Inspire_with_SM]

bhaiya mera code ==>

class Solution {
// Approach - 1 (Greedy Approach)
// T.C : O(n)
// S.C : O(1)
public long maximumValueSum(int[] nums, int k, int[][] edges) {
long maxSum = 0;
int count = 0;
int minimumLoss = Integer.MAX_VALUE;

for(int i=0; i<nums.length; i++){
int xorValue = nums[i] ^ k;
if(xorValue > nums[i]){
maxSum += xorValue;
count++;
}else{
maxSum += nums[i];
}
minimumLoss = Math.min(minimumLoss, Math.abs(nums[i] - xorValue));
}

return count % 2 == 0? maxSum : maxSum - minimumLoss;
}
}

[HammyHues]

Guys,
Let's consider,
In first approach min_nuksaan=7, and ideal_sum=248 and count is odd.
expected_sum = 248, that time there is no point in returning (ideal_sum-min_nuksaan), just because we have odd count we choose not to xor any edge.

the code is getting accpeted because that kind of testcase is not present, but in leetcode editorial section it is clearly explained.

[SnehaGupta-mynr]

If we are choosing any edge then what would be the use of given vector of edges, like we don't need to choose edge from given edges?

[manishjoshi]

sir hum nuksaan ki calculation ko else block k ander q nhi krre since nuksaan tbhi hoga jab xored value original value se kam niklegi, nuksaan ki calculation else kbahar krnse agar positive increment bhi hua wo bhi nuksaan main count ho jayega

[ashishanubhavmaharana]

Hey sir thanks for the wonderful explanation.
But sir I have one doubt in Approach -1 that why are we checking the diff for each index, we should check for the difference for the where we are getting a loss not for every index.

[mind.less]

#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

class Solution {
public:
long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
// Calculate the initial sum of the nums array
long long ans = accumulate(nums.begin(), nums.end(), 0LL);

// Traverse each edge
for (auto& edge : edges) {
int u = edge[0];
int v = edge[1];

// XOR of nums[u] and nums[v] with k
int xor_u = nums[u] ^ k;
int xor_v = nums[v] ^ k;

// Calculate the potential new sum if we XOR both nums[u] and nums[v]
long long newSum = ans - nums[u] - nums[v] + xor_u + xor_v;

// If the new sum is greater than the current sum, apply the XOR operation
if (newSum > ans) {
nums[u] = xor_u;
nums[v] = xor_v;
ans = newSum;
}
}

return ans;
}
};
sir whats wrong with this solution??