Largest Color Value in a Directed Graph - Leetcode 1857 - Python
Vložit
- čas přidán 25. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Solving leetcode 1857 - Largest Color Value in a Directed Graph, today's daily leetcode problem on April 8th.
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/largest...
0:00 - Read the problem
3:30 - Drawing Explanation
10:30 - Coding Explanation
leetcode 1857
#neetcode #leetcode #python
Bro keep this up, it's always nice to have your videos to come back to if the daily challenge is a little too challenging xD
thank you very much , don't stop this series
Thank you for Awesome Explanation, Neetcode Sir! 👍
To make it even clearer, perhaps explain why you use max() and not just addition per color.
To do that, perhaps a better example, ideally a non-tree, with the same color on different converging paths.
Phenomenal explanation! Thank you .
Great Explanation ! you saved my streak today
Excellent explanation as always, thanks!
Great explanation as always, thx dude!
Thanks to you, the problem isn't hard anymore 😊
Bruh I didn't realize u had this other channel too WTF am very happy to see you always posting these algo vids. Friggin ledge!!!
Thank you so much 🙏
Explanation is great!
Although, according task constraints we have up to 10^5 nodes.
In your test pass you were lucky to have quite short recursive calls.
But what if it happens to get 10^5 recursive calls in a row on some input data? Overflow? Time limit exceeded?
Thank you so much
thanks, after listening, I tried to write the code without checking the video again, I made a mistake at 16:06, it's really easy to make a bug without thinking loop in path first
please make a video on Shortest Common Supersequence
The explanations for hard tasks are the most precious. Optimal cycle detection was my weak point.
If I got this on an interview it would take me way too long :( great vid
bring in more
14:36 Don't you mean "greater than that"? Because once we return Infinity there's no bigger value than infinity.
How long does this sort of problem take you to solve?
H Neet or any other Goolglers,
Can I ask do you suggest for the coding part
1.) Coding and explaining what's happening line-by-line with interviewer like what you show in the video?
or
2.) Say Can I take a couple of minutes to finish my code first? Then, coding but do not talking to the interviewer, after coding it out, then explain to interviewer?
hashmap instead of array gives 60%+, seems leetcode runtime doesn't like constant *26 for every test case
awesome
Aliens 👽👽 attendance taken by here
Here the main intuition is that we just have to have to look for any single color max value. It took e a lot time to get it, toposort is bit simpler in term of coding and understanding.
Here is the code:-
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n=len(colors)
indegree=[0]*n
graph=collections.defaultdict(list)
for a,b in edges:
graph[a].append(b)
indegree[b]+=1
d=collections.defaultdict(list)
for i in range(n):
d[i]=[0]*26
q=deque()
for i in range(n):
if indegree[i]==0:
q.append(i)
count=0
while q:
node=q.popleft()
d[node][ord(colors[node])-97]+=1
count+=1
for curr in graph[node]:
for i in range(26):
d[curr][i]=max(d[curr][i],d[node][i])
indegree[curr]-=1
if indegree[curr]==0:
q.append(curr)
if count!=n:
return -1
ans=0
for i in range(n):
ans=max(ans,max(d[i]))
return ans
Thank You NeetCode Bhaiya 😊
why it failed 49th testcase can someone explain?
class Solution {
vector adj;
vector vis;
vector pathvis;
vector t;
string c;
int n;
public:
int dfs(int node){
vis[node] = true;
pathvis[node] = true;
int idx = c[node] - 'a';
t[node][idx] = 1;
for(auto it : adj[node]){
if(!vis[it]){
if(dfs(it)==INT_MAX) return INT_MAX;
for(int i=0;i
I used the same approach in C++. It gave TLE. Any suggestions?
code:
class Solution {
public:
int dfs(int i,unordered_map &adj,unordered_set &visit,unordered_set &path,vector &cma,string colors){
if(path.find(i)!=path.end()) return INT_MAX;
if(visit.find(i)!=visit.end()) return 0;
visit.insert(i);
path.insert(i);
int cindex = colors[i]-'a';
cma[i][cindex] = 1;
for(auto nei:adj[i]){
if(dfs(nei,adj,visit,path,cma,colors)==INT_MAX) return INT_MAX;
for(int c=0;c
According task constraints we have up to 10^5 nodes. So in some cases it's possible to get 10^5 recursive calls in a row. Could we implement DFS without recursion?
replacing colors.size() with colors.length() made it work for me..hope this helps
i got tle too, but once i remove this return line "*max_element(cma[i].begin(),cma[i].end());" from dfs, and only call it once when i need to return the answer of this problem, that is very waste your time to count every time you run dfs, furthermore it's not necessary to count every time too.
class Solution {
fun largestPathValue(colors: String, edges: Array): Int {
// 1. build adj list
val adj = mutableMapOf() // 0 -> [1, 2]
edges.forEach { edge ->
adj[edge[0]] = (adj.get(edge[0]) ?: mutableListOf()).apply{ add(edge[1]) }
}
// 2. init grid
// a, b, c, .. z
// 1
// 2
// 3
// nodeNum
val grid = Array(colors.length) { IntArray(26) {0} }
// 3. run dfs
var res = 0
val visited = mutableSetOf()
val path = mutableSetOf()
fun dfs(cur: Int): Int {
if(path.contains(cur)) {
// cycle
return Int.MAX_VALUE
}
if(visited.contains(cur)) {
// been before
return 0
}
visited.add(cur)
path.add(cur)
// update grid
val curColor = (colors[cur]).toInt() - 'a'.toInt()
grid[cur][curColor] += 1
adj.get(cur)?.forEach { nei ->
if (dfs(nei) == Int.MAX_VALUE) return Int.MAX_VALUE
(0 until 26).forEach { c ->
grid[cur][c] = maxOf(grid[cur][c], grid[nei][c] + if (c == curColor) 1 else 0)
}
}
path.remove(cur)
return 0
}
for(i in 0 until colors.length) {
if (dfs(i) == Int.MAX_VALUE) return -1
}
val maxValuesForRow = grid.map { it.max() ?: 0 }
val maxValue = maxValuesForRow.max() ?: 0
return maxValue
}
}