Largest Color Value in a Directed Graph | Leetcode - 1857 | META | Explanation ➕ Live Coding Trash

This is the 21st Video on our Graph Playlist.
In this video we will try to solve a Hard but a very good Graph problem "Largest Color Value in a Directed Graph" (Leetcode-1857).

We will solve it using BFS and soon I will post another video on DFS approach as well.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Find the Link for that below.

Problem Name : Largest Color Value in a Directed Graph
Company Tags : META

0:00 - Understanding Problem
03:07 - Intuition Building
10:53 - Approach Building
19:06 - Story (Dry Run)
36:32 - Story to Code

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

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[_arpittiwari]

Before watching your video i was lile why this man is uploading videos of 40 to 50 mins.But after watching i must say its worth it;

[alphadrones]

amazing explanation for an awesome question ...

[VineetKumar-pjbk]

Bhaiya itni shiddat se koi explain nhi karta poore YouTube pe🔥

[iamnoob]

What a fabulous explanation, Took me some time to understand why are we storing maxfreq for each color at each node. Thank you

[wearevacationuncoverers]

I left the problem as soon as I read it because I had no idea how to solve this. I knew your video will be coming so I waited

[snehagoyal]

Your story telling is so great that I can even enjoy the question with popcorns. Thanks bhaiya

[elakstein]

nice explaination. Today I learnt topological sort with some of your other videos. I knew about the dfs one but Kahn's is a new learning for me.

[JJ-tpdd]

Thanks bhai, Java Implementation:

class Solution {

public int largestPathValue(String colors, int[][] edges) {

HashMap<Integer, List<Integer>> adj = new HashMap<>();

int N = colors.length();
int indegree[] = new int[N];

for(int[] edge: edges) {

int u = edge[0];
int v = edge[1];

adj.computeIfAbsent(u, k->new

indegree[v]++;

}

Queue<Integer> q = new LinkedList<>();

int dp[][] = new int[N][26];

for(int i=0; i<N; i++) {

if(indegree[i] == 0) {

q.offer(i);

dp[i][colors.charAt(i) - 'a'] = 1;

}

}

int answer = 0;
int seenNodesCount = 0;

while(!q.isEmpty()) {

int u = q.peek();
q.poll();

seenNodesCount++;

answer = Math.max(answer, dp[u][colors.charAt(u) - 'a']);

if(!adj.containsKey(u))
continue;

for(int v : adj.get(u)) {

for(int i=0; i<26; i++) {

dp[v][i] = Math.max(dp[v][i], dp[u][i] + ((colors.charAt(v) - 'a') == i ? 1 : 0));

}


indegree[v]--;

if(indegree[v] == 0) {

q.offer(v);

}

}

}

return seenNodesCount == N ? answer : -1;

}
}

[mohithadiyal]

The best explanation one could ever find 😊

[arjunsolanki]

Indeed a great video. Indeed a great explanation. Indeed a great teacher. Period.

[kartikkk]

maine isko pichla longest cycle in graph type vala logic lagaya tha 38 testcase pass hoke TLE aagya thora, new logic nhi soch paya mai, F

[souravjoshi]

JJ bhai, we all are waiting for the Java code 😃

[wearevacationuncoverers]

now I know why people call you king of graph

[prudhvirajmacherla]

Sir leetcode contest ka bee solution update kardo

[shashwats]

Bhaiya, please provide the slides also on which you write :)

[gautamarora]

Hey, could you please tell me why can't we maintain a hashmap each time we travel a path instead of a 2d matrix?

[snehagoyal]

REQUEST - Bhaiya can you pls start uploading videos in which you'll solve all questions of Leetcode Weekly and Biweekly contest.
Today's contest was a bit difficult for me and I could not find a great video with a great explanation like yours.

[MakeuPerfect]

sir today's leetcode contest ka second question karao plz

[elakstein]

If possible please link the prequisite video link in the description. I went to check out you graph playlist. The names are a bit confusing so unable to find out which video corresponds to the Topological sort.

[codeandtalk]

In the dry run example how 0 1 3 is a valid path?