You are my guru in coding. Happy Guru poornima Sir🎉 I cracked phone screen round of google. Now, i am gonna take onsite rounds. Thanks for sharing the knowledge @neetcode
Hi If u dont mind can u share how u reached till the phone screen round . I am actually applying to lot of jobs recently but have been finding it hard to get an interview atleast. So any advice from u will be helpful .btw all the best for ur upcoming rounds
Solved it on my own. Yesterday I solved 4 problem on topic Topological sort from Neetcode and it turns out this problem can be easily solved using topological sort. Thanks Navdeep for Neetcode and Happy Guru Poornima 🎉
Happy Guru Purnima Navdeep sir!💐 Your videos have motivated and helped me whenever needed, to complete the July leetcode challenge so far and I have loved to see your approaches even if I was able to solve the problems myself. July leetcode badge coming soon. Thank you so much for all of your great content!
That was really a impressive use of topological sorting who would have thought we can use that algorithm in this question Nice solution as always @NeetCodeIO happy Guru Purnima🎉
Topological sort should work on a disjoint graph. A single dfs wouldn't because you can't cover all nodes from a single source, since the graph isn't connected
Thanks bro , bro prodigiously got them across to us pretty well, this problem is such an overwhelmingly hard for me and i couldn't have just coped with this without your aid
Within 8 mins i understood what the problem was asking and it's because of your amazing explanation. I know topo sort but my mind couldn't think of it until i watched your video You're just too good at teaching❤
I'm from Pakistan and currently pursuing a degree in software engineering. Alongside my studies, I'm dedicating significant time to mastering data structures and algorithms (DSA). However, I'm uncertain if excelling in DSA alone is enough to secure a job at top tech companies like the one you work for. Do I need to develop additional skills, such as web, app, or game development, to increase my chances of success? Also, could you share your experience on when you started focusing on DSA-was it during your degree or afterward?
i used a graph and a bfs with the same steps but didnt pass for some reason 😑 if they seriously made it so that only this algorithm passes thats extremely lame
Although the explanation was concise but one thing that I still cant understand in the example is, what exactly is preventing 3 and 1 from occurring in the same row coz at the end of the day, 3 and 1 jst need to be above 2 (row-wise) and 3->2->1 (column wise) right?? Please help me with this
Yeah, as per my understanding, it can be in the same row, but for our simplicity we are assuming different rows. It can be in same row, as long as that row is strictly above the row in which second element is.
I think he assumes they are in different rows for simplicity. That way , we can still fit every number in the matrix and have a valid solution. Because we have k rows and k columns for k numbers so even each number has a unique row and column , it's still possible .
For top sort both variants 1-3-2 and 3-1-2 are valid. But for our result only 3-1-2 fits. It seems just a luck that we choose 3-1-2. Place for possible bug. What do you think?
hey NeetCode(I know the real name but I love calling you that lol) great video and solution :D Thanks for this I had a doubt on 19:04 that you mentioned there will always exist the number in the rowOrder/colOrder if they're not empty(which is meant for they having a cycle) but what if they don't have a condition in the rowConditions/colConditions as given in the 2nd example of Leetcode problem statement :? what if there isn't any condition associated with a number that they can be placed anywhere in the matrix without any restrictions that we should check right? This is the part I'm confused with 😕
since in the topological sort we attempt to run a DFS from every source (1 through K), we should be able to collect every single one, even in a disjoint graph.
@@NeetCodeIO Thanks for the reply!🫡 My question was, what if the node isn't present in any of the disjoint graphs meant as k=3 rowConditions=[[1,2]] colConditions=[[2,1]] 3 isn't present anywhere so where should it be placed? I mean I couldn't see this condition that these row/colConditions would have all the nodes in them
OHH my bad lmao +_+ > The two arrays contain integers from 1 to k. didn't see this line from the problem anyways thanks for replying neetcode.. have a great day :D
Stopped after getting the intuition and came up with this #Cross topological sort def get_topological_sort(adjList, n): indegree = [0] * n nexts = defaultdict(list) for i, j in adjList: j -= 1 i -= 1 indegree[j] += 1 nexts[i].append(j) q = [] for i, j in enumerate(indegree): if j == 0: q.append(i) res = [] while q: record = q.pop(0) res.append(record + 1) for nxt in nexts[record]: indegree[nxt] -= 1 if indegree[nxt] == 0: q.append(nxt) return [] if len(res) != n else res rows_topo = get_topological_sort(rowConditions, k) if not rows_topo: return [] cols_topo = get_topological_sort(colConditions, k) if not cols_topo: return [] res = [[0 for _ in range(k)] for _ in range(k)] idx_pair = defaultdict(list) for i, j in enumerate(rows_topo): idx_pair[j].append(i) for i, j in enumerate(cols_topo): idx_pair[j].append(i) for num in idx_pair: i, j = idx_pair[num] res[i][j] = num return res
