Problemlösungsfähigkeiten mit Elite-Code-Problemen verbessern

Hey, what's up everyone and welcome back to another video.

So if you want to become a great data scientist, software engineer, Uber, hacker, dude,

dude at you first want to become a good problem solver.

So in this video we're going to walk through a bunch of elite code problems and the reasoning

for this is twofold.

One, these elite code problems kind of can help you improve your general coding skills.

And then two, these are algorithms type problems.

So they really make you think and then really kind of train that problem solving muscle.

In this video, we're going to go from easy problems or relatively easy problems to more

difficult problems.

So feel free to do a little binary search to figure out like the right difficulty for

you.

Also feel free to kind of like watch one problem, then come back to the video another

day, et cetera.

And also the general way that you'll want to approach each problem is I'll link every problem

problem that we do in the description.

So what you should do is try out the problem on your own.

And then if you can't figure out the solution or just want to see how I would approach the

problem, play through my solution of the, the problem in the video.

Think this should be a fun one without further ado, let's get into it.

How I'm going to get to these problems is I'm just going to go to leekode.com.

I'm going to click on problems.

I'm going to use filter by algorithm, it doesn't really matter here.

And then just to kind of figure out what's harder, what's easier.

This isn't a perfect filter, but what I ended up doing is I filtered or I sorted by acceptance.

So the higher the acceptance rate, you think that that would be kind of the easier problems.

More people got them right.

So to start off, we'll kind of do some higher acceptance, easy problems, then we'll

move into kind of some higher acceptance, medium problems.

And then maybe at the end of the video, we might do one or two hard problems, not positive

yet.

All right, to start off, let's do this problem, the goal parser interpretation.

This is problem 1678 and I've linked it in the description.

And so you can read through the problem statement, but the basics is that we have this

parser that takes in strings of the format like this and translates it into more readable

strings like this.

And so there's three characters, there's the G, the parentheses and the parentheses with

the AL, and we need to just do these replace bins.

So it's pretty straightforward problem, but let's give it a shot.

Feel free to pause the video and then resume when you want to see me solve it.

All right, so when I look at this problem, I think about replacements in Python.

We're taking these inputs over here on the left and we're making these outputs.

So when we're thinking of replacements in Python, I think of the string replacement method.

And if you're not familiar with that, as always, kind of allude to, do a quick Google

search like replace strings in Python.

And you'll find something useful that can maybe help you out.

So it's as easy as doing something like this.

Well, now that we have that, we can just simply do the replacements that are necessary.

So we have a command, right?

And if we do dot replace, or we can replace the G with a G, but we don't really need to

do that because that's not actually replacing anything.

So we can start with the parentheses.

Anytime we see parentheses, let's replace it with just an O.

We can chain these commands together.

So this is going to return us a string.

So we can actually just simply do dot replace again with AL and making that just AL without

parentheses.

And that should be all there is to changing it to the format that we expect.

So I want to just go ahead and return this and see what happens.

So I'm going to run code.

Nice.

It looks like it worked.

And the next thing we want to think about when we're doing problems like this, are there

edge cases that we're not considering?

Well, I think to do that, we're going to have to look at the different examples and

kind of the constraints.

So we know that it's going to be between 1 and 100.

So that's pretty straight forward.

That's pretty small.

We don't have to really worry about like, is the replace method like efficient or not.

And we also know that we're constrained to only these three characters.

So there's no like weird, maybe like situation where there was like something like, you

know, a parentheses that's not fully closed or something and or like nested parentheses

like that.

So I think we're good here.

You can feel free to type in these other examples as test cases, but I'm going to go ahead

and submit this.

Accepted.

Look at that.

Cool.

And there's many different ways to do this.

My other recommendation when you're doing these problems is you can go to the discussion

always and look at other people's solution.

So we see like Python online, I'm guessing this is going to probably be the same as what

we have and look at that it is, but maybe some of these other solutions are different.

So Python, C++, simple solution using dictionaries.

And we see this person has done something else in their solution.

So it's good to maybe look through these discussion solutions because that gives you other

ways, other perspectives on how you can solve these different things.

All right.

Next, let's do problem 1436 destination city.

So in this problem, we are given an array paths and each path in that array is a connection

between city A and city B where there is a, which means there is a direct path going from

city A to city B.

And our goal is to return the destination city, which is the city that doesn't have any

outgoing paths from it.

So as an example, we see in this case, we have the path London to New York.

We have New York to Lima, Lima to Sao Paulo.

And because Sao Paulo has nothing coming out of it, no, no paths are leaving from Sao

Paulo, we know that Sao Paulo is the destination city.

There's also you can have more complex examples, like example two, where you can go from

B to C, you can go from D to B and you can go from C to A. So there's a few different

path options as we can see here.

But every one of those paths leads to A. So we know that A is the destination city.

So how could we program out a solution that could kind of find that destination city?

So what I think about this problem, I think about counting.

We're ultimately trying to count the city that has no outgoing nodes from it.

So if we count how many outgoing nodes, each one of the cities that we see has and just

return the one that has zero outgoing, that will be our solution.

So we can probably use a lot as a dictionary to help us do this.

So let's write a solution that does that.

So for path in paths, we want to iterate over each path.

And I do want to quickly add some sort of dictionary that we can use to count.

So let's say that this is called outgoing count and we'll make that an empty dictionary.

So for path in paths, well, that each path is going to be a pair of two cities city A and

city B. So what we could do is we could say that city A comma city B equals path.

This is just unpacking a path like London, New York.

So city A would be equal to London and city B would equal to New York.

That's one way we can unpack a list of two items or a tuple of two items.

So we have city A and city B. And really what we want to count is we want to increase

this account every time a city is listed as city A.

But we do want to count city B because ultimately if we only counted city A is we'd

miss out on the destination city.

So let's add both of these to the dictionary.

So what we can do is something like outgoing count and

we can use the city that we want to input into that.

And then what we want to do is kind of like increase that count by one.

But it might not be set to begin with.

So we'll have to keep that in mind.

So we'll say something maybe like outgoing count dot get of the city A.

And if we don't have city A already there, then let's go ahead and set that to one.

Do we get in with?

And we can do something similar for city B.

So we can say outgoing count city B equals outgoing count.

Dot get city B.

But this time because city B is the destination node,

we don't want to increase that outgoing count for city B.

So if we haven't seen city B before, let's just set it to zero.

And I guess in this case too, we don't want to just get the number.

We do need to increase it.

So in this case, we should do, we don't even need it.

We can say keep this at zero, but we should add one at the end.

So if we haven't seen it before, we set it to zero, but then we add one.

If we have seen it already, we've seen that there's outgoing node.

Then we get that count and we just add another one to it.

