Most Profitable Path in a Tree | BFS | DFS | Detailed | Leetcode 2467 | codestorywithMIK

Hi Everyone, this is the 69th video of our Playlist "Graphs : Popular Interview Problems".
Now we will be solving a good Graph problem - Most Profitable Path in a Tree | BFS | DFS | Detailed | Leetcode 2467 | codestorywithMIK

Problem Name : Most Profitable Path in a Tree | BFS | DFS | Detailed | Leetcode 2467 | codestorywithMIK
Company Tags : Intuit

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

Video Summary :
Approach-1 (DFS for Bob and DFS for Alice)

The idea is to first find Bob’s path to node 0 using DFS and store the time he takes to reach each node. Then, Alice starts her own DFS traversal from node 0, deciding how much profit she can collect based on whether she reaches a node before, after, or at the same time as Bob. The goal is to maximize Alice’s income when she reaches a leaf node.

Approach-2 (DFS for Bob and BFS for Alice)

Bob’s path to node 0 is determined using DFS, just like in the first approach. However, instead of DFS, Alice explores nodes using BFS, ensuring that she visits nodes in the shortest time possible while maximizing income. This approach effectively leverages queue-based traversal to efficiently process nodes level by level.

✨ Timelines✨
00:00 - Introduction
0:24 - Motivation
0:44 - Problem Explanation
9:50 - Thought Process and Intuition
22:11 - Story To Code
25:01 - Coding Approach-1 (DFS + DFS)
37:09 - Fixing important error
39:22 - Coding Approach-2 (DFS + BFS)
43:29 - Time Complexity

#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[rdwlf]

You are an inspiration brother.. i was struggling with dsa but following your videos i am able to solve medium level questions on my own as well as sometimes with your help..

[Bunny-lvqp]

This was one of the nicest question i had ever attempted on leetcode . Thank you mik for making it understand in such a easy way and story

[gauravbahukhandi]

Aap ky padhate ho bhaiya.. hats off to you ❤❤

[floatingpoint]

the question looked so hard but you made it easy

[baitMaster]

Solved it after two hours by myself. I just thought to myself - "how would MIK approach this?" and tried to mimic you, thank you so much, sir.

[AkashSingh-iqkw]

I was able to solve this question just by listening to your thought process at 11:30. Thanks MIK!

[kusumjoshi]

Kya explain kiya hai.. you are the best mik🥰

[bhuppidhamii]

aapki graph ki playlist padni padegi!!!

[ritikgupta]

your thought process (of just 1-2 mins) is enough to solve any problem.😊
here's my approach using 2 bfs:-

class Solution {
public:
int edges, int bob, vector<int>& amount) {

int n = amount.size();
unordered_map<int, vector<int>> adj;

// Build adjacency list
for(auto edge : edges) {


}

// Correctly identify leaf nodes
unordered_set<int> isleafnode;
for(int i = 0; i < n; i++) {
// A leaf node has exactly one neighbor, except for root
if(i != 0 && adj[i].size() == 1) {
isleafnode.insert(i);
}
}
// Special case: if root has no children, it's a leaf
if(adj[0].size() == 0) {
isleafnode.insert(0);
}

// Find parents using BFS
vector<int> parents(n, -1);
vector<int> visited(n, 0);
queue<int> q;

q.push(0);
visited[0] = 1;
parents[0] = 0; // Root is its own parent

while(!q.empty()) {
int node = q.front();
q.pop();
for(auto adjnode : adj[node]) {
if(visited[adjnode]) continue;
visited[adjnode] = 1;
parents[adjnode] = node;
q.push(adjnode);
}
}

// Calculate Bob's path and arrival times
unordered_map<int, int> bobpath; // node -> time
bobpath[bob] = 0;
int count = 1;
int i = bob;

// Keep moving toward root until we reach it
while(i != parents[i]) {
i = parents[i];
bobpath[i] = count++;
}

// Alice BFS to find max profit path
queue<pair<int, pair<int, int>>> alice; // <node, <time, profit>>
alice.push({0, {0, amount[0]}});

int ans = INT_MIN;

fill(visited.begin(), visited.end(), 0); // Reset visited array
visited[0] = 1;

while(!alice.empty()) {
int node = alice.front().first;
int time = alice.front().second.first;
int profit = alice.front().second.second;

alice.pop();

// If we've reached a leaf node, update answer
if(isleafnode.count(node) > 0) {
ans = max(ans, profit);
continue;
}

for(auto adjnode : adj[node]) {
if(visited[adjnode]) continue;
visited[adjnode] = 1;

int currsum = 0;

// Calculate reward/cost at this node
if(bobpath.find(adjnode) != bobpath.end()) {
if(bobpath[adjnode] == (time + 1)) {
// Alice and Bob arrive simultaneously
currsum = amount[adjnode] / 2;
}
else if(bobpath[adjnode] < (time + 1)) {
// Bob already opened the gate
currsum = 0;
}
else {
// Alice arrives first
currsum = amount[adjnode];
}
}
else {
// Bob never visits this node
currsum = amount[adjnode];
}

alice.push({adjnode, {time + 1, profit + currsum}});
}
}

return ans;
}
};

[mendahaseena]

Thank you. Your approach is really easy to understand and helped me a lot

[RohitSharma-kult]

today's question is very good . i understand many logic in single video. thank u MIK.

[AdityaSharma-oxdv]

Thankyou bhaiya for your help and hats of to your efforts

[utkarshjha]

your videos have made me consitent brother you consitency make more motivated than your motivation part i have gained much confidence after watching you videos recover soon bro and thanks a lot

[thebhrotherslakshya]

Thanks for this story to code, I really Admire you for the Best Explanation, Thanks to god So that i found your channel before, so that good explanation can come to find, Also i am planning to complete graph series from your playlists, Thanks.

[aadarshdontul]

Now I feel like a confident person in Graph Problems, the reason is you codestorywithMIK💯❤

[souravRawat-mrzk]

i was literally waiting for your video

[ShreyanshSingh-nk]

i thought the same lkogic..just cam here to see if I was right, lol

[AbhijeetMuneshwar]

Respected MIK Sir,

Your way of writing code and then updating / evolving it teaches us a lot about how one can write code and then improvise it as per requirements.

Thank you so much. 🙏

[vikasvoruganti]

I didn't seen the video yet but I solved just because of yesterday's community poll..

As the questions says it's tree, there is only one path between any two nodes in tree.
Finding the path between root(alice) to bob and adjust the amounts at nodes as per question.
Now using dfs from root(alice) to all leaf nodes calculate alice's net income and return the maximum income.

[madhukars-kk]

bhaiya video thodi choti banaya kro and jo aapne phle padaya use in video me merge mt kra karo please because agr koi new guy dekhe gaa to use SAMAJ NHI AAT LIKE KHaNDANI CONCEPT. it my personal openion. thanks for your all hardwork for us🙌🙌🙌