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.
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?
Using a fixed array of size 26 might not be efficient if you don't always need to track every letter. A Counter from Python's collections module might be a better fit in this case, as it dynamically adjusts to the letters present without allocating unnecessary space. Just that change will boost your algorithm several times over to the top end.
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
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
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?
In the presented solution, it seems suboptimal to use a set to check if a node is part of the current path or not. We can define the nodes as a structure {index: int, in_path: boolean}, where we change the in_path value on the fly each time we add or remove a node from the DFS stack. The solution is inspired by Tarjan's algorithm, which uses DFS to search for strongly connected components in subgraphs. The existence of a strongly connected component indicates the presence of cycles. The idea is to modify Tarjan's algorithm to incorporate the update of color scores inside its DFS and to stop all search as soon as a cycle is found.
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?
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 } }
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 🙏
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.
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
Great Explanation ! you saved my streak today
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?
Using a fixed array of size 26 might not be efficient if you don't always need to track every letter. A Counter from Python's collections module might be a better fit in this case, as it dynamically adjusts to the letters present without allocating unnecessary space. Just that change will boost your algorithm several times over to the top end.
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
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 for Awesome Explanation, Neetcode Sir! 👍
Phenomenal explanation! Thank you .
The explanations for hard tasks are the most precious. Optimal cycle detection was my weak point.
Thanks to you, the problem isn't hard anymore 😊
14:36 Don't you mean "greater than that"? Because once we return Infinity there's no bigger value than infinity.
Excellent explanation as always, thanks!
hashmap instead of array gives 60%+, seems leetcode runtime doesn't like constant *26 for every test case
If I got this on an interview it would take me way too long :( great vid
Why are we returning 0 if node in visit.
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?
Great explanation as always, thx dude!
please make a video on Shortest Common Supersequence
bring in more
In the presented solution, it seems suboptimal to use a set to check if a node is part of the current path or not. We can define the nodes as a structure {index: int, in_path: boolean}, where we change the in_path value on the fly each time we add or remove a node from the DFS stack. The solution is inspired by Tarjan's algorithm, which uses DFS to search for strongly connected components in subgraphs. The existence of a strongly connected component indicates the presence of cycles. The idea is to modify Tarjan's algorithm to incorporate the update of color scores inside its DFS and to stop all search as soon as a cycle is found.
Aliens 👽👽 attendance taken by here
How long does this sort of problem take you to solve?
Thank you so much
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
Thank You NeetCode Bhaiya 😊
awesome
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
}
}