And really it doesn't even matter.

All we care about is ultimately what's left as zero.

Okay, so that creates our dictionary.

So once we have a dictionary that has all those counts,

then we actually need to go ahead and count them and see what value is the lowest.

So what we could do is just iterate over the dictionary.

So let's just say for city and outgoing count.

And then if we ever find a city that has zero outgoing counts, that's our solution.

So that's what we can return.

So outgoing count of city, if outgoing count of city equals equals zero,

then we want to return that city.

And we always are supposed to have a destination city.

So there should never be an error case here.

So I think that this is probably a good solution.

Look at that, it seems to work.

And so what would be the complexity of this solution?

Well, it's bounded by O of n to iterate over each path in the paths.

And really we can't get any better than O of n because we have to look at

every path to ultimately figure out what's the destination city.

But I guess the question is, does this last second iteration over the dictionary

increase that runtime complexity?

And ultimately it does not because it's just another,

instead of just going O of n or like just one iteration of n times,

we're doing a second iteration of n times.

So it's really a total of two n iterations which is still bounded by that O of n

runtime complexity.

So that seems like a pretty good solution to me.

Let's go ahead and submit that.

And it is submitted or it is accepted.

Cool.

And it looks like it's running pretty well.

It's less than 97.31% of the Python 3 online submissions.

And it's faster than 74.51% of them.

So in this case, our first solution worked out well and did a good job.

Sometimes that's not the case and we have to continue and prove things.

But I would say that I would be pretty happy with this.

If I saw this as the solution to like a coding interview question,

one thing that's cool to do though is kind of look at the discussion,

see if there's anything else really clever that people did.

And look at that.

This person used a set and basically said, OK.

I mean, this is a little hard to read, but I really like this idea of a set.

Basically, they counted what's in city A and what is a city B.

And then they subtracted the set of B elements that were in B from elements

that were in city A. And ultimately, the one that's left in B

that wasn't in A will be that element that is returned.

Next, we're going to do problem 1365.

How many numbers are smaller than the current number?

Again, linked in the description.

And so the problem statement here is, given array numbs, for each numbs I,

find out how many numbers in the array are smaller than it.

That is, for each numbs index I, you have to account the number of valid j's

such a j is not equal to i.

So that's talking about indexes.

And numbs j is less than numbs i.

So sometimes these problem statements can be kind of confusing.

So my recommendation is always, you know, really look at the examples.

That will be what really solidifies the problem.

So we see here in this example, we have this input, which is an array of numbs.

8, 1, 2, 2, 3.

And we see the output is 4, 0, 1, 1, 3.

And what they're doing here is that we look at this number 8, and we see that we have

4 numbers that are less than it.

That's where we get the 4 here, the 1.

There are no numbers in this array that are less than it, so we get the 0, et cetera.

So when we're solving problems like this, what I recommend is don't try to be creative.

Don't try to be clever to start.

What is a simple solution that you can think of that would work?

And so when I look at this, I see what's easy to me is just let's do some kind of a straightforward

counting.

Let's look at each number in this.

And as we're looking at that number, let's just iterate over the entire list and just count

how many numbers are less than that number and append it to our output.

So for example, this 8, we would be looking at it and then iterate over the rest of

the list.

1, that's less than it, plus 1, 2, plus 1, 2, plus 1, 3, plus 1.

That's a total of 4, so we'd append 4 to our list, and we just kind of continue down

our list.

So let's write that in code.

And this solution I just described would be a complexity of n squared.

So I think we can probably do better, but I think it's good to just kind of write out a

simple solution first.

But if you were doing this in an interview setting, just be like, hey, this is what I'm

thinking of right now.

But ideally, we could figure out something more efficient and kind of start there.

See that you're thinking, see that you are kind of always seeing how you can improve things.

All right, let's implement this.

So for I in Nums, we'll look at each number here, I'm going to keep track of our output

in a row.

So we're going to say output equals an empty list.

So for I in Nums, we want to then iterate over 4j in Nums.

And basically, as we are looking at this problem, we don't want j to be equal to i.

So we're going to say if j is not equal to i, then we want to, maybe let's say we have

a counter, count equals 0, and we're going to increase that counter.

Count plus equals 1.

And then when we've exited out of this loop, so when we've iterated over the entire array

of Nums for this specific i, we can do output is the append of the current count.

And then we will get our next i, and our count will be reset to 0.

So we do that for everything, and then we can simply at the end return the output.

So hopefully that made sense, and let's run it and try it.

Wrong answer.

Okay, I guess something got screwed up there.

So I'm pending every time.

We want it only append if j is not equal to i, and Nums j is less than Nums i, oops

about.

That was a silly mistake.

Index our list index out of range.

What do we do here?

Oh, oops, now what are we doing?

Now we're not looking at the indexes.

So see, you make mistakes if you're not careful, but what's happening here is we're not

iterating over the actual index value.

So what we could do is we could say, in length of and range, length, Nums, and again,

we want to iterate over the index value, so we're going to do range, length, Nums.

And what I would recommend is if you have premium, you can get the debugger, so you can

actually print out values and see what's going on.

But you also could just like open up a sublime text window, whatever your code editor

of choice is, and try out some of these test code cases with a function that you define

there.

But let's run this code again.

Okay, look, that looks like it works.

We could try more test cases, but I'm feeling confident that let's just go ahead and

submit our code.

Look at that.

It is accepted, but we see that our runtime is only faster than 8.83% of Python 3 submissions.

So there's something we can probably can do that is smarter than this.

So we're right now at a complexity of N squared.

I'm going to just scrap all this and we're going to start fresh.

Let's try to get to a complexity that is better than N squared.

And one thing to note is you can always find the code.

If I click on accepted here, I could find that last submission.

So I'm not losing anything by deleting all of my code.

Let's go back.

All right, we just did an N squared solution.

What I think is better, this is the next thing that comes to mind.

It might not be the optimal solution, but I'm thinking if we sort this list and know the

length of this list, then it's pretty easy for us to tell how many numbers are less than

the current number we're looking at.

So if we sorted this, let's say, like 8, 3, 2, 2, 1, so I'm going to type that out real

quick.

So let's say we sorted this to 8, 3, 2, 2, 1, well, we see that 8 would get 4 numbers

less than it, 3 numbers less than it, 2, well, we see we have 2, and we see the next

number is 2.

So really, we need to start counting only when we get to the new number.

So we'd have to count how many times we see that the same number and kind of append that

many times.

So we'd 2 would be 1 number, 2 would be 1 number, and then 1 is the last item, so that'd

be 0 numbers.

So couldn't we implement this solution?

All right, I'm going to kind of just start fleshing things out, and I might have to like

