Build a Matrix With Conditions - Leetcode 2392 - Python

Summary

In 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

00:00

😀 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.

05:00

🧠 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.

10:02

🔍 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.

15:04

💻 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.

20:04

🔎 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.

25:06

🏁 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.

Keywords

💡Matrix

A matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. In the context of the video, the matrix is the primary structure the presenter is working with, aiming to build it according to specific conditions. The script mentions creating a 'K by K' square matrix, emphasizing the dimensions of the output matrix.

💡Conditions

Conditions in this script refer to the rules that govern how elements are placed within the matrix. The video discusses 'row conditions' and 'column conditions' that dictate the relative positions of numbers within the matrix, such as one number needing to be 'above' another.

💡Topological Sort

Topological sorting is an ordering algorithm used on directed graphs. It is a linear ordering of vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. The script describes using topological sort to solve the matrix-building problem by creating an order for the rows and columns based on the given conditions.

💡DFS (Depth-First Search)

Depth-First Search is an algorithm for traversing or searching tree or graph data structures. The script mentions that topological sort is similar to DFS and that understanding DFS is crucial for implementing topological sort, as it is used to visit all the nodes in a graph in a manner that respects the edges' direction.

💡Adjacency List

An adjacency list is a collection of unordered lists used to represent a finite graph. The script describes converting a list of edges into an adjacency list to facilitate the process of topological sorting, which is a way to prepare the graph for the algorithm to work on.

💡Cycle Detection

Cycle detection is the process of identifying cycles in a graph. The script discusses the importance of detecting cycles in the row and column conditions because the presence of a cycle would invalidate the matrix, as it would create a contradiction in the placement of elements.

💡Graph

In the context of the video, a graph is a structure that consists of nodes or vertices and edges that connect these nodes. The script uses the concept of a graph to represent the relationships between numbers in the matrix, with edges indicating that one number must come before another in the matrix.

💡Hash Set

A hash set is a data structure that stores unique elements. In the script, hash sets are used to keep track of visited nodes during the DFS to avoid revisiting the same node, which would lead to infinite loops, and to detect cycles in the graph.

💡Algorithm Complexity

Algorithm complexity refers to the amount of resources (such as time and space) that an algorithm consumes when it runs. The script briefly touches on the time complexity of the solution, suggesting that it is determined by the traversal of the graph, which could be as large as 'k^2' in the worst case.

💡Disjointed Graph

A disjointed graph is a graph that is not connected; it has two or more separate subgraphs. The script mentions that topological sort works on a disjointed graph, meaning that even if the graph is not fully connected, the algorithm can still find a valid ordering for the nodes.

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