Build a Matrix With Conditions - Leetcode 2392 - Python
Summary
TLDRIn this coding tutorial, the presenter tackles the complex problem of building a matrix with specific row and column conditions. They start by explaining the problem and its constraints, then dive into the intuition behind the solution, drawing parallels to previous problems like the course schedule and alien dictionary. The core algorithm discussed is topological sorting, a concept integral to solving this problem, which is compared to depth-first search (DFS). The presenter outlines the steps for topological sort, including cycle detection, before demonstrating the solution in Python code. The video concludes with a walkthrough of the code, ensuring viewers understand the logic and implementation.
Takeaways
- 😀 The video aims to solve a problem involving building a matrix with specific conditions.
- 🔍 The problem description is lengthy and complex, involving a K by K square matrix filled with numbers 1 through K, with the remaining elements being zero.
- 🔢 Two input arrays provide conditions for the placement of numbers in rows and columns, indicating which numbers must be above or to the left of others.
- 🔄 The solution involves a topological sort, similar to the algorithm used in the 'course schedule' problem, which is a prerequisite for understanding the solution.
- 📈 The core idea is to transform the two-dimensional problem into a one-dimensional one by first focusing on the rows and then applying the same technique to the columns.
- 🔎 A graph is constructed based on the row and column conditions, which helps in visualizing the problem and applying the topological sort algorithm.
- 🌐 The topological sort algorithm is used to determine a valid order for the elements in the matrix, ensuring that all prerequisites are met for each element.
- 🔁 The process involves running a depth-first search (DFS) to detect cycles in the graph, which would make the matrix invalid.
- 📚 The solution includes converting lists into hashmaps (dictionaries in Python) to efficiently look up the row and column positions for each number.
- 💻 The final implementation involves coding the topological sort and DFS in Python, with careful attention to cycle detection and the correct ordering of elements.
Q & A
What is the main problem being discussed in the script?
-The main problem discussed in the script is building a matrix with specific conditions based on two input arrays that dictate the placement of numbers within a K by K matrix.
What is the significance of the numbers 1 through K in the matrix?
-The numbers 1 through K are the only values that will be populated in the matrix, with the remaining elements being zero. Each number must be placed according to the conditions given in the input arrays.
What does the term 'above' in the row conditions signify?
-In the row conditions, 'above' means that one number must be placed in a row that is strictly above another number, and they cannot share the same row.
What is the core algorithm that needs to be understood to solve this problem?
-The core algorithm needed to solve this problem is Depth-First Search (DFS), which is used in conjunction with topological sorting to order the elements in the matrix according to the given conditions.
Why is it important to know the topological sort algorithm for this problem?
-Topological sort is important because it helps in ordering the elements in a way that respects the directed edges (or prerequisites) of a graph, which in this case is analogous to the conditions for the rows and columns of the matrix.
What is the role of the adjacency list in the script?
-The adjacency list is used to represent the graph of conditions for both rows and columns, making it easier to perform DFS and topological sort to determine the order of elements.
How does the script simplify the two-dimensional problem into a one-dimensional one?
-The script suggests focusing on the rows first, treating the problem as a one-dimensional ordering issue, and then applying the same technique to the columns after determining the row order.
What is the condition that would make the matrix invalid according to the script?
-The matrix would be invalid if there is a contradiction in the conditions, such as a cycle in the graph, where a number is above another and that second number is above the first, creating a loop with no valid ordering.
How does the script handle the possibility of a disconnected graph?
-The script handles disconnected graphs by running topological sort from every node and marking them visited as it goes, ensuring that all nodes are considered in the final matrix.
What is the time complexity of the solution provided in the script?
-The time complexity of the solution is determined by the traversal of the graph, which in the worst case could be O(K^2), where K is the dimension of the matrix.
How does the script ensure that the final matrix satisfies the row and column conditions?
-The script ensures this by using the results of the topological sort to create mappings for the row and column positions of each number, and then populating the matrix according to these mappings.
Outlines
😀 Introduction to Matrix Construction Problem
The video begins with an introduction to a coding problem involving the construction of a matrix based on certain conditions. The presenter outlines a plan to quickly go through the problem description, which is lengthy and complex, and then compare the problem-solving intuition to a previous problem. The core algorithms needed for the solution are highlighted as complex, emphasizing the importance of understanding algorithms like DFS. The presenter also mentions that the problem will be tackled in Python and concludes with a note about taking a break due to a long week.
🧠 Understanding the Problem Through Topological Sorting
The presenter dives into the problem by explaining the conditions for filling a KxK matrix with numbers 1 through K, with the remaining elements being zero. The conditions involve certain numbers being placed above others in rows and to the left in columns. The analogy of a directed graph is used to simplify the problem, where numbers are prerequisites for others. The concept of topological sorting is introduced as a method to order the values in a way that respects the given conditions, drawing parallels to the problem of scheduling courses in a curriculum.
🔍 Deep Dive into Topological Sorting and Cycle Detection
The video continues with a detailed explanation of how topological sorting can be applied to solve the matrix problem, both for rows and columns. The presenter discusses the process of converting the problem into a graph and using an adjacency list to represent it. The concept of detecting cycles in the graph is introduced as a critical step to ensure the matrix can be validly constructed. The presenter explains the use of two hash sets to track visited nodes and the current path to detect cycles, highlighting the importance of these steps in the algorithm.
💻 Coding the Topological Sort and Handling Edge Cases
The presenter moves on to the coding part, explaining the implementation of topological sort and depth-first search (DFS). The code is structured to handle the row and column conditions separately, using helper functions for topological sort and DFS. The video discusses how to convert the list of edges into an adjacency list and how to use hash maps to quickly look up the row and column positions for each number. The presenter also addresses how to handle the case where the matrix might not be valid due to a cycle in the graph, returning an empty array in such cases.
🔎 Implementing DFS and Cycle Detection in Code
The video script details the implementation of DFS and cycle detection in code. The presenter explains the parameters passed to the DFS function, including the adjacency list, visit hash set, path hash set, and order array. The function is designed to detect cycles by checking if a node is already in the current path, indicating a cycle. The DFS function is used to traverse the graph, appending nodes to the order array once all their neighbors have been visited. The presenter also discusses the importance of reversing the order array to match the topological sort requirements.
🏁 Wrapping Up the Solution and Taking a Break
In the final part of the video script, the presenter wraps up the solution by summarizing the steps taken to solve the matrix construction problem. The focus is on the implementation of topological sort and DFS, and how they were used to populate the result matrix. The presenter acknowledges the complexity of the solution and congratulates the viewers for making it through the explanation. The video concludes with the presenter taking a break, thanking the viewers for watching, and promising to see them soon.
Mindmap
Keywords
💡Matrix
💡Conditions
💡Topological Sort
💡DFS (Depth-First Search)
💡Adjacency List
💡Cycle Detection
💡Graph
💡Hash Set
💡Algorithm Complexity
💡Disjointed Graph
Highlights
Introduction to the problem of building a matrix with specific conditions.
Problem description involves creating a K by K matrix with conditions on row and column placement.
Only K elements will be populated in the matrix with the rest being zeros.
Row conditions specify that certain numbers must be placed above others.
Column conditions dictate that numbers must be placed to the left of others.
Observation that each element in the matrix will have its own unique row and column.
Simplification of the problem by considering rows first, ignoring columns initially.
Comparison of the problem to course scheduling and alien dictionary problems.
Introduction to topological sort as a method to solve the row ordering.
Explanation of how topological sort works in the context of directed edges and prerequisites.
Application of topological sort to columns, similar to rows.
Visual representation of how elements are placed in the matrix based on row and column orders.
Discussion on how to code the solution, emphasizing the need for a hashmap for efficient lookup.
Implementation of topological sort with considerations for detecting cycles in the graph.
Use of depth-first search (DFS) in the implementation of topological sort.
Explanation of how to detect cycles using a path hash set and a visit hash set.
Coding the solution in Python, detailing the process of converting lists to hashmaps for efficient access.
Final steps in the solution, including initializing the result matrix and populating it based on the determined orders.
Conclusion and encouragement for viewers who have followed through the complex solution.
Transcripts
hey everyone welcome back and let's
write some more neat code today so today
let's solve the problem build a matrix
with conditions okay so since we all got
things to do in places to be I'm going
to try to make this quick don't hold me
to that though so the first thing I'm
going to do is just go through the
problem description because to be honest
it's kind of long and pretty complicated
second I'm going to show you that the
intuition to solve this problem is
actually very similar to yesterday's
problem while at least trying to figure
out the general idea third I'm going to
explain the core algorithms you're going
to need because even if you're a genius
and you kind of know how to solve the
problem the algorithms themselves are
actually kind of complicated that's why
I always say that you should know
algorithms like DFS very very well
because when you get to a problem like
this DFS is only a small part of this
problem finally we're going to code it
up in Python lastly when I'm done with
that I'm probably going to take a break
because to be honest it's been a long
week and I'm sure you might feel the
same so let's get into it the idea is
let's focus on the example we're given K
so tells us the dimensions of the output
Matrix that we want so it's going to be
K by K it's going to be a square Matrix
next we're given these two input arrays
this is kind of the complexity of the
problem what the first array is saying
is that these two numbers are going to
well first of all let me just say that
the only values in this are going to be
the numbers 1 through K the only values
in column conditions are going to be the
numbers 1 through K and we want to take
the numbers 1 through k and put them in
this Square Matrix now that might sound
confusing because if we have a k byk
Matrix how can we fill it with just K
elements well the remaining elements are
going to be zero so only K elements are
going to be populated 1 through K
obviously in this example K is three so
what the first array row conditions
tells us is that one will be in a row
above the value two so theoretically we
could have had one over here and two
over here or we could have had one over
here and two over here or we could have
had one over here and two over here and
that's what we ended up with now there's
a second condition 32 so three has to be
above two two could have been here or it
could have been here or maybe three
could have been here and then two could
have been down there so it's a little
bit ambiguous isn't it right now the
ordering is three one 2 for the rows we
could have I think had 1 3 2 because all
we need is one to be above two and three
to be above two and I think both of
these satisfy that condition when they
say above it needs to be strictly above
so they can never share the same row the
second array column conditions is pretty
much the exact same thing except for
column so if we have 2 one we say two
has to be to the left of one it could
have been like this or it could have
been you know like this or it could have
been like this now once you realize that
these are saying it needs to be strictly
different like it needs to be above or
with the columns it needs to be to the
left you kind of realize that every
single element in the Matrix is going to
have its own row and its own column
that's kind of an important observation
to make right like here you can see
everything has its own row and own a
column so this kind of makes the problem
seem like it's not the end of the world
doesn't mean it's easy but I'm about to
show you how you can actually make it
easy for yourself look I'm not going to
lie to you I still don't know how to
solve this problem so what can we do
let's just try to simplify it for a
second forget about the columns let's
take this two-dimensional problem and
turn it into a one-dimensional problem
if we only had to deal with rows how
would you solve the problem well I don't
know about you but this is kind of
giving me vibes from the problem course
schedule if that's not enough maybe
you've solved that crazy hard problem
alien dictionary is it giving you
similar Vibes because it is for me if we
only have one array it's basically
saying that one is a prerequisite of two
like one is like a directed Edge kind of
right like one is going to be above two
and we're also saying three is going to
be above two as well so if we were
actually to draw it as an entire graph
we'd have a graph that looks like this
and this is only for the rows by the way
so now it kind of becomes clear well it
becomes clear if you've heard of the
algorithm
topological I I don't know how to spell
today I'm really sorry topological sort
if you don't know what this algorithm is
I'll try to teach it to you because it's
not super bad but at the very least I
hope you do have a decent understanding
of DFS if not I have plenty of other
videos you can check out n cod. but
definitely get a good understanding of
DFS before attempting this because what
topological sort says is what is a valid
way that we could order the values in
this graph so that they're actually
visited in the order that the edges are
represented such that basically for us
to visit to we visit all of its
prerequisites first so basically one
valid ordering would be 1 3 and then two
or 3 1 and then two so like those two
orderings I said would work now we've
kind of solved the problem in one
Dimensions if we didn't have to worry
about a matrix if we were just ordering
the values on which like row each
element is going to go in we've pretty
much solved the problem haven't we okay
but that's not enough because if we say
okay we have 3 1 2 well we got to put
these in different columns well can we
just take the exact same technique and
apply it to the columns why not I'm
going to do exactly that and let's just
try it and see what happens so down here
I'm going to have the columns graph I'm
going to take these edges build a graph
in ter terms of code we generally use
something called an adjacency list so
that's what I would do but visually it's
going to be looking something like this
so two goes into one and three goes into
two okay so this time it's actually very
straightforward there is not a choice
here it has to be in this order meaning
the columns the First Column has to be
three the second column has to be two
and the First Column has to be one okay
so that makes sense so far and we've
pretty much solved the problem if you
don't understand it let me kind of draw
it out for you suppose I took one of
those valid orderings from the row let's
just represent it in terms of a list and
I'll kind of do it consistent with this
example so let's say we did three first
and then one and then two these are the
orderings of the rows and then same
thing for this we got 3 2 1 this is the
ordering of the columns now what does
this tell us it might not seem obvious
but if three is in the first position
it's going to go in the first row
meaning it's going to go in row zero one
is in the second it's going to go in row
one two is in the last position it's
going to go in row two three is going to
go in column zero this is going to go in
column one this is going to go in column
two so basically the index that each
element shows up in is going to be the
like coordinate it's going to be
assigned so three you can see three is
at row Zer and column Zer so it's going
to go obviously at 0 0 one is at Row one
and column 2 so it's going to go at Row
one and column index two so right over
there lastly two is at row two column
one so it's going to go at row two
column 1 and that's exactly it look we
just did it conceptually it's not super
crazy even this by the way like I drew
this out like it's so simple but even
this in terms of code how do you think
you'd code this up because the way I
filled this in was number by number so
the way we're going to code this up is
actually by converting this into a
hashmap but that's a minor detail I
think can be explained more easily in
the code explanation we're actually not
quite done with the drawing explanation
yet there's a couple other things we
have to cover one is going to be how
does topological sort work how am I
going to implement it it's very similar
to DFS with a couple differences second
there is an edge case that we do have to
consider because it's Poss possible that
the Matrix is not valid let me actually
start with that can you think of what
would have to happen for the Matrix to
not be valid well we need a
contradiction right so what if I said
okay Row one is above row two this is a
one Edge row two is above Row three and
then I tell you well Row three is above
Row one do you see the contradiction
like if I put one here and then I put
two down here and and then 2 is above
three how can three be above 1 it's a
contradiction so how would the graph for
this look like let's say something like
this 1 to 2 2 to 3 and then 3 to 1 now
you might see we know it's invalid if
either of the graphs either the row
graph or the column graph has a cycle
then it's invalid we'll get stuck in
like an infinite Loop now how would you
detect that there is a cycle because
consider this for a second just consider
like a random looking graph that looks
something like this uh one maybe goes
into two and three and then both of
these go into something called four like
imagine we have a graph that looks
something like this this does not count
as a cycle it doesn't count as a cycle
because from one we can go to three and
then we go to four that's it then we go
back to three we go back to one and then
from there we go to two and we get back
to four yes we visited the same one
twice but that doesn't mean there's a
cycle a cycle would mean that you know
along the same path we keep going and
then we get back to a previously visited
node this is not a cycle because we go
here and then that's the dead end then
we go all the way back and then we go
down here and then we go all the way
back I don't see the cycle here because
there isn't a cycle in this graph so the
way I'm going to detect Cycles is by
having one hash set for visit did
because we don't want to have repeated
work we don't want to end up visiting
the same node twice consider if this one
had some descendants and we wouldn't
want to have to Traverse them multiple
times so that's going to be one hash set
but the hash set that's going to detect
Cycles I'm going to call it the path
hash set and I'm always going to add
every node that's along the current path
in that hash set if we pop back I'm
going to remove that node from the hash
set but nothing is ever going to be
removed from the visit hashset so that's
the small distinction and that's pretty
much the main distinction the only other
point that you need to know in terms of
like how I'm going to implement
topological sort there are a couple ways
to do it but I'll show you why I prefer
doing it the way I'm going to show you
consider pretty much the same graph
actually and then uh maybe like we have
some choices here like we have a five
here and believe it or not topological
sort works on a disjointed graph so you
can see these are all connected but
imagine I had six and it connects to
seven and imagine I had like eight to
nine so imagine a graph like this how is
topological sort going to work well
basically these ones are pretty
straightforward the topological sword of
this would just be 8 9 the topological
sword of this would just be 67 the
topological sword of this would be more
interesting there'd be more choices here
so we definitely have to start with one
and then we have a choice of either
three or two let's pick three we can't
go to four yet because we haven't met
the prerequisite so we have to also have
two here now that we have one we have 3
two we can either pick four or five the
order of these doesn't really matter we
could have it either way I'll just write
it like this with topological sort it's
non-deterministic there could be
multiple correct Solutions well I don't
know if non-deterministic is the best
word to describe it but it could have
multiple orderings so how would we
actually arrive at this in terms of code
well the way I prefer to do it and you
might have a different opinion I run a
dep first search I run the depth for
search until we get to the base case so
this is what I would do I would have my
output array which is going to be the
topological sort ordering I'm going to
get to one I'm not going to add it yet I
might add this to the visit hashset but
I'm not going to add it to the output
yet I'm going to do it in reverse order
I'm going to get to one I'm going to get
to two then I'm going to get to five
okay five is the one that doesn't have
any more descendants it's kind of the
base case so I'm going to add it at the
beginning I'm going to go back up to two
I can't add two yet I'm not going to add
two to the output yet I'm going to wait
until I do all of its descendants so
four is one of The Descendants now I'm
going to add four to it and now that
I've done both of its descendants now
I'm going to add two to the topological
sort output and then I'm going to pop
back up to one and I haven't done all of
one's descendants yet so now I'm going
to go to three and then I'm going to do
all of its descendants its descendants
have already been visited so I'm going
to go back now three all of its
neighbors have been finished so I'm
going to add three to the output
ordering and then I'm going to pop back
up to one everything's been finished so
we can go ahead and add one to the
output the only thing about this is It's
not what we want but it's an easy thing
for us to fix just take this and reverse
it that's it because with topological
sort what we're trying to do is visit
each node before we do all of its
descendants it seems like it might be
easy to do but this example will show
you it's not if I tried to do okay add
one then add two then add five okay it
seems like it's working so far then add
four and then we go back up to one and
then we add three well do you see the
contradiction how did we have four
before we added the three that's why
it's easier to code up if you do it in
reverse order you add these the nodes
that don't have any more descendants you
add them first and then you can just
reverse the output so that's pretty much
everything you need to know to solve
this problem and in terms of a Time
complexity I assume that there's not
going to be any duplicates in here so
it's basically going to be bottlenecked
based on the traversal which we're going
to run two times but that's a constant
so it doesn't matter so how big could
one of these graphs possibly be I guess
in the worst case each value could be
connected to every other value so I
think in the worst case that's k^ squ so
this is like the literal worst case I
don't think it'll actually be that much
so I guess
um it's either k^ s or the maximum of
either of these two it's going to be the
minimum of those so I guess you know
just take the length of either of these
actually now that I think if we're going
to be creating a matrix like this I
think k^ squ is probably the most
appropriate way to put it so I'll be
leaving it at that so now let's code it
up uh I don't know how helpful this is
but this is the train of thought that I
had um you can see it's going to be kind
of a lot of code so I'll try to keep it
relatively organized so the way this is
going to work is we're going to run
topological sort but remember the
example I showed you where we had a
disjointed graph where the graph isn't
connected we can't just pick one random
node in the graph and then run top
logical sort on it we might have to run
top logical sort from literally every
node in the graph and we can mark them
visited as we go so that's why we're
actually going to split this up into two
different helper functions I'm going to
have one helper function for topological
sort it's just going to take in the list
of edges either this or this and we're
also going to have a function for depth
for search that's the one where kind of
the bulk of the work is going to be done
so let's just think about it abstracted
for a second let's think about it from a
high level the way I'm going to be
calling topological sort is like this
I'm going to call it twice passing in
row conditions the first time and I'm
going to be passing in column conditions
the second time and what we expect this
to return is pretty much what I had in
the drawing this is going to return the
row order of the numbers the order that
the numbers should appear in in terms of
the row the other one is of course going
to do the column order so these are
going to be arrays these are going to be
lists the way I'm going to code up the
topological store is if there's a cycle
I'm going to detect that by returning an
empty array so if either of these is an
empty array if not row order or not
column order then we're going to return
an empty array because that's what they
pretty much told us to do in the problem
description if that's not the case
assume that you already have these two
maybe in your real interview you don't
know the implementation details of
either DFS or topological sort but you
know that those are required to solve
the problem I think it's better to
actually start with this part of the
code because then at least you know
where you're going if you can Implement
these you can solve the problem so here
what I'm going to say is we have these
but what we're trying to do is populate
the result Matrix so I'm actually going
to initialize that down here in pyth on
it's pretty straightforward to do it's
going to be K by K so something like
this and now I want to go through every
number from 1 to K num in range 1
through K and I want to say that at some
row column position I want to assign
this numb but we don't know which row
that this number belongs to or which
column it belongs to but the fact that
we have the column and row ordering we
can get that with these data structures
we wouldn't be able to get it in
constant time so I'm going to convert
convert these two lists into hashmaps or
dictionaries in Python so I'm going to
say before this over here I'm going to
say value to row hashmap and you know
you could probably code this part up
like in your language of choice in
Python I'm going to try to keep it
concise because this is going to be a
long enough solution as it is so I'm
going to use something called dictionary
comprehension right now I'm also going
to enumerate I'm going to say for i n in
enumerate row order so this will give us
the index and the number in that array
of course we want the number to be
mapped to the index which tells us the
row so I'm going to say n maps to I I'm
going to copy this and just update it
slightly by renaming this to Value to
column and renaming this column order so
it's going to do the exact same thing
for column order so then down here I'm
going to look up the row and column with
these two data structures just just like
that and assuming we do that we should
have the result and we can guarantee
that row order and column order if
they're non-empty are going to include
every number from 1 through K because
even if the graph is not connected even
if it's a disjointed graph we're going
to visit every Edge and I'm going to
show you that part right now I just
happen to know it off the top of my head
because I know how topological sort
works at a pretty decent level this is
like an advanced algorithm which is why
I cover it in my Advanced algorithms
course I don't expect you to like be an
expert on this so if we're passing in
the list of lists generally that's not
how we want to run a DFS so the first
thing we're actually going to do in here
is convert it into an adjacency list so
I'm going to call it adjacent default
deck and I'm going to pass in list and
so that will make it easy for us to do
this for Source destination in edges
because we know we're dealing with
directed edges here so I'm going to say
that for this Source node I'm going to
append to its neighbors this destination
note so that's just initializing the
adjacency list the next thing we would
want to do over here is go through every
Source from one through K so I'm going
to say 1 through k + 1 and then run a
DFS on it now of course we're going to
have to pass in the source node to run
the DFS but there's a few other things
we're going to have to pass in as well
another thing will be the adjacency list
obviously another thing is going to be
the two hash sets that I talked about we
want them Mark positions visited we
don't want to get stuck in an infinite
Loop and we also want to be able to
detect a cycle so we're going to create
two hash sets for those I'm going to
just copy that right there there is one
last parameter we're going to pass in
it's going to actually be an array I'm
going to call it order because remember
ultimately what we're trying to do is
collect the order so that's kind of what
I showed in the drawing explanation when
we reach the base case in DFS that's
when we will append a node or not even a
base case but once we visited all the
neighbors of a given node so um here I
will create an array for the order and
then remember before you return the
order you definitely want to make sure
to reverse it in Python you can do that
pretty easily like this and here I'm
just going to make a comment that that's
reversing it now what about cycle
detection the way I'm going to detect a
cycle is like this that's actually the
first thing I'm going to do in the DFS
other than I guess assign what
parameters we're going to have for it so
all these parameters so if source is in
path and the other one is if source is
in a visit I very specifically put this
one first because if a source node is
along the path that we're already on
then we detected a cycle if that's true
though this is also going to be true we
want to know if this one is true more
because this is the case where we've
detected a cycle and that's when we're
going to return false in the other case
down here I'm going to return true this
might make more sense when I finish the
rest of the function because as you'll
see when we get to a node we're going to
mark it as visited immediately add this
to visit so Source also I'm going to say
add it to the path just like that and
then I'm going to run my DFS somewhere
over here and then when I'm done with
that I'm going to say okay now path.
remove this node but we're never going
to remove a node from visit once a node
is visited it should never be visited
multiple times Okay so so now the actual
DFS part it's not super crazy let's go
through every neighbor of the current
node that's exactly why we have the
adjacency list so uh Source now we run
DFS on the neighbor so passing in the
same adjacency list same visit hashset
same path hash set in same order array
now what if we returned false from one
of the base cases like what if we
returned false from here what should we
do in this case well probably return
false immediately because once you
detect a cycle there's no point in
continuing so as soon as we see it if
not this then just return false no need
to visit the remaining neighbors if we
never detect a cycle though down here
let's just go ahead and return true
there's only a couple things left first
of all the order variable we haven't
really used it anywhere and that's
because we're saving it once we go
through all the neighbors of a given
node at the end after all that is when
we append the current node so that's
just the DFS portion okay I actually did
have a typo so this is going to be
Source sorry and I think we're actually
nearly done I'm just going to quickly
read through the rest of the code so I
think the DFS looks good it's very easy
to make a bug in a solution like this
where there's so much code so that's
another challenging part about this here
if the DFS returns false so if not DFS
here then we should return an empty
array there's no need to continue
running DFS and we definitely don't want
to return the values that have already
been added here at this point we return
an empty array so that here we can
detect that and then return an empty
array now before you call DFS you could
check if Source has already been visited
but that's literally a base case in the
DFS so it'll execute immediately anyway
so I don't think it's necessary to have
that line here um but here we're calling
topological sort getting the output
orderings um this is the case where we
detected the cycle then we otherwise we
convert it into the hashset down here we
ize The Matrix we get the row and column
here actually I think I messed this up
these are hash Maps um we want to look
up this number we want to map it to its
row so I'm going to fix that and here we
want to map that to its column so I'm
going to do that as well now I think
this is pretty much correct but it's
hard to fit it all on one screen yeah I
don't think it's possible to fit it all
on one screen I'm really sorry I'm
trying my best it's just really it's
it's 40 lines of code we should be able
to get it so that's a best I can do you
might have to zoom in but I'm going to
run it and it does look like it works
and it's pretty efficient if you made it
this far good job give yourself a pat on
the back I'm going to go take a break
thanks for watching and I'll see you
soon
Посмотреть больше похожих видео
Balanced Binary Tree - Leetcode 110 - Python
Word Ladder - LeetCode Hard - Google Phone Screen Interview Question
L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist
Lamps/Streetlights CodeSignal Coding Question - Sweep Line Algorithm
8 patterns to solve 80% Leetcode problems
Subtree of Another Tree - Leetcode 572 - Python
5.0 / 5 (0 votes)