throw some print statements in this and whatnot to get it to fully be working.

But let's start out by defining sorted num's equals sorted, I think we do that, sorted.

I think that's a built-in Python function of num's.

And honestly, I could real quick do print sorted num's and just check.

So we're going to run code real quick, and it does give us our standard output, okay.

So we see that it's sorting it lower to higher.

So I think if I pass in the keyword reversed equals true, I'm like, really, I would normally

be Google searching this, I'm like crossing my fingers at those works right now.

this is, maybe it's reverse, oh, look at that, it worked.

Normally I would have to look this up, I kind of vaguely remember that.

Okay, so we have 8, 3, 2, 2, 1, that's what we're looking for.

And now what we're going to do is, let's go for num, or let's do, how about this?

Let's do, for I comma num, so we're going to have an index and the number, and a numerate.

A numerate's a very useful keyword, a numerate sorted num's.

And we also need to think about the original index here.

So there's a couple of things that now that we're working through this, that I'm trying

to keep in mind, because now that we sorted it, things are out of order, so this output

would be out of order as well.

So how could we keep that in mind?

So one idea that comes to mind, and I'm not positive if it's the optimal solution, but

if we have a list like 8, 3, 2, 2, 1, let's create a dictionary that looks of the format,

you know, value, so the key of the dictionary is the value, and it maps that value to the

number of values that are less than that value.

So like 8 would map to 4, 3 would map to 3, etc.

And then we'll do a additional pass on our input just doing lookups in this dictionary

to create our final output.

So this will make sense in one second.

So what we could do is something like, as we look at a number, so let's say we're looking

at 8, we check the next number.

If it's less than 8, then we check the length of this array, and we subtract this current

index to find the number of values that are remaining in the array.

And then we append that to our dictionary.

So I'm going to call this value dict, or maybe I'll call it, if I want to be more descriptive,

like smaller, smaller count, I'm struggling to just figure out a good name.

It's good to use descriptive variables, but you don't have to worry too, too much.

I think smaller count makes sense, they're probably something better I could use.

But what we're going to do is, so we're looking at a current num, so basically if sorted

num's i plus 1 is less than sorted is less than num, then we want to take these

the index of sorted num's i plus 1, and basically do remaining values equals sorted num

or equals length of sorted num's minus i plus 1, because this is the index that we're

looking at, and this is the total length.

So this subtraction would give us the number of values that meet that criteria.

So we see if we had 8, this would be length 5, the 3 would be index 1, length 5 minus

index 1 would give us 4, so we'd see that 8 has 4 values.

So what we would do is then do num or smaller count of that num that we're currently

looking at equals remaining values.

And one thing that I see right now is that we're going to get an error when we get to the

last index, because i plus 1 will not be defined, so I'm actually going to switch this up again

and actually do for i in range length of sorted num's just so that I can actually go

until 1 less than the total length, so that i plus 1 is always defined.

We always know that the smallest number will be 0 less than, so we can add that at the

the end, so a smaller count of the last index, so we could just do sorted num's negative

1 equals 0, so this is kind of the last case, okay, so for i now we need to define num,

so num equals sorted num's i, and if we wanted to be very kind of neat about this we could

say current num equals sorted num's i, next num equals sorted num's i plus 1, then we could

change this to if next num is less than the current num, we want to do this.

Now this, the one case that we want to think about is what happens when we're iterating

through our list, we go 8, 3, 2, 2, 1 and we get to a situation like this where 2 and 2 are

the same number. Well in this case what our code is already actually nicely factoring in but it

might not be intuitive that it's doing this is if the next num is not less than the current

num, then we're basically going to skip over it because we really only start counting when

the next number is in fact less than the current number, so every 2 here will have the same value

1 number less than it, and ultimately that will be added to our dictionary right at this last 2,

so we could have 100 2's but that last 2 is going to define how many numbers are after it that

are less than it. So we've now created our smaller count dict and then the final thing is to

just iterate over our smaller count dict, so for value in smaller, I guess we want to iterate

over our input, so for number in num, we want to create an output list, oh and so for num

num and num, we want to replace every num, we want to do output, dot append, the lookup of the

smaller count of the number we're currently looking at, run that code, I didn't return anything

Oops, and we also have an error, oh this is current num, gotta make sure that we don't, we change

if we change a variable name we gotta change it everywhere, and now we're getting nothing

because we're not returning anything, return output, accepted, look at that and I'm feeling confident

it again and so I'm gonna go ahead and submit, and look at that, that's crazy, so that this new

solution we just implemented, we're not doing n squared time complexity anymore, we're gonna be

ultimately bottlenecked by how long this sort takes, and if you know anything about sorts,

typically sorts are upper bounded by time constraint of n log n, so o of big o of n log n is

kind of time constraint with this sort, I don't know exactly what sort this sorted does by default,

but you can expect o of n log n for time complexity there, so hopefully this answers a bit more

complex, but as we can see it 10x speed up, upgrades are our solution, so this is in an interview

setting, this is the type of thing that you kind of work to get better and better, and there might

be even more optimal solutions, but I'd be pretty happy with this n log n solution, so retroactively

I wanted to check to see if this was an optimal type solution, I went to the discussion, and I

ultimately saw this Java solution beats 100% o of n, so they somehow found a way to do o of n,

and ultimately I'm not gonna go through this, you can look at it if you want, it's pretty

easy to find from the problem statement, but what we missed when we were looking at this problem

is the constraints are very important, if you're in an interview setting, always ask about the

constraints, you know how big can the numbers in this number list be, how many numbers can there be,

because that can influence how you design the solution, and ultimately what that very quick solution

did that was very highly upvoted in the discussion is they noticed that the numbers are always

gonna be between 0 and 100, so ultimately as a result of that, you can kind of do smarter things

with counting, because the numbers are, there's not infinite number like infinite possibilities

of what numbers you can choose, so you can ultimately like store everything in a bucketing

solution, and that discussion problem has that, and speed it up further, so constraints can be very

important here, always try to, and I'm guilty here, but it's always good practice to get more

information about the constraints. All right, next let's do a problem 704 binary search, so if

you're familiar with binary search, it's probably pretty straightforward what this question is

asking you to do, if you're not familiar with binary search, then this is a great example to kind of

help you learn what binary search is, and ultimately binary search is used in a lot of these coding

interview questions, so it's always good to be kind of thinking of this whenever you're trying to

do a problem that you need to find something inside of like a bigger array, binary search pops up a

so ultimately what are we trying to do? Well, we're given an array of numbers, and we're given a target,

and ultimately our goal is to figure out what index, or if there is even an index that that target

occurs at, so in this case we see that there is a target, and because it occurs at index 4, we return

4, in this second case, there's no 2 inside of this array, so whenever we don't see a number,

we output negative 1, so we could implement this in a very, very straightforward manner and just

kind of iterate over each element 1 by 1, and then if we see the number, then we return the index,

if we don't, then we return negative 1, and that is a valid solution, and let's just type that

up real quick, the issue with this solution is it's you'll find out it's not optimal, so let's do

for i and range length numbs, or we could do something like for i common num in enumerate numbs,

let's say if num equals equals target, then ultimately we want to return the index that that happened

else, if we get through every one of these items in the list, and we don't see a number that

equals target, then we can go ahead and return negative 1, and I always forget, I think it's index

common num when we use this enumerate keyword, this is supposed to be the index, this is supposed

to be the actual item in the list, I always forget the order, let's run code and see if this works,

it looks like it works, I'm actually very curious if this will be an accepted answer, it might

time out on us, so it was accepted, but it is not optimal because ultimately this problem

is the key to this problem is that this is sorted, so is there a way instead of iterating over

every number and figuring out if our targets there, is there a way that we can do this in a more

efficient manner, and this is kind of the crux of binary search, so if this isn't immediately

come to you, don't worry, like this can be tricky, but try to think, if the target is nine,

do we have to look through all of these numbers, so maybe take a second pause the video,

think about that, and resume it when you're ready to here, okay, so yeah, the key is that this is

sorted, so because it is sorted, well we can do in what kind of the root of binary search is,

instead of iterating over every number, let's just start in the middle, let's start with this five

or this three, our target is nine, so let's say we started with the three, is three bigger or

smaller than our target, well three is smaller, so ultimately we can ignore everything that comes to

the left of that three, because we know that it's also going to be smaller, so let's just focus on

these last three numbers, now we'll repeat the process, we'll hit the middle of the remaining

elements, and that is nine, and that's exactly our target, so the index of that position is what

we'll ultimately return, and so this is going to be kind of tricky to write and code, but let's

give it a shot, I think the best way to think about this as you start writing code is to think

of examples of how this might work, so let's say that we have the array of num that is equal to

negative one, three, four, six, eight, nine, twelve, fifteen, eighteen, and we have the target,

which is equal to nine, well how could we go about solving this, well we see that this has a length

of one, two, three, four, five, six, seven, eight, nine numbers, so that would mean that the first index

is always going to be, so our start index let's say is equal to zero, and our end index, this has nine

numbers, so because we start index counting at zero, that would be the end index would be eight,

and so our middle index would be equal to start plus end divided by two, which in this case,

plus end divided by two equals four, so that would give us zero, one, two, three, four, this is our

new kind of like our middle point, and we know that nine is bigger than eight, so what that tells

us is we can ignore all this stuff to the left, and so what we can do with binary search is basically

say okay our new start is going to be four, our new end is eight, still eight, and now our new middle

is four plus eight, which is twelve divided by two, which are going to be equal to six,

and that would give us zero, one, two, three, four, five, six, twelve is our new number,

well as nine, our target less than or greater than twelve, well it's less than in this case, so

we'll iterate again, our start equals four, our end now equals six because we're looking to the

left, and so now our midpoint equals four plus six divided by two, which gives us index five,

which also we see is the nine, so in this case we would return the five, if instead our target was,

so I'll say our mid equals five, that number equals the target, so return five,

if instead let's say our target was ten, well we get to the same point be between eight and 12,

but we'd see that our iteration of nine, our midpoint was less than ten, so we'd kind of like

repeat the process, we'd say start equals four, end equals, or I guess our start equals five now,

end equals six, and we see that if we try to like add those, and divide by two, our midpoint

point is the same as it was in the prior iteration, if we floor divide, so it doesn't quite work,

so let's get this out in code,

so I'm going to say start equals zero, end equals length of num's minus one, because if our,

we have nine numbers, the last index is one less than that, and so our first midpoint is going to

be start plus end divided by two, to be safe, because we might have an odd number here, let's

do floor divide by two, basically what we're going to want to do is, while our start

is, I'm writing in English, even though I'm talking code, while start is less than or equal to

end, let's continue this process, and I guess let's define our mid inside this for loop, so while

start is less than or equal to end, our midpoint is this, our number then is going to be

num's of midpoint, if target is equal to our number that we're looking at, then we want to return

that midpoint, that index that gave us that number, but if it's not, then we want to reset

our start or end to be kind of the new value, so if target is greater than num, then let's say like

we were here, well we would have to go look to the right, so we should shift up our start, so we'll

say that now start equals mid, else, and we can write this more elegantly, but we can do that after,

if target is greater than num, this is less than num, then our end is going to be equal to mid,

and then this for loop, we'll just go or this while loop, we'll go again until we hit this kind

of base condition, and if we exit the loop without ever finding a match, then we can return

negative one, let's see if this works, look at that works, and so if we wanted to be a little

bit more elegant here, we could have said that this was like lf, and this was even an else

conditioner, we could do another lf, so basically it doesn't try to run these statements if you

enter this statement, hopefully that kind of makes sense, binary search is very well documented,

so if this kind of quick code solution didn't make sense, then you definitely can find resources

online that can provide more I guess, algorithms type high level intuition about binary search,

let's go ahead and try submitting this, and I hope we didn't miss like an edge case or something,

we should be going kind of slow, time limit exceeded what did we do something silly,

as there any case that this, I feel like we might get into a never ending loop.

All right, so what I'm thinking about is it doesn't really make sense for us to just start the new

start at the exact midpoint, or the end at the exact midpoint, because we've already looked at

that midpoint, so we don't need to include it in our range. So let's just go ahead and make that

the start is whatever the midpoint one was plus one, and the end, if we have to change that,

it's whatever the middle point was minus one, so that you kind of are shifting in the right

direction. So like if we found the midpoint was eight, then we do eight, the index of eight plus one

to get just this instead of looking at eight again in our range. So I think that that hopefully

we'll solve the time limit exceeded, because basically I think we're getting into an infinite

loop, and that's why it wasn't working. So I'm going to try running the code again.

Accepted, submit it, cross our fingers. Accepted, look at that. And honestly, it didn't run that

that much faster than our first solution, but honestly, I believe that that's probably because

of the test cases that they used for this problem, but feel free always to look at the solution.

So let's see what the solution actually does. It seems like pretty similar.

There's even a video solution here.

Yeah, it looks pretty similar if just kind of some slight nuance.

Yeah, and instead of using a time complexity of O of N that we did originally, now it's O of log N,

cool. All right, we're going to do 409 longest palindrome.

So the question here is, and if you don't remember what a palindrome is, it's something that's the

same forward as backwards. And basically what we're trying to do is given a string, we want to know

how many digits would be the longest palindrome in that. So we have A, B, C, C, D, D, and we see that

the output is seven because the longest palindrome would be D, C, C, C, C, D. So we need to write

some code that figures this number out. Okay, so how should we think about this?

Well, if we think about palindroms, they have to be the same in, you know, going left to right

as right to left. They have to be the same forward and in reverse. So really, they need to

be flippable. And what that tells me is that really the digits that we use in it

need to all be even except for whatever that middle one is, if there is a middle.

So really, if we just count the number of characters in the string that have even number of

occurrences, that's going to be really the longest palindrome. Plus, if there's any odd numbers,

we would just do a plus one on that. So it should be a pretty straightforward counting problem.

Let's use a dictionary to do this counting. So we'll say character count is an empty dictionary

and what we can do is for character and string. We want to do character count. Well, if we haven't

seen this character yet before, we'll want to do equals character count dot get of the character.

But if we haven't seen it before, we'll want to set it to zero and then we can do plus one.

This lets us feel gracefully in case character is not already in the dictionary. Whereas if we did

something like this, it would error out because characters not in the dictionary and we're trying

to reference it, but we're able to set it like this. So that's why we're using the dot get because

if it doesn't find character, then it defaults to zero and then we can plus one to that. Okay.

So that would count all of the characters in the string. And so what basically we're going to want

to do is our final count will say is equal to zero for character in character count. Well, if the value,

so if the value is that's going to be character count of that character, if it's even so mod

two equals equals zero, so if it's evenly divisible by two, then we want to go ahead and add to

our final count all of those characters because they all could be included in a palindrome because

you could use half of them in the front and half of them in the back. So the equals character

count the character. All right. So that would add all of the even number characters. And now we

just need to count the odd number of characters. Well, we only can count a single one of them because

only can it be in the middle to create a valid palindrome. We couldn't have them on both sides.

So here we just really need to have some sort of Boolean that tracks whether or not we find a

character count that is odd. So what I'm going to say here is just an else. So this would mean it's

not evenly divisible by two. Then basically we just want to say that odd is present, I'll say,

equals true. And we can set out value odd is present, equaling false initially. And all we're going

to do with this variable is at the end once we've iterated over thing. If we did find an odd number

of values, we'll just add one more to our final count. And then we'll return that final count.

Let's give this a shot on code. That seemed to have worked. We can try another test case. It's always

good to use these short strings as test cases because you always can get errors on the short ones.

And also do we know that the string length is always between, yeah, it always has to at least be

one. It can't be an empty string. That's another good edge case to think about. So now we have the

three examples that gave us. Oh, wrong answer. No. So BB was wrong. What was BB wrong? It should have been

count two. Oh, oops. If why did I not do this? If odd is present, then we want to increase the

final count by plus one. So the last one odd wasn't present. So we shouldn't count that. Let's

run it again. Cool. Let's submit. Come on. Wrong answer. CCC. Oh, interesting. This is an

interesting edge case. It could be all of the same characters. So this is what happens. If you're

not careful, you should be thinking about the different edge cases. And I was running, you know,

I was jumping the gun there. So let's think. How do we incorporate this one?

Okay. So we need to add one more if statement to our condition. Basically what we want to do is

if it is divisible by two, then we add the exact character count. L if it is, or I guess else,

if it's not divisible by two, then we would want to do final count plus equals character count

the character minus one. So how does this work? Well, if there's three Cs, right, then that is not

divisible by two. So we wouldn't, we'd skip this if statement and we'd enter this one. Well, we can count

the two Cs because that is a palindrome. So we could add two there instead of three. That's basically

what we're doing right here. And then the last thing is, is there is an odd value present in this case.

It is three in general. So that remaining C, we can add it back in using the same if statement we had

originally. And then return the final count. So this should work. Look at that accepted and submit.

I think that will be good this time. Accept it. Yay. Cool. And it runs faster than 88.20% of Python

three submissions. Memory usage is not great though. Let's think. What is the runtime here?

Well, we count everything, every number in the string. So that would be O of n. And then

we iterate. Oh, so yeah, we count all that. That's O of n. And then we just iterate over our dictionary.

So that's also O of n because we could have n different unique characters. So really our runtime is

bounded by O of n. And that's really the best you're going to get because you do have to kind of

look at every character to figure this solution out. But we could do better probably in the memory

usage department. But I'm happy with this solution. Next, let's do 1561. Maximum number of

coins you can get. And as always, it's linked in the description. So in this problem, there are

three n piles of coins with varying size. And you and your friends will take turns taking one of

the piles of coins. And so in each step, you'll choose three piles of coins. And it's kind of,

we don't know which piles of coins we'll select. Of those three piles that we choose, Alice,

we'll always pick the maximum number of coins. Then we will pick the next maximum number of coins.

And then our last friend Bob will pick the remaining pile. And then we repeat until there are no

more piles of coins. So fairly straightforward problem. It seems like let's look at an example.

So we have the piles two, four, one, two, seven, eight. And we kind of are just randomly choosing

triplets. So like you can imagine any pair of three we start with. So if we picked two, four,

one is our first triplet. Alice would pick the four. I would pick the two. And then Bob would pick

the remaining, the one. So given that we could pick any of these three at any time, what is the

maximum number of coins that we could ultimately get? And so as we see in this example, like we

chose two, seven, eight first, we'd get the seven. And then the next triplet, one, two, four, we'd

get the two. And our maximum would be nine. There's no way for us to get any better than that

based on how this is structured. All right. So when we're thinking about solving this problem,

let's start with kind of a very, you know, simple solution. What would work? What is the easiest

thing we can think of that would work? Well, I'm thinking about that. I'm thinking about, okay,

if we just looked at every single pair of three items, like all the different combinations of

triplets and then just took the max sum based on all those different combinations, then we get

the solution. But we got to think about if that's practical. There are so many different ways we

could break up even just like six items into triplets of three. I'd have to do some kind of

combinatorics of the word to figure out the exact count of that. And I think in this case,

it'd be six choose three, which would give us our count. But in like other cases, longer cases

would be like nine choose three times six choose three all the way down until you, you know,

you have no triplets to go to. So that would add up really quickly. And it scares me,

especially given that the length could be 10 to the fifth in total. So doesn't seem like counting

all the different triplets in like summing that way makes sense. So what else can we do?

Well, I think the key thing to think about is that we just really care about the maximum number

of coins which we can have. So all we care about is the most optimal case. We don't have to care

if that's probabilistically likely that this happens. We just need to know in the best case scenario

what happens. And so if we're thinking about the best case scenario, we would pick the, we'd get

triplets that always have like the max number and the second max number and then the lowest number

and always get that like any triplet always would get that second max number of the remaining piles.

So as an example, what we could show is that let's take this list piles. So we have two, four,

one, two, seven, eight. Well, if we wanted to figure out what's optimal and it might actually work

better to take like this longer example, just to really demonstrate this property, take this,

well, I think we should sort it. So if we sorted this, we'd get one, two, three, four, five, six, seven,

eight, nine. And so what would be the most optimal thing to happen? Well, the most optimal thing

would be, okay, maybe our first pairing is has the eight and nine because those are the two

largest numbers. And then it has the smallest number for Bob to pick. Next iteration, we'd keep

going. So hopefully we'd have the next two biggest numbers, the six and the seven, and then maybe

like the smallest number for Bob to pick. So that would leave us with the biggest numbers remaining.

And then finally on the last iteration, our last triplet would be three, four, five,

it would be these three numbers. So why would this be optimal? Well, if we ever change one of

these numbers, so let's say like we put the seven in this spot instead of how we structured it,

well, that would mean that Bob would get the seven and ultimately that would reduce what we

could ultimately acquire. So we always want Bob to get the smallest and we always want to have

the opportunity to get the second biggest thing remaining. So that's why we'd like these triplets.

So really what we have to do is just sort this list and then iterate two from the right and one

from the left and keep going until we have no more items remaining. And then just add up

all of the second most from each triplet, like as we're doing that, just keep adding the second

biggest item in each triplet. So let's implement that in code. And let's think about also just

real quick runtime. Well, this would be bottlenecked by how much time it takes to sort this sorting

takes O of n log n. So n in this case would be the piles length. So you take that to sort it and

iterate over this. We could do that in just O of n. So our total runtime would be O of n log n.

All right, so what does that look like? Well, we could say sorted piles equals sorted of piles.

That's a good way to just do this in O of n log n. It's built in Python keyword.

Then so what we want to do is let's keep track of our index. So for i in range, the number of

iterations we're going to do in total because piles is 3n. We see 3n piles of coins. The total number

of iterations we want to do for grabbing three to time is just n. So let's do a length and also

given our constraints, we see that we know it's always going to be divisible by 3. So we can go

ahead and do length of piles or we can do sorted piles. It doesn't really matter,

divided by 3 to give us how many times we'll have to iterate. And so for each iteration,

our triplet is going to be sorted piles of i sorted piles of length of piles

because our last index, let's think about our last index. If we have length piles,

then our last index is length piles minus one. So I'm going to define this as a variable.

We'll say end index equals length piles minus one so that in this case we'd want to go

our next part of our triplet would be that end index. And then we also need a factor in

our index. So we apply something like minus i times two because we're looking at two items

each time on the right side when it is sorted. And then finally our last item would be sorted

piles end index minus i times two. That same thing is before minus an additional one,

just to get that offset one. So that would be what's consisted in our triplet.

I can make this a little smaller. You see it looks like something like that. But let's think about,

do we need every item in this triplet? I don't think that we do because we only care about our own

individual pick. So really all we care about is this last pick right here because that's what

we're going to take every time. That's what we're going to get based on these rules in the problem.

And I think that these last two things are right. We'll probably have to play around and print

some stuff out to be sure. But we're going to go ahead and say our value equals instead of doing

this whole triplet, we'll just do this last part. So I'm going to just copy this and paste that in.

And so let's think. So on the first iteration, our index index is the last item in the array.

So if we had six items, our end index would be five. Five minus i times two. i is zero in the

first case. So that's minus zero. So we're still at five minus one would give us four. And that

sounds correct. Next iteration would be, I would be one, that would give us five minus

two, which would be three for this index minus one, which would give us this one right here.

Assuming that this is sorted, I'm kind of just using this array down here in the bottom left,

just to show index and think about my head, the index values here. So our value,

equals this. And really what we could do is just keep track of account. So our count equals zero.

And so, or maybe I could even say our value equals zero. And so every time we get a new item in the

triplets, we do plus equals our value. And so once we get through this iteration, we can just go ahead

and return our value, I believe. Let's run code.

Float value cannot be interpreted as and integer. Why is that giving me an integer? I want this

to be an int. So I'm guessing this division is being interpreted as a float for whatever reason.

We might be able to do a floor divide to give us always an integer. Not positive. Let's try.

It should always be divisible. We know that from the constraints, but I guess it's just kind of how

Python implementation works here. Okay, we get that working. We can also try these other test cases.

Let's try two, four, five. And let's try this one right here.

Both of those are working. Cool. So I'm thinking that this solution works.

And realistically, you know, we could even make this smaller number of values, but I think it's

fairly neatly written out right now. I guess the only confusing part would be this what we're

taking it from. But hopefully the steps that I walk through to get to this point make sense.

with that whole triplet idea. So let's go ahead and submit our code.

Accepted. But it is kind of slow compared to some solutions. So I wonder if there's something

that we're missing here. I'm thinking maybe just the way we're iterating over here is kind of confusing.

Or maybe we have to do these calculations every time. So right now our solution is O of n log n.

Is there anything we can do better? I feel like n log n is realistically like one of the best you

can do unless you really want to like do something clever with a bucketing type solution

and knowing that your piles can only have range from one to 10,000 here.

Let's look at the hints. Which pile of coins will you never be able to pick up? Well,

it's from the left. I think we've already covered that in number two.

Okay, yeah, we covered both of these things. I'm just wondering about the implementation.

Honestly, I'm happy with this solution. So let's just look at the discussion to see if there's

anything better.

This scene is the exact same as what we're doing.

Yeah, so if we look at this solution, realistically,

what we can do is just do a smarter summation of things. Instead of doing a for loop, do something

like this. And that will be quicker. But the algorithm all seems the same.

Okay, we're going to do 1472 design browser history. And I really like problems like this.

From my own experience, if I'm interviewing candidates, I love to give them a problem like this

where you're actually building out a class or something. Because it really is more of a

realistic feel for what their software engineering skills are. So I usually in an interview

process would give one of these types of problems and maybe one algorithms type problem to get a

full feel. But I'd probably be more closely thinking about how they work on their classes and

whatnot than the algorithms questions. The algorithms question tells me that they're a good problem

solver. This type of question tells me that they have good software design principles.

So that's good to keep in mind with a problem like this. Okay, so what does this problem say? Well,

we're we have a browser and we always start on the home page. And in this browser, we can also

visit another URL as well as go back and forward in history, a certain number of steps. And so

we need to implement all of the details there that allow us to have a browser such as this. So

we're implementing what allows us to kind of keep track of the browser history. So what we need

to do is first and just be able to initialize it with string home page that gives it that first

item in the browser history. We need to be able to visit new things which clears up all of the

forward history. So that's good to know too. We need to go back a number of steps. So the couple

details there and it needs to be able to go forward a couple of steps until it returns to the most

last item that we've looked at the most recent item. The examples here, I would say like

probably did details here are going to be more clear than looking at the example.

Basically behind the scenes how they're testing this is using info like this.

But kind of following this trend can get you understanding what's going on.

So let's just kind of work off of this and see how we do. And then if we need to look at the

examples a little bit more closely we can do that. So I mean obviously it makes sense to start

with this initialization step. How do we get it to be able to be initialized with a home page?

And so let's keep the start thinking about the different data structures we might need in a

problem like this. The biggest thing that I'm thinking about is that we need to keep our history and

something. So it makes sense to me to keep that in an array and Python. So I'm thinking right here what

we'll do is that we'll initialize this home page into something that we call history. So we're

going to say self.history equals a list with just the home page in it. That's how we're going

to think about history. And now all these other functions in the class method they need to access

self.history and do certain things with it accordingly. So visit what does this visit do?

Well visit would append to our history on top of it. So what we would want to do here

is just do self.history.append whatever the URL is that we're now visiting.

Another thing to keep in mind here is that it says that it clears up all the forward history.

So if we are at certain index in this history then we know we should clear all the

so let's say we had like site one site two after the home page and we are currently on site one

and we wanted to visit a new URL. Well that's saying that this would be forward history and it's

saying that if we were on site one then we would want to go ahead and just say that this is like

the new URL and we'd have to clear everything. Let's think about that. How do we want to implement

that and clear all the stuff? Well I think what might make sense is to also keep track of our

current index. Maybe you would make this like a private method like current index. Sometimes you use

that a little underscore here to kind of signify this is like private to the browser history.

It's up to you how you want to go about this. I'm going to just say self.current index

equals well it's going to equal zero to start with just the home page. So when we append our URL

our new current index is going to be whatever it was so self.current index equals plus equal one

because we're going to take whatever we had before add one to that. We might not want to append

this URL right away because that would be a pending it on top of existing history. So instead

maybe let's say we update the current index first and then basically say that our history is now

equal to what it was before. So self.history from the start. So from zero to whatever the current

index is now. So self.current index. So that will allow us to keep everything that was already

there because and then we can go ahead and do self.history.append the URL. So I think this

would capture then the two things that we need to do here which is clear up the forward history

will do that first and then append the new URL as the head of the forward history. Now let's do

back. We'll back would just move our current index. So basically what we want to do here is do

self.current index is going to equal and let's be clever here. We can move steps back in history.

If you can only return x steps in history and steps is greater than x, you will return only

x steps. So it's basically like we can't go beyond the zero of index when we're going back.

So what we can think about here is we could do return the max of zero and steps are of and self.current

index minus steps because if we were we had a list of let's say site one, site two, site three,

site four. And let's say we were on index three and we wanted to go back two steps. Well then in

this case we would go index two, index one. That would be two steps. This would return one,

max of zero and one would allow us to get that right current index. So I think we're good there and

we don't have to update the history at all in that case. Similarly for forward we can do self.current

index equals, well it can't go farther than the max index. So we could say the min of

whatever the length of our history is. So self.history.

And then the last index there would be that minus one. Otherwise we would go just like in the last

one we do self.current index and this time we would probably plus the steps. Plus steps.

If I make this a little smaller it would be more nicely on a single line and you could change up

these names if you wanted to. But I honestly think okay and then these two steps were back and

forward we need to return the current URL that we're at. So that would be return self.history

of self.current index and this would be return self.history self.current index.

And this returns nothing and this is just the initialization method. I think that this is good. Let's

give it a shot.

Accept it. Look at that. Nice. And I think we can go ahead and submit.

Accept it. And it runs with pretty good memory usage pretty fast. And this type of a problem

as long as your solution is not particularly slow it's not doing anything obnoxious.

I would be more concerned about making this nice and readable than trying to

make it highly performant. And you would want to explain to whoever's interviewing you

like this is what you're doing. This is why you're doing it. If you find that performance is an issue

you know you could do some additional stuff to kind of speed up things. With that my kind of final

recommendation here would be comment your code as necessary or just clean up things as necessary.

Is this if someone didn't hear you walking through the problem could they understand what you're doing

here? And for some of the things that I implemented I think that it's pretty straightforward but

there might be some details here that aren't clear without an explanation. So like the one

line I'm really thinking about right now is that it's not immediately clear to me that this

clears forward history. So maybe I'd add a comment like clears forward history here right here

and then it would be a little bit more straightforward that okay you know you're adding one because

we're visiting a new site we're clearing the forward history and then add the new site.

Hopefully this probably made sense. Hopefully the solution made sense. If you have recommendations on

how this could be improved definitely let me know in the comments. And also just keep in mind like

this is another like designing classes and object-oriented programming. This is another great skill

set to have in an interview setting no matter if you're software engineer data scientist etc.

It's really nice to be able to see that someone can structure code in a succinct and understandable way.

So usually you're gonna have to do a problem like this as well as an algorithms type question.

And you know the better you can do in both areas the better case you're making to the interview

or that you're a good hire candidate. All right let's do problem 1110 delete nodes in return

forest. This is a medium problem. So we're given the root of a binary tree and each node in the

tree has a distinct value. After deleting all the nodes with a value in some list 2 delete we are

left with a forest and then our goal is to return the roots of the trees in the remaining forest

and we can return the result in any order. So to make that clear we see that we have a tree that

looks something like this. We see that each of these nodes has its own unique value and what we're

asked to do is delete a couple of those nodes. Particularly in this example 3 and 5. So it's

basically saying if we deleted node 3 and we deleted node 5 what are the resulting trees we're

left with. So as we can see if we delete a node 3, delete a node 5 we'd have one part of the tree

that would be 1, 2, 4 and this part of the binary tree would be null. And then because we deleted

that 3 you can be left with these two just single node roots 6 and 7 and that's what's our output.

So this is what we're trying to do in this problem. So when we're doing any sort of problem that

involves trees usually one of the things I start thinking about is traversing through the tree.

There's a couple different ways to do this. You can kind of do like an in order traversal

which would be like 1, 2, 4, 1, 2, 5, 1, 3, 6, 1, 3, 7 which would be an implementation of depth

for search. But in this case I think that really we want to work top down so something like 1, 2, 3,

4, 5, 6, 7. And the reason we want to work top down is I think that it'll be easier as we delete

nodes to kind of just be going from top to bottom and not have to like keep track of those deleted

nodes throughout the entire process. So how would we implement breadth for search? That's kind of

of the first thing I'm thinking about it. So I think when we start writing this solution I'm going

to just start with writing out something that could go through this entire tree and then we'll

modify that breadth for search to delete nodes and kind of return of result accordingly.

You can implement breadth for search using a queue which means that the first nodes you put

into some sort of queue are the first nodes that you take out of that queue. So we can imagine

defining some sort of queue and well to start off the queue would just be whatever root we have

so we could say root and then we could do something like while queue and so this would mean

it's basically while queue is not empty. We can pop off the root nodes so our node is going to be

equal to queue dot pop and then we want to look at for this given node we want to look at its left

child and its right child. So we could imagine we would add onto our queue the left child as well

as the right child. And given this is first and first out we don't want to pop off the end

really we want to pop off the beginning so that for future iterations we're always making sure we

grab the thing that was added to the queue first so we'll do we can do that like this and Python

okay and basically let's see something I think if we printed node dot value I guess it's node dot

value looking at this class implementation up here node dot value we could see that this would be

like a valid traversal of the tree so I'm just thinking about traversing the tree and then we'll

modify our breadth for search and this is typically with these tree problems you're taking some sort

of thing that you know about that data structure and then modifying it to fit whatever the problem

requests so let's just run what this does so as we can see for the example we're given here

this does go ahead and print 1234567 so that's good to know now what do we need to do

really the question is what do we need to do to change this so that we can delete nodes

and so to do this I would think about what items do we need to keep track of well one thing that

we need to keep track of is all the distinct roots so we'll have to implement that into our code

somehow and then the other thing is for a specific tree we need to modify that tree so that

any deleted nodes get updated in that tree accordingly so like if we had the node one here we need

to make sure that we said set node like the right node of this one to be none because it gets deleted

here so there's kind of two different tasks going on let's take care of just updating a

existing tree first so basically what we can think about is we're not going to automatically

append node.left or node.right to our queue we're going to first check to see if

node.left or node.right even exists in the first place so we can do something like

if node.left so if that's not none then we want to keep going down that part of the tree when

it continue our search so we can do a queue so this is basically what we're already doing before

but it's just we're adding an additional check that make sure that we actually have that

child defined so queue.append node.left and then the second thing we want to do is

for whatever tree we're looking at so for the tree with root we want to just make sure that

we should be counting this node that we're traversing down as part of that original root tree

and the only way we wouldn't include it is if that node happened to be deleted so let's say

if node.left.val is in so in two delete

well then we would want to set node.left equal to none so basically for the root node that we're

looking at if we find that its left child should be deleted then we ultimately just want to

remove that from the tree because now we've gotten to like a disjoint root or disjoint node

so we can repeat that with node.right so I'm just going to copy and paste

so node.right queue.append node.right if node.right.val is in two delete then node.right

equals none so that's just basically seeing that's basically taking care of this aspect of

things we are properly setting something in the case that we have deleted nodes so if I run the code

here and then I guess once we're done with the queue we could just

let's just to start return root and see how we've updated the tree

so as we can see by doing this so as we can see by doing this right here

we've updated the tree properly like we like we have here so let's look at that one our time

but now we need to figure out how do we capture those disjoint nodes so that's the big question

well maybe what we should do is let's keep track of our output kind of as a global parameter of

this class so I'm going to say when there's initialized this class to have an empty output list

by default and basically anytime we call this delete nodes method let's add

the whatever root we're looking at so in this case this root so self.output.append root

and so what do we accomplish by doing that well what we can smartly do is imagine that we had

in our nodes to delete from this tree up here in the example we were told to delete node 1

well if the node we were looking at was deleted then we would know we would have root nodes at 2 and 3

assuming that 3 wasn't actually in this list just assuming one was the only thing we're deleting

so basically you know that 2 and 3 are like the root nodes of the disjoint trees

well what we can do is basically another if statement so if node.val

in to delete so basically this is a different scenario if that value is in to delete then let's

recursively call delete nodes on the left and right child so we have to call self.delete nodes

on root her node.left and self.delete nodes on node.right and because of the way the functions

define will also pass in to delete to both of these things and so what we get with this recursive

call to delete nodes is that now the left and the right nodes of a deleted node will get

appended to our output and I guess one thing we should change right here is we need to only

append if root.val is not in to delete

okay so now if we look at our solution if we I think just run this

uh none type okay I think one thing we also need to do is double check that

node.left is defined and double check that node.right is defined before we try to call that

recursively otherwise we'll get an error when we try to do something like this

okay okay oh and then we need to now instead of returning root here we would want to do self.output

we want to return the output so return self.output

look at that we got it um

I think that looks good basically if we're need if we're looking at a node that needs to be

deleted then we want to just add um the left and right nodes as like new distinct roots and we

recursively call the function on that otherwise we just keep looking at the the tree the root that

currently examining and just keep adding things and just updating that existing tree accordingly

to get something like this so let's go ahead and submit this

oh no wrong answer hmm okay so we see here in this example we get an extra five node

that we shouldn't so that tells me that something is getting a pended twice for whatever reason

I think it's basically because we shouldn't both call a recursive call and continue this process

so I'm thinking if we add an else statement and append these inside I think that will fix

things so that we don't traverse down on the left or on the right multiple times when we've done

it already here

accepted

um not great um memory usage or runtime but let's just let's let's figure out what our runtime is

here so the way that we're doing this is we are looking at the root node we're doing both for a

search we're doing a modified breaths for search and breadth for search is going to have

a runtime of the number of edges plus the number of nodes and in this case it's a one-to-one

correspondence so it's really just a runtime of how many nodes we have so you could think oh

then and even though we're doing this you know I guess the thing I don't love about this solution

is that there's a lot of if else type stuff I guess one way to I mean it's not terrible

I think it's readable

I know that this solution is oh of n because we we modified that breadth for search so I'm happy

honestly I feel like most of these answers will just be like slightly smarter versions of what we

have here so I'm fine not changing things what I'd recommend is feel free to go to the discussion

check out like the top solution this guy lead 215 he's pops up all over place he does a great

job explaining these problems

and honestly this looks very similar to what we're doing but it's just being a little bit smarter

using this helper method instead of what we're doing with if else is so I'm happy with our solution

all right that's all the problems we're going to do in this video hopefully you found this useful

if you did enjoy it it would mean a lot if you throw it a thumbs up and also subscribe if you

have it also I just created a new second channel huge announcement right now but I'm going to be

posting a lot more frequently on that channel and I'll probably be doing a lot of these types of

problems so if you enjoyed this video definitely check out the second channel I'm going to start

posting on that once I hit 1000 subscribers and I will definitely take requests for additional

problems I could solve there whether that be lead code problems or problems from another site

if you have any questions about the contents of what we did in this video let me know down in the

comments but until next time everyone peace out