10 Common Coding Interview Problems - Solved!
10 Common Coding Interview Problems - Solved!
Preparing for coding interviews? Competitive programming? Learn to solve 10 common coding problems and improve your problem-solving skills.
💻 Code: https://gist.github.com/syphh/173172e…
✏️ Course developed by Inside code. Check out their YouTube channel: / @insidecode
⌨️ (0:00:00) Introduction
⌨️ (0:00:37) Valid anagram
⌨️ (0:05:10) First and last index in sorted array
⌨️ (0:13:44) Kth largest element
⌨️ (0:19:50) Symmetric tree
⌨️ (0:26:42) Generate parentheses
⌨️ (0:37:03) Gas station
⌨️ (0:50:06) Course schedule
⌨️ (1:06:50) Kth permutation
⌨️ (1:20:13) Minimum window substring
⌨️ (1:47:46) Largest rectangle in histogram
⌨️ (2:10:30) Conclusion
🎉 Thanks to our Champion and Sponsor supporters:
👾 Raymond Odero
👾 Agustín Kussrow
👾 aldo ferretti
👾 Otis Morgan
👾 DeezMaster
—
Learn to code for free and get a developer job: https://www.freecodecamp.org
Read hundreds of articles on programming: https://freecodecamp.org/news
Content
0.08 -> In this course you'll learn how to solve
10 Very popular coding interview problems,
5.04 -> and you'll learn the theory behind the solutions,
so you'll be better equipped to solve other types
10.64 -> of problems as well. We'll come to the 10
popular coding interview problems course 10
16.32 -> well chosen problems that cover different
algorithms and data structures topics
20.72 -> to increase your knowledge
and prepare for interviews.
23.92 -> Please try to solve before watching the solution
prepare yourself and see you in the first lecture
36.16 -> Welcome to this video, where we will solve
the first problem of this course valid anagram
40.96 -> acquired easy problem compared to Knucks wants we
are given two strings s one and S two and we are
47.92 -> asked to check if their anagrams. Two strings are
anagrams if they're made of the same characters
54.08 -> with the same frequency just in a different order.
For example, with a string standard and garden,
59.76 -> we take one of them will rearrange its
characters and we get the other one.
65.6 -> How are we going to solve this problem? We know
the two strings are anagrams if they have the
70.48 -> same characters with the same frequency. So what
we can do is to calculate the frequency of each
75.36 -> character and as one, calculate the frequency of
each character in s two and compare the results.
82.16 -> But what structure do we use to do so we can use
an array where each cell represents the number
87.2 -> of frequencies, they all start at zero, then for
each character in the string will increment the
92.48 -> corresponding cell. This solution is suitable
when the alphabet is small, while the number of
98.8 -> possible characters is not big. For example,
if the strings can only be made of lowercase
104.08 -> alphabetical letters, would need an array of 26
elements, it's fine. But it's not necessarily
110.24 -> the case. They can contain all the characters.
And we have 1000s and 1000s of existing possible
117.12 -> characters, the array would take a lot of
time and space to create it and traverse it.
122.48 -> The best structure for our problem is the hash
table structure that maps unique keys to values.
128.8 -> In our case, the key will be the coke
to other values number of occurrences.
134 -> For example, if you have nameless and salesman
whose name was we get this hash table.
138.96 -> And the salesman we get this one. Do they have the
same keys with the same values so they're equal?
145.76 -> It means that nameless and salesmen are anagrams.
152.08 -> Encode who first showed that both strings
have the same length, because if they're not,
156.32 -> it's impossible for them to be anagrams. Then who
grid our two hash tables, and we start to our C
164 -> for each character and as one if the key is
already existing. And for one who does increment
169.6 -> else, we created a new set its value to one than
for us to same logic, but with freq. Two. And
177.12 -> now that we filled them with each other, they
have the same values. For each cane frog one,
182 -> if it doesn't exist in frog two, or for
quality isn't able to frog to off key,
186.48 -> return false. It means that either the character
of us one doesn't exist in our stew, or they don't
191.92 -> appear the same number of times after the loop,
if we didn't find any difference, we return true.
201.04 -> And in Python, we don't ever need to
write all this because we have a class
204.88 -> named counter in collections module that builds
the table of occurrences just by passing the
209.28 -> string as an argument. And we can compare
dictionaries with the equality operator.
214.8 -> So in reality, who does return count
off as one equal to count off as two.
221.84 -> For the time complexity, in the worst case, as
well as to have the same length. Let's name it
227.28 -> as we're traversing N characters at most three
times, and Sujan. Inserting in a hash table
233.12 -> costs are one in average, got off, amp was off and
was off and we'll give some of amp on complexity.
240.88 -> And for the space complexity, we have an hour
for each table because they can contain up to n
245.92 -> keys each we got an often space complexity.
We still have another solution to discuss.
253.68 -> You have to know the two anagrams how
the same lexicographically sorted string,
258.32 -> for example, with nameless and salesman. If we
sold nameless, we get a ELMN s s. I will salesman
266 -> same thing. So in the second solution, who
do salt posturings and compare the results
272.96 -> in code, after the equal condition,
returns sorted as one is equal to sorted
279.072 -> as two. But sorting a string of characters
because of n log n time we're doing it twice
285.04 -> was after comparing. We've got an off n log n
time complexity. And for the space complexity,
291.2 -> we have often for the sorted result twice,
we'll get an off air space complexity.
298.64 -> Who's the end of this video? whistle
the valid underground problem,
302.64 -> I hope that you understood the ball
solutions and seen the next one
313.44 -> Welcome back to the course in this lecture
rule. So the first and last position problem,
318.56 -> you are given a sorted array of integers are an
integer target. And we're asked to find the index
324 -> of the first and last position of target and our
if Target can't be found in our return minus one
330.16 -> minus one. For example, if our is 245-555-5799,
and target is five, the author's would be to six
339.68 -> because the first position of target
is to, and his last position is six.
345.2 -> First of all, because the array is sorted,
all the elements with the same value will
349.44 -> be ages into each other. For example, here all
positions of the value five are consecutive.
355.84 -> It means that the first possible solution is to
start traversing the array from the beginning
360.48 -> for the first position of target, and keep
walking until finding the last position.
365.44 -> With our example, we have two four,
then five who found the first position
370.48 -> we can walk in, we have 5555. This one is the
last one, we found the N position, we turn them
379.6 -> in code, we start traversing indexes of our and if
our phi is equal to target, it means that we found
385.68 -> the start position. Now we keep walking while the
next element exists and is equal to target y plus
392.56 -> one is smaller than length of our and our five
plus one is equal to target increment i. After
399.12 -> the while loop. INR represents the position of
the last occurrence. This is why we return start i
406.96 -> and if the fall ends without
having returned the result,
409.84 -> it means that we didn't find target in
our at all return minus one minus one.
416.8 -> Know that it's possible to have sought position
equal to and position it happens when there
421.2 -> is only one occurrence of targeting our for
the time complexity on target exists, which
427.68 -> covers the part befores first position, third
sequence of occurrences and where it doesn't,
433.12 -> which covers a whole array. In both cases, which
covers almost add elements, where n is the number
438.88 -> of elements of our we've got a time complexity
of add a cost and space complexity because
445.68 -> we're just using n variables. This solution uses
linear sir, to give an off on time complexity.
455.44 -> Both the resorted so we can think of using binary
search. Let's try to use binary search to find the
461.76 -> start position. With binary search, you can find
the position of an element in a sorted array.
467.84 -> But here, we're not searching for any position
of target, we're searching for the first one.
474 -> R is the first position of target
if r is equal to target, obviously,
478.56 -> but also r of i minus one has to be smaller
than target smaller because the array is sorted.
485.52 -> So we will use binary search normally, but
to add a second condition before returning.
492.16 -> Let's try it with our example. Left and right
solid first and last element of our as usual.
498.24 -> Man, his left password divided by two, we get four
here is true that our four is equal to target,
504.56 -> but it's not enough our four minus one is
not smaller than target. So med is not the
509.52 -> starting position of target. But should you
go to the left part or to the right part now,
515.92 -> our have made is not created on target. So the
first position can only be in the left part
521.92 -> we continue made is now zero plus
three divided by two we get one,
526.4 -> our phone is smaller than target. So the starting
position can only be in the right part we continue
532.72 -> made is now two plus three divided by two which is
to have meat is equal to target and our male minus
538.64 -> one is smaller than target. So meta represents
the first position of target, we return it.
545.28 -> In code, we're going to first have an early
exit condition for the case where the first
549.12 -> element is equal to target with DACA know that
zero is the starting position returned zero.
555.68 -> By the way, in solutions based on binary
search, put as much early exit conditions
560.32 -> as possible to handle edge cases
and avoid out of bounds problems.
565.6 -> After it we initialize left and right
at zero and minus one respectively.
570.16 -> Zero and r minus one are the indexes of the
first and last element of R. Now while of is
575.84 -> smaller than or equal to right, we calculate mid
index is left plus rho divided by two. Afterward,
582.4 -> we have three cases the case where both conditions
are respected. where alpha is equal to target on
588.08 -> our beta minus one is smaller than target. It
means that made is a sort of position we turn it
595.12 -> second case are made is smaller than
target. It means that we're still before
599.36 -> the starting point. position. This is why we
take left and mid plus one to start again in
603.92 -> the right part. Else, it means that we exceeded
the consecutive sequence, or we're excited but
610.4 -> not other beginning. So start can only be in the
left part, we take rato mid minus one of the wall
619.36 -> didn't return the result is means the target
doesn't have an existing our return minus one.
626.72 -> Now we found this thought in the experts,
we still need to find the end index,
631.28 -> we can think of just walking starting from
start until we find the last position of target.
636.4 -> But it would ruin everything we
did, because in the worst case,
639.68 -> we need to traverse the whole array, which
results in an old Anton complexity same as
644.16 -> the first solution you guys did to find the
end index, we will also use binary search.
651.6 -> But the condition is a bit different from the
first time when searching for the start position
656.64 -> are of men how to be equal to target and our male
minus one smaller than target. And for the end
662.64 -> position, our med has to be equal to target and
our mid plus one has to be greeted on target.
669.12 -> Next element has to be greater because it
would mean that from the right, we're not
672.88 -> in consecutive Target Elements anymore, so the
actual position is the last position of target.
680.24 -> In code, we just change a few things, the only
exit condition occurs now when the last element
685.76 -> is equal to talk, it means that the last position
of target is in the last index of our n minus one
691.52 -> without a return. Then in the three cases, the
cases where we will turn mid is when our made is
697.76 -> equal to target, and our met plus one is greater
than target. For the two remaining ones, he won
704.4 -> our main is greater than target, then we exceeded
the consecutive sequence, we'll go to the left
709.36 -> part, right becomes mere minus one else, it means
that either will be for the consecutive sequence
715.76 -> or incited but not at the end, so and can only
be in the right part, left becomes mid plus one.
723.6 -> Now we have our fine salt function,
we have our Find and function,
727.44 -> we can move to the main solution function. First
of all, we have some early exit conditions,
734.24 -> who can identify at least three cases
where we can't find target role.
738.08 -> When the array has no elements, one target is
smaller than the first element. And when target
742.96 -> is greater than the last element in the last two
ones. Because the array is sorted, who can deduce
748.72 -> the target is not equal to all other elements. If
at least one of these conditions is true, without
759.28 -> the return minus one minus one health who co
found sought to give the stock position we
760.72 -> call font and to find the end position and wait
on start. And if Target doesn't exist in our
767.36 -> sorted annual have returned minus one
bath, we still got the expected result.
774.4 -> For the time complexity, we're using binary
search twice. And binary search has an
779.2 -> awful lot and time complexity because
we keep dividing the input size by two,
783.52 -> two times of work and gives us
all of log n time complexity.
788.72 -> Add for the space complexity, you'll get all
one because we're just using eight variables.
795.6 -> Before ending this lecture, I want to tell you
that if you're not comfortable with binary search,
800.32 -> you should really work on it because
it's a fundamental algorithm technique
803.84 -> that appears in many problems on this one, find
peek first bad version, and many other ones.
812.48 -> Lose Hello this lecture, I hope that you
understood the solutions and seen the next one.
824.32 -> Welcome back to the course in this lecture, we
will solve the cliff largest element problem,
829.12 -> you are given an array of integers and
an integer k. And we're asked to find
833.12 -> the K eighth largest element. For example,
if you have are equal to four to 9756713
840.72 -> and k equal to four, the output would be
six because the largest element is nine,
845.6 -> the second largest is seven, the third
largest is seven and the fourth largest is six
853.36 -> Firstpost possible solution that we may think of
is to remove the maximum element k minus one times
859.04 -> because after doing so, the next maximum
represents the K eighth largest element.
864.16 -> For example with our array K is four. So
we remove the maximum element three times
870.48 -> first iteration Max is mine we remove it, second
iteration Max is seven we move it third iteration
878 -> Max is seven we remove it now that we finished
the three iterations the maximum in the remaining
884 -> elements is the fifth largest element of the
original array, it six here who returned it.
891.44 -> In code, we have a follow various repeated k
minus one times one remove the maximum element
897.36 -> after the loop, return max of all But for the
time complexity suited for the maximum cost of n,
904.88 -> where n is the number of elements and removing
it from the array cost, and in the worst case,
909.68 -> because we may need to shift all the n minus
one elements, and our loop is repeated k minus
915.92 -> one times we'll have k minus one times to add,
plus add for finding the final largest element.
922.32 -> In total, we have k minus one times two n
plus n, which is two times k times n minus n,
928 -> which gives us off k times our time complexity,
where n is the number of elements of our
935.12 -> own, although in reality during the
iterations, and will decrease because
938.48 -> we have less and less elements, but we get the
sample complexity. And for the space complexity,
944.08 -> we're not using input size related variables,
we have a constant space complexity.
949.92 -> This solution is a bit slow. Let's move to the
next one. The idea of the second solution is to
955.44 -> start by sorting the array because by doing so, we
know that the largest element is other last cell,
960.8 -> the second largest element just before it, the
third largest just before it, and so on with our
966.8 -> array was sorted, and k is four. So return
the fourth element starting from the end,
972.8 -> in a gentle way, we sold our and we turn our
n minus k, and minus k represents the index
978.8 -> of the key elements starting from the end. For
the time complexity, we have both analog and for
984.96 -> sorting the array and all one for accessing,
we've got an O of n log n time complexity.
990.72 -> And for the space complexity, it depends on
the space complexity or the sorting function.
996.72 -> This solution is way faster than the first
one except in some cases, but we still have
1000.88 -> an all the solution to discover. In the first
solution we didn't have to solve to it is good,
1007.12 -> but searching for the maximum cost at each
iteration, which slows down the process.
1012.4 -> What if instead of getting the maximum cost log
out only yours is possible by using a priority
1018.32 -> queue. A priority queue is a queue where the next
element to be popped is not the first one that
1023.44 -> entered with the one with the highest priority.
And it's usually implemented with a heap. If you
1028.8 -> don't know about heaps, and priority queues,
you should really watch my YouTube video on
1032.88 -> the subject, you will find the link below or you
can just search for inside code heaps on YouTube.
1040.16 -> And after building our priority queue, popping
the next element because of work out holy,
1045.2 -> so we just have to pay the cost of
building the priority queue, which is add.
1049.84 -> For example, with our array, this is what our
heap would look like, you can see that the element
1054.8 -> at the top is the greatest one who extracted
and it costs of work and to rearrange notes.
1061.36 -> second iteration will extract the root cause
of work and to rearrange to maintain the order.
1067.36 -> third iteration, same thing. Now that we do the k
minus one iterations, the next extracted node is
1073.92 -> the eighth largest element, we'll turn it here
it's six. In Python, we have the hip Q module
1081.04 -> with a problem is that it's implemented with a
min heap, not a max heap. So the top will find
1086 -> the smallest element not the greatest to counter
that will just multiply values by minus one to
1091.44 -> reverse the order. So we start by replacing our by
minus ln for each element in our after doing so,
1098.48 -> we heapify our to make it respect to heap
property. And now we really do start extracting,
1104.24 -> we extract from it k minus one times. After
the loop, we extract the last time and return
1110.72 -> the result multiplied by minus one, obviously,
to get the original number though was in our,
1116.32 -> for the time complexity, who have earned to build
a new array with reverse values, and to heapify
1121.68 -> it, go check the video to know why. And then
we have k minus one iterations, each iteration
1127.6 -> because of work and to extract after the loop,
we have all worked out to extract one more time.
1134.64 -> In total, we have two n plus k minus one times
log n plus log n, which is two n plus k log n,
1141.12 -> which gives a time complexity of of amples k
log n, which is a bit better than the one of
1145.84 -> the previous solution, because k can't exceed
add. For this solution, stop giving interesting
1152.56 -> time performance difference only when n is
huge and case small. Because when k is close
1157.2 -> to an off campus, k log n is close to O of n log
n, the time complexity of the previous solution.
1157.819 -> Pause When k is close to zero, O of n plus k log
n is close to O of n for the space complexity
1171.68 -> who have unfold the priority queue who got an
offer and space complexity. We reached the end
1178.24 -> of this video I hope that you understood the
three solutions and see what the next one will
1189.44 -> come back to the course in this lecture we will
solve the symmetric tree problem. We have a binary
1195.52 -> tree and we want to see if it's symmetric.
In other words, if it's a mirror of it Self.
1201.36 -> For example, this tree is symmetric, because
if we take his left part, reverse it, who that
1206.48 -> is right part. And vice versa, if we take its
right part, we reverse it who got his left part.
1215.12 -> But this one is not symmetric. For example, if
we reverse its left part, we don't get the right
1219.84 -> part. Okay how to solve this problem? To check
if a tree is symmetric, what we really need
1227.6 -> to check is that left and right sub trees are
symmetric to each other. Who will focus on that
1234.8 -> you need to know that for tree problems,
the solution is usually don't coercively
1239.12 -> we process the root, then we call the function
on both sub trees and we combine the results.
1244.64 -> For example, to get the sum of elements of a
binary tree, we have the value of the root,
1249.52 -> then recursively call the function on both
sub trees to get the sum of their elements.
1253.92 -> After doing so, we return root value plus some of
left subtree plus some of right subtree. This way
1260.48 -> of traversing is called depth first search, and
it's how we solved the majority of tree problems.
1266.8 -> Let's go back to our problem, we have two
trees, route one and route two and want
1271.2 -> to check if they're symmetric to each other.
First case, both trees are empty. In that case,
1276.96 -> we return true because they're still symmetric
to each other, there is nothing that breaks the
1280.88 -> condition. Second case, won't we exist,
but the other one doesn't. In that case,
1286.88 -> without let it use it and not symmetric
because the node of the tree that exists
1291.2 -> doesn't even exist in the other
one, it's empty, we return false.
1297.12 -> Third case, both trees exist, but the
roots don't have the same value. Here also,
1301.76 -> they're not symmetric, because in symmetric
trees, the roots must have the same value,
1306.64 -> because when we reverse the tree, the root
position doesn't change. And last case, both trees
1312.96 -> exist, and they have the same root value. In this
case, we still can say that they're symmetric,
1318.72 -> because Okay, the roots have the same value.
But we still need to check their sub trees,
1323.6 -> having the same root value is not
enough to serve their symmetric.
1328.48 -> And if we take two symmetric trees, we can
notice that they have the same root value,
1332.88 -> though the left subtree of the first one is
symmetric to the right subtree of the second one,
1337.04 -> and on the right subtree of the first one is
symmetric to the left subtree of the second one.
1343.84 -> We verified that root values are equal. So
we need to try the remaining two conditions.
1349.04 -> And how are we going to do so we're going to do
so recursively, because if you think about it,
1354.08 -> we're building a function that checks
if two binary trees are symmetric,
1357.92 -> which is exactly what we need. This
is why we'll use the same function.
1362.88 -> It may sound hard to understand,
but this is what recursion about
1366.16 -> a function calling itself. If you're not familiar
with recursion, you should really have a look at
1371.84 -> it before continuing this course because
we will use it again in a further problem.
1376.8 -> If you want to learn recursion, you come
to the course I made on the subject.
1380.8 -> It's a complete and well appreciated course
that will let you be comfortable with recursion.
1386.96 -> Let's go back to our problem. We saw that we use
the function we're making, we saw that we use the
1392.4 -> function we're making. We call it on route one
dot left and route two dot right we're called
1396.72 -> on route 1.1 and route dot left and we tell you
at both calls return true, it means that both
1402 -> conditions are verified, the left subtree of route
one is symmetric to the right subtree of route
1407.6 -> to other the rights of drove route one is
symmetric to the left of Jove route two.
1412.88 -> Let's quickly see an example. We want
to check if this tree is symmetric,
1417.52 -> so we check if it's sub trees
are symmetric to each other.
1422 -> They have the same root value, so we check the
left subtree of root one with white socks off root
1424.125 -> two, same root value, who took the left subtree
of root one with right subtree of root two, same
1432.32 -> root value, we check left and right, same root
value. Other children are both normal they will
1438.24 -> turn true. Same with value and symmetric children.
All conditions are respected, it returns true.
1445.76 -> Now right up to a fruit one with lots of to
fruit two, they have the same root value.
1450.72 -> Their children on both know both calls
return true. All conditions are respected.
1455.52 -> The caller turns true. Back to here, all
conditions are respected. The Colita is true.
1462.32 -> Now REITs offshore foot one with Latakia for
two, they don't have the same root value,
1467.28 -> the call returns false. Not all conditions
are respected. The call returns false.
1473.92 -> Who don't ever need to check the second call
because we already have a non respected condition.
1478.16 -> The call returns false. The initial call
return false so our tree is not symmetric.
1485.52 -> In code, let's first make our our symmetric
function. It takes two trees as parameter
1490.64 -> route one and route two. First case
both don't exist without Q two and true.
1496.32 -> Second case, one of them exists but the other
one doesn't. Third case, they have a different
1501.68 -> root value. In both of these cases, the
trees are not symmetric, so return false
1507.84 -> will write, if root one is non is not equal
to root two is non, or root one dot val is
1509.68 -> not equal to root two, that wall will
return false. And now in the last case,
1517.6 -> both trees exist and have the same root
value, we still need to Chuck's up trees,
1522.56 -> which are that would wander I'd love to see much
to root to the droid. And that root wonder tried
1523.92 -> is symmetric to root to the left, we do so by
recursively, calling the function twice. Once with
1532.56 -> root one dot left and root two dot right and once
with root one or twice and route two dot left,
1538.56 -> both of them need to return true. So we turn
the results combined with the Add operator.
1544.96 -> And now when our main solution function is
symmetric, we first check that the input
1549.2 -> tree exists because if it doesn't, we cannot
return true, an empty tree is symmetric. Else,
1555.52 -> whichever is sub trees are symmetric to
each other with the function who made Now
1559.6 -> we return our symmetric Rudolph left and rudos.
Right. That's it. For the time complexity,
1566.16 -> we're just performing a depth first
search traversal of the input tree
1569.52 -> and the first cause of anti m
where n is the number of nodes.
1574.72 -> And for the space complexity, a symmetric tree
has to be balanced. And the call stack size
1579.44 -> needed by a recursive function that traverses a
balanced binary tree is an awful look at who got
1584.64 -> an off walk and space complexity. That's it for
this lecture, we've seen an interesting problem
1590.32 -> on trees. I hope that you have been able to
understand the solution seen with the next lecture
1602.56 -> Welcome back to the course in this lecture, we
will solve the Generate parenthesis problem,
1607.44 -> a problem that we will solve using backtracking.
By the way, in this course, I try to include
1613.36 -> problems on different pattern spire research
hash table backtracking, depth, first search,
1619.44 -> and so on. But one problem and each is not enough.
This is why you need to study more problems.
1625.44 -> For that, I suggest you to have a look at my
50 popular coding interview problems course.
1630.88 -> It contains 50 Problems different from the ones
in this course, about many data structures and
1635.76 -> algorithmic techniques, you can have a look at
the curriculum and reviews on the main page.
1642.24 -> Anyway, let's go back to our problem. We
are given an integer n and we're asked
1646.64 -> to generate all valid combinations of N pairs of
parenthesis. For example, with an equal to three,
1652.8 -> here are all the valid combinations. First of
all, what does a vowel combination mean and how
1658.56 -> to check if a combination is valid. A combination
that contains one type of paranthesis is valid.
1664.4 -> If every opening parenthesis has its closing
parenthesis, and it doesn't have a closing
1669.28 -> parenthesis without having an end used opening
parenthesis before it. Let's see some examples.
1677.2 -> This combination is invalid because these opening
parenthesis don't have closing parenthesis
1682 -> the syntax is invalid. Second example
this combination is invalid because we
1687.2 -> have a closing parenthesis without an
end use opening parenthesis before it.
1692.08 -> Last example, this one is valid because each
opening parenthesis has its closing one,
1696.88 -> and there is no closing parenthesis
without an unused opening one before it.
1702.48 -> Now how to check if a combination is valid. To do
so we can maintain a stack where we push one we
1708 -> find an opening parenthesis and we pop one and
find the closing one. The condition is that we
1713.6 -> don't try to pop from the stack when it's empty,
or the stack has to be empty after we finish
1718 -> traversing the combination. Trying to perform
the stock one is empty means that we have a
1723.28 -> closing parenthesis without an available opening
one before it all ones what we found before have
1728.56 -> been popped by all the closing parentheses. And
the second condition is that the stock must be
1733.92 -> empty at the end. Because still having elements
in the stack after traversing means that we have
1738.88 -> opening parenthesis that didn't gather closing one
yet. In both cases, the combination is not valid.
1747.52 -> And because we have only one
type of parenthesis around once,
1751.12 -> we don't ever need the stock, who can do is use
a variable div that represents the difference
1755.68 -> between the number of opening parenthesis and the
number of closing once. It has to be zero the end
1762.32 -> and if it becomes negative during
the process, then it's not valid.
1767.12 -> Okay, but what's the relation with backtracking?
In this problem, we're not asked to check if a
1771.92 -> combination is valid. We're asked to generate
all valid combinations of N pairs. And we use
1778.16 -> backtracking because at each step of building the
combination, we have two possibilities, adding an
1783.92 -> opening parenthesis and adding a closing one. And
because we want all combinations, we try them both
1790.64 -> because we get new ones want to add an opening
one, and all the ones want to add a closing one.
1796.16 -> Also in backtracking. We can have a
condition where we backtrack With continuing,
1801.28 -> it's one we know that the actual branch won't
lead us to a valid solution. In our case,
1806.8 -> it's one death becomes negative, it means that
the combination we built until now isn't valid,
1812 -> it's useless to continue building it, we know
that it won't give us a valid combination. Anyway.
1818.32 -> Let's see an example. With n equal to
three, we'll get this recursion tree.
1824.56 -> If you're wondering why our sauce at six is
because the n given us input represents the
1829.2 -> number of pairs. And in n pairs, we have two
advantages. So we multiply by two because we're
1834.88 -> adding one parenthesis by level one, we go to
the left to add an opening one and increment div.
1840.16 -> And when we go to the right to add
a closing one, and decrement, if
1846 -> we can notice that we have branches
that have been stopped earlier,
1849.36 -> those are branches were diff becomes
negative. As soon as they've becomes negative,
1853.52 -> we stop also Evon with branches that created the
combination of N pairs, we don't take all of them,
1860.16 -> we take only those who are divisible to zero,
remember the validity condition. So at the end,
1866.48 -> here are the combinations that get
added to our combinations array.
1873.44 -> Encode who stopped by creating a recursive
function rack that will fill the combinations
1877.68 -> array, it takes us parameters and the
number of remaining parentheses to add,
1882.56 -> def the difference between opening and closing
brackets COMM The actual combination that we're
1887.92 -> building, and comps theory of combinations, the
one that we're searching for in our problem.
1896.56 -> The first base case is one difficult negative, hit
it with Dr. Batra Kodaka return to go back to the
1902.4 -> previous call. The second base case is one we've
been able to add all the parenthesis we've been
1908.08 -> able to build a combination. But in this case,
we don't automatically add it to our comps array,
1914.24 -> we first check if d f is equal to zero. Remember
the condition. So if f is zero, we draw the
1920.48 -> parenthesis of our combination to form a string
and we add it to our valid combinations array.
1926.72 -> Else, we have the recursive case, we
said that we have two possibilities,
1931.6 -> adding an opening parenthesis and adding a closing
one. Therefore, who will have two recursive calls.
1937.92 -> For the first one, we add an opening parenthesis
to our combination, then when we call and becomes
1943.68 -> n minus one because we have one less parent is
to add and this becomes the plus one because
1949.44 -> remember that to add one one will add an opening
parenthesis. After the call, we move the opening
1956 -> one we added to put a closing one. After doing
so we call the function again. But this time
1962.16 -> diff becomes diff minus one. Remember that we
subtract one when we add a closing parenthesis.
1969.12 -> And after the call, we remove the parenthesis
we added to backtrack to the previous call.
1974.16 -> And we made our function. By the way, we can ever
optimize a little bit by dotclear. Returning if
1981.52 -> div is greater than add because if is the case,
it means that we don't have enough remaining
1986.16 -> parenthesis to close all our opening parenthesis.
div is greater than n. So we just return.
1993.84 -> If you're confused about what's happening
here, have a look again other recursion tree.
1998.08 -> And most importantly, you should learn
more about recursion and backtracking.
2002.16 -> The method we're using here to
generate all possible combinations,
2005.44 -> it's common to a lot of problems, you
should really be comfortable with it.
2011.2 -> Now in the main solution function, we'll first
create an array comps where we will put our valid
2015.6 -> combinations and we call our QC function to fill
it. But the tricky part here is that we pass two
2022.08 -> times n as an argument not add, because the n
given as input represents the number of pairs,
2027.92 -> nor the number of parenthesis and a pair is
made of two parentheses. So we pass two times,
2034.48 -> our combinations will be of length two
times. After filling comps, we just return it
2041.44 -> for the time complexity. In the worst case, what
add a zero, we have a cost of an to join the
2046.64 -> parenthesis we write T of zero is equal to add
n in the recursive case, and again moving from
2053.28 -> the combination cost of one, but we have two
calls where the input size gets reduced by one
2058.48 -> and is becoming added minus one in total t of n
is equal to two times u of r minus one plus one.
2067.92 -> Now we keep replacing t of n is equal to two times
t of n minus one plus one. So T of N minus one is
2070.545 -> equal to two times t of n minus two plus one we
replace or simplify and we got four times two
2080.64 -> and minus two plus three. We replace again, t of
n minus two is two times two of Armani three plus
2086.88 -> one will replace will simplify and we get
eight times T of animal is three plus seven.
2094 -> This recurrence relation is a common one we can
already notice the drill form. It's t of n is it
2100 -> To power k times t of n minus k plus two power k
minus one, we have the value of T of zero, so we
2107.12 -> need to find the value of K to go to T of zero
and minus k equal to zero. So k is equal to n,
2114 -> where plus k by n, who got t of n is equal to two
power n times T of zero plus to power n minus one.
2121.28 -> We know that T of zero is earned workplace,
we got t of n is equal to two power n times
2127.04 -> n plus two power n minus one would give us
an O of n times two power n time complexity.
2133.92 -> Know that here and represents the length
of the combination, which is two times
2137.44 -> the number of pairs given us input. Also,
n times two power n is not the exact power,
2143.2 -> the number of operations will be less than that
do two branches where we backtrack earlier,
2148.08 -> O of n times two power n would be the exact
bound if we had no condition on our combinations.
2155.2 -> If you don't know the technique are used to find
the time complexity over this recursive function.
2159.52 -> It's called the substitution method, it's an
important technique to know you should learn
2163.92 -> about it. And for the space complexity, we have
n plus one for the cost like size, the length
2170.4 -> of the longest branch in the recursion tree. But
we also need to count the required space to store
2175.2 -> the combinations. The length of a combination
is at and it has two possible characters. So
2182 -> we have two power and possible combinations.
And the length of each one of them is n. So we
2187.84 -> need n times two power n space to solve them. We
got off on times to power and space complexity.
2194.88 -> But not all of them are valid, we will
need way less than n times to power n,
2199.6 -> n times two power n is just an upper bound. And
we all t the required space for combinations
2205.12 -> is n times the number of elements after
filling the comms array. We reached the end
2211.52 -> of this lecture, I hope that you understood this
backtracking solution and see you in the next one.
2224.4 -> Welcome back to the course in this lecture
rules or the gas station problem are given
2229.44 -> a circle a list of gas stations where we can
go from Station II to the station i plus one,
2234.8 -> and the last one goes back to the first one.
2238.16 -> And we are asked to find the index of the station
from where we start to be able to traverse all the
2242.72 -> stations and go back to the initial one without
running out of gas. Know that we can only move
2250 -> forward the gas tanks thought empty gas of i
represents the amount of gas at the station i
2255.68 -> cost of iron presents the cost to go from the
station out to the next one, the answer is
2260.08 -> guaranteed to be unique. And if the station we're
searching for doesn't exist return minus one we
2264.24 -> did use or there will be at most one station
for more we can traverse and be able to go back.
2272.08 -> For example, if we have these 10 stations, the
output is eight because when we start from station
2277.04 -> eight, we can go back to it without running out
of gas. We start with no gas, as mentioned the
2282.56 -> the problem, we add for gas of station eight and
we pay one to move to the next station, who add
2284.075 -> five gas of station line and we pay two to move
to the next station, we add one and pay five who
2291.92 -> add five and pay two, or three and pay two, or
three and pay eight, we add five and pay two,
2295.28 -> or three and pay for we add one and pay two, or
three and pay five, and we've been able to go back
2306 -> to station eight, you could see that the amount of
gas never became negative. Which is not the case
2312.56 -> for Office stations, for example with station one
who add five and pay two, or three and pay two,
2317.36 -> or three. And if you pay the eight to move to the
next station, the amount of gas becomes negative,
2324.64 -> which means that we can't continue, the
station we started from is not the right one.
2331.52 -> Let's solve this problem. A brute force solution
of a darkly comes in our mind is to simply
2336.72 -> simulate what happens with every station and we
find one that respects the condition who turn its
2342.4 -> index. Let's try it with our example. With the
first one, we add one with a five and the cost
2349.52 -> becomes negative Dr eliminated. Next one, we add
five and P two we have three and PE two, we have
2354.8 -> three and PE eight air the amount of remaining
gas became negative not this one. Next one, three
2362.8 -> and PE two we have three NP eight and remaining
became negative. Next one, we have three NP eight
2369.36 -> remaining became negative. Next one, we add five
and pay two or three and pay for we add one and
2375.84 -> pay two or three and pay five and remaining became
negative not this one. Next one, we add three and
2382.24 -> pay for negative. Next one, we add one and pay
to negative next one who has three and pay five
2388.96 -> negative next one who have plus four minus one
plus five minus two plus one minus five plus five
2396.48 -> minus two plus three minus two plus three minus
eight. was four minus two, plus three minus four,
2402.88 -> plus one minus two plus three minus five.
And we've been able to go back to the station
2407.36 -> from where we started without the alternate
because we know that the answer is unique.
2414.8 -> In code, we create a function that takes
us parameters, the array gas theory, cost,
2419.76 -> and index of the station form where we thought
the goal of this function is to tell us if we can
2425.44 -> finish the cycle by starting from the stations
thought, we first need a variable remaining
2431.12 -> that source the remaining amount of gas, we also
need the variable to store our actual position.
2436.64 -> Our initial position is the station FOMO,
we thought so initialize our add start.
2443.2 -> And we also need a boolean variable started
to know who started walking yet or not,
2448.08 -> we need this variable in our loop condition. We
need to keep looping until we go back to start,
2454.4 -> we write why isn't equal to start or not
started. Here not started is important,
2460.4 -> because if we don't use it, we won't even enter
the loop. Remember that I initialize a stock.
2466 -> So I installed our equal, we want them to
be equal. But after traversing the cycle,
2471.68 -> not now this is why we need the variable started
to know if we're in the case, where is equal to
2476.64 -> start, because we didn't start yet. Or because
we traverse a cycle, and I went back to start.
2483.36 -> Let's continue inside the loop we saw started to
true because we started then we update remaining.
2489.92 -> We saw that on the station i We are the amount of
gas in it, and we pay the cost to move to the next
2495.04 -> one. So we add gas of our answer drug costs of I.
After doing that, if we mainly becomes negative,
2502.64 -> it means that we couldn't go back to salt, we
don't have enough gas, we return false, else,
2508.48 -> we move to the next station. The next station is
usually i plus one. But we need to add modules
2514.72 -> the number of stations to handle the case were of
the last station i becomes i plus one add modules
2520.64 -> and it goes back to zero, we right i becomes
a plus one modules the number of stations.
2528 -> And if we finish the loop, it means that we've
been able to go back to start return true.
2534.8 -> Now in our main solution function, we just
tried the function we made on each station
2539.04 -> as we did in the example. And we turn the actual
station as soon as the function returns true.
2545.04 -> And if the function fails with all stations
will to n minus one for the time complexity,
2551.6 -> because the answer is unique. A
possible worst case is this one,
2555.84 -> because by starting from station zero, which
covers n stations before getting a negative amount
2560.96 -> from station one, which covers n minus one from
station two, which covers n minus two, and so on,
2567.36 -> we get the sum n plus n minus one plus n minus
two and so on until one. After simplifying,
2574.08 -> we found that it's an O of n squared, we'll
get an O of n squared time complexity,
2579.6 -> or the constant space complexity because
we're not using input size related variables
2586 -> of n squared is low. For this problem, we're
getting off n squared because for each station,
2590.8 -> we're traversing again, almost all the stations,
let's see how to optimize it. The main thing that
2596.88 -> you need to understand for the second solution
is that if we start from the station or the index
2601.52 -> thought and reach a negative amount of the station
I then all stations between Staten Island clauses
2607.68 -> are not valid. We don't need to try them with
Dr. John to Iboss one. Let me tell you why. We
2614.72 -> have the case where gas of thought is smaller
than cost of start. He the loop stops darkly
2619.44 -> because remaining becomes negative, it stops us
thought so there are no other stations involved.
2624.64 -> Nothing to talk about here. But when gusoff Start
is greater than or equal to cost of salt, the loop
2631.28 -> moves to all the stations, it can traverse a bunch
of stations before remaining becomes negative.
2637.04 -> For example, here when we start at station four,
remaining becomes negative at index seven. It
2642.16 -> means the stations 456 and seven are all invalid.
We'll start again from purpose one, eight. But why
2649.84 -> girls will start is greater than or equal to cost
of start. In our case, the difference is three.
2655.28 -> Every three is considered as an advantage over
starting from next stations is like a bonus by
2661.28 -> starting from station four. We have three more gas
and installing from the next one, station five.
2667.04 -> And even with that bonus, we didn't have enough
gas to do a full cycle. We stopped at station
2673.28 -> seven avenue that bonus we couldn't go over
station seven. So how do you want to go over
2678 -> it without a bonus? It's like you have $500 and
they aren't enough to buy a particle PC. Then you
2685.12 -> say this $500 weren't enough. I'll try with four
hundreds maybe they will be enough. It's a logical
2695.04 -> and this is why when remaining becomes negative.
We don't try again from the station that comes
2699.68 -> after The one where we started, who skipped all
the ones who traversed we started going from IPOs.
2705.52 -> With our example, who start from the beginning, we
may name becomes negative who's taught from IPOs
2710.72 -> one at five and we pay two remaining becomes three
who are three, we pay two remaining becomes four,
2717.68 -> who else we pay eight remaining becomes minus
one negative. What we're going to do now is to
2723.52 -> dock the start again from here, without
trying again, from stations to three,
2728.16 -> who add follow up to remaining becomes three, who
else we will pay for remaining become Sue, who
2733.92 -> add one who pay two remaining becomes one who
has free will by five remaining becomes minus one
2739.6 -> negative. Once again, without his thought, again,
from i plus one, we add four we pay one remaining
2746.64 -> becomes three who add four who pay two remaining
becomes six, and we finish traversing the array,
2752.88 -> the candidate is station eight. But it doesn't
mean that it can do a full cycle, it just means
2758.48 -> that we can reach the end of the array without
reaching a negative amount of gas. We didn't check
2763.2 -> the pot before it. This is why I said candidate.
It's a potential valve station. We don't know yet.
2770.56 -> To say that a candidate station
is valid by starting from their
2774.16 -> remaining Miss never become negative one
traversing the path from candidate to the end.
2778.8 -> But also when traversing the path from the
beginning of the array to candidate X clause.
2784.88 -> The first part of the cycle is what we verified
during the traversal. And for the second part of
2789.6 -> the cycle, we just calculated the sum of gas from
zero to candidate minus the sum of costs from zero
2795.04 -> to candidate, the result represents the remaining
gas after traversing that pot. And if by adding
2802.64 -> it to remaining the result stays positive, then
candidate is a valid station. Else we have no
2807.92 -> valid station. For example, here the sum of
gas from zero to candidate exclusive is 24.
2814.16 -> The sum of course from zero to candidate exclusive
is 30. The difference is minus six. What remained
2821.28 -> from candidate to the end is six what remains in
the pot before candidate is minus six by adding
2826.16 -> them together we get zero which is positive. So
candidate is the valid station. Question. What if
2832.64 -> we got a negative result here, then with Akutan
minus one because there is no valid stations.
2839.76 -> But what if the valid station comes after
the candidate, it's impossible. Once again,
2844.96 -> the station forma we started candidate
has an advantage over next stations,
2849.92 -> we know that gas of candidate is greater than
or equal to cost of candidate. So even if with
2854.8 -> that bonus, we get a negative remaining amount of
gas, it will also be the case for next stations.
2862.32 -> Let's jump to the code on the side all of
this remaining starts at zero. And same
2866.64 -> thing for candidate because at the beginning, we
assume that the first station is the candidate,
2871.36 -> the potential valley station. Now we start
traversing stations. For each station, we update
2878.16 -> remaining gas, we are guests of our answer truck
cost of AI. And if remaining becomes negative,
2884.72 -> we sell that to start again from APL small, it
becomes a new candidate, and remaining becomes
2889.92 -> zero because we will start again. After the loop,
we calculate the remaining gas of the pot before
2895.92 -> candidate the sum of gas minus the sum of costs
of the pot from zero to candidate X clause IV.
2902.88 -> Now we have three possible cases we have
the case or candidate is equal to and
2907.36 -> it means that we reached the end of the
array without finding a potential station,
2911.52 -> no station made it to the end
of the array, we return minus
2915.76 -> one. So in case we have a candidate, but when
adding prev remaining, we found the negative
2920.32 -> result, it means that it stopped somewhere
in the pot from zero to candidate return
2924.96 -> minus one. And third case, we have a candidate and
remaining plus prayer remaining is not negative.
2931.76 -> So candidate is the false station for more we
start to be able to do a full cycle, we return it.
2939.12 -> In code. If candidates is equal to
length of gas, the number of stations,
2943.6 -> or remaining prosperity remaining is smaller than
zero, we return minus one else we return candidate
2951.36 -> who can even keep track of remaining in the first
loop to avoid traversing again to calculate the
2956.16 -> sums. For the time complexity, we just have a loop
that does n iterations all other operations are in
2963.36 -> over one, we get an off and on complexity, where n
is the number of stations much better than O of n
2969.12 -> squared. Add a constant space complexity because
we're not using inputs all related variables.
2977.28 -> Basically, in the solution, we search
for the candidate the station that made
2980.88 -> it to the end of the array without
reaching a negative amount of gas.
2984.72 -> Then we check if it still boosts up
when traversing remaining stations,
2988.88 -> those in the pot from the beginning of the
array until going back to it who's the end
2994.08 -> of this video. I hope that you understood the
optimal solution and see what the next one
3006.24 -> Welcome back to the course in this lecture
rules of the course scheduled problem,
3010.88 -> we have n courses labeled from zero to n
minus one in clauses that we need to take.
3016.16 -> But some of them are prerequisites the other, we
cannot take a course before taking the other one.
3022.56 -> And we have to determine if it's possible to
finish all the courses. So we are given an integer
3028.4 -> as representing the number of courses and an
array prerequisites who are prerequisites of r is
3033.28 -> equal to a b means that you first need to take the
course P before taking the course a. For example,
3039.44 -> if we have this input, the output should be false.
Because to take course three, we must have taken
3043.354 -> course zero, and to take her zero must have taken
course one. And to take course one, we must have
3044 -> taken course three, it is impossible, it's
like we have a dependency cycle. This is
3055.44 -> why we cannot finish all the courses return
false. But with this input, the output is true,
3062.16 -> we can take or zero then course three, then
course one, then course five, then of course two,
3065.12 -> that course for each course will have its
prerequisite satisfied when taking it.
3072.72 -> How to solve this problem. Here we have
elements, courses and relationships between them,
3078 -> of course being approved was that of a novel
course. And every time we faced this situation,
3083.76 -> having elements and relationships between
them, you should think of using a graph.
3088.96 -> I'm not saying that it will always give the best
solution. But even if it doesn't, it will at least
3094.08 -> give you a way to visualize the problem with
vertices and links between them. In our case,
3100 -> the vertices represent courses and edges
represent dependencies and add from u to
3105.04 -> v means that we first need to take the course
you before being able to take the course fee.
3112.08 -> Okay, now we build our graph, we got a
directed graph what we will do with it.
3117.04 -> Our goal now is to search for dependency cycle.
If we find one, it means that it's impossible
3122.32 -> to finish all the courses return false. Else if we
don't find one at all, it means that it's possible
3128.56 -> to finish the mole return true. Basically, we're
searching for a cycle in a directed graph. In a
3136.8 -> linked list, a classic way to check if there is a
cycle is to traverse a linked lists while saving
3141.76 -> visited nodes. And if we step on a node that we
visited before, it means that there is a cycle.
3148.48 -> We can think of applying the same logic for graph
which covers with depth first search, for example,
3153.52 -> while using a set of visited notes. And if we step
on a node that has already been visited, it means
3158.88 -> that we have a cycle return false. By the way, if
you don't know about the full search, it's a way
3165.68 -> of traversing trees and graphs by diving deep into
a direction until we can move forward anymore.
3171.12 -> Go back, try and all the way and so on. I made a
huge video about the subject that you can watch.
3177.6 -> You need to know about DFS before continuing
this video is a prerequisite intended pun.
3184.88 -> But this strategy doesn't always
work. Here is a counter example.
3189.2 -> We have this graph let's start traversing. We
start for example from two we put it in visit it
3194.88 -> we move to zero we pull it in visit it will
move to three we pretend visit. This one has
3200.72 -> no outgoing others, we backtrack, this one has
no remaining neighbors to traverse we backtrack.
3207.04 -> From here we move to the second neighbor one we
put it in visit it will move to four we put it
3211.92 -> in visited. Then from here we move to three
and it's already in visited so our strategy
3216.96 -> would return false. Which is wrong because
we can totally finish all the courses here.
3222.24 -> We can start with two then zero then three than
one than four, all prerequisites are respected.
3230.112 -> Was the solution done? Well, let me
first talk about topological sort.
3235.04 -> We have a directed graph where vertices represent
tasks and an ad from u to v means that u is
3240.16 -> a prerequisite of V. topological sort is the
process of finding a linear ordering of vertices
3246.16 -> such that each vertex comes after is perquisites.
And all the words, for each edge from u to v,
3252.32 -> V must come after you in the ordering. For
example, for this graph here is a valid ordering.
3260.08 -> Know that a valid ordering is not always unique,
it's possible to find all the orderings that
3264.8 -> satisfy the condition. But the logical sort is
not always possible. It's not possible when the
3271.92 -> graph contains a cycle like this one. B is a
prerequisite of C, C is a prerequisite of D, D
3278.56 -> is a prerequisite of E and E is a prerequisite of
B, so we have no way to order them. Fortunately,
3285.2 -> while performing the topological sort, we can
detect the existence of a cycle. If it happens,
3290.24 -> we just stop and say that we cannot have a valid
ordering of vertices. And it's exactly what we
3296.56 -> want to do in our problem who have courses.
Some of them are prerequisites the other ones,
3301.52 -> and we want to know if we can take all the courses
and all the terms if a valid ordering exists.
3307.76 -> Therefore, who will use the biological source
and if during the process, we found the cycle
3312.32 -> return false. Otherwise return true because it
means that we've been able to make an ordering.
3319.12 -> Okay, but how does topological salt work? A
possible way to implement a biological source
3324.4 -> is depth first search. Let's, for example, soft
foam this vertex, we put it on the past stack,
3330.88 -> the pastor contains the vertices of the actual
path. B is its neighbor, we go to it, and we
3337.2 -> put it on the past stack is his neighbor, we go
to it, and we put it on the path stack. He is
3343.52 -> his neighbor, we go to it, and
we put it on the path stack.
3347.36 -> Now it has no neighbors, it means that
we can safely put it in our ordering,
3351.76 -> because there are no vertices that have to come
after it is perquisite of no one, we put it in the
3357.36 -> order stack and we backtrack to the previous node.
Next neighbor is I will go to it and we put it on
3364.8 -> the path stack. Same again, it has no neighbors,
who remove it from path stack and pull it
3370.32 -> on all the stack. And we backtrack. Next neighbor
is if we go to it, J is a neighbor, we go to it,
3378 -> it has no neighbors, we move it from path stack,
we put it on all their stack, and we backtrack.
3384.72 -> Next neighbor is all but it's already visited. It
has no more unvisited neighbors, so all vertices
3390.96 -> have to come after it in the ordering our visit,
we can safely put this one and we backtrack.
3397.44 -> This one also has no more unvisited neighbors,
we can put it in order staff, and we backtrack.
3404.08 -> And the process continues like that. Until
we traverse the whole graph of the end,
3409.36 -> we get this ordering, we reverse it together from
the beginning to the end. Now the opposite. encode
3417.12 -> our DFS function takes us parameters to graph
the vertex promo we start the path stock,
3422.88 -> the oldest stack and the set of visited notes. We
start by adding our vertex to the past, just when
3430.4 -> we start traversing it, then for each unvisited
neighbor, who first added to visit it, and we call
3436.32 -> DFS with it as an argument to traverse it. After
doing so for all the neighbors who can safely put
3442.48 -> the actual vertex on the oldest stack will pop
up from past stack and give it to all the stack.
3449.36 -> And in our main top sort function, it takes us
an argument the adjacency list of our graph,
3454.88 -> it squares the visit itself,
the Bastok, the older stack,
3458.72 -> then it visits each unvisited vertex
with DFS. After doing so, the other
3463.84 -> stack is filled with turns reverse together the
ordering from the first vertex to the last one.
3468.64 -> Now the opposite. And starting from this
algorithm, we can add instructions to detect cycle
3476.8 -> we find the cycle when you find a back arch,
and as that goes from vertex u to a vertex V,
3482.16 -> where V is already in the path stack. Like here
we have a B, C, D, E, then he has B as a neighbor,
3489.44 -> which is already on the path stack. This graph
contains a cycle B and E depends on each other.
3497.2 -> In Code, our DFS function will not be a Boolean
function. It returns if yes or no we've been
3502.56 -> able to make an ordering. What we add is that
before moving to a neighbor, we check if it's not
3508.24 -> already in the stack. If it's the case, without
a return false, we can't make a valid ordering.
3514.56 -> Also, if traversing enable returns false, it means
that we found a cycle one going from there. This
3520.64 -> is why if the recursive code turns false, will
also return false here. And if we've been able
3526.64 -> to traverse neighbors without getting a negative
result return true, we could make an ordering.
3533.2 -> Know that to optimize checking for the
existence of the actual vertex in the stack,
3537.2 -> it's better to use a set instead of a list
searching and assert is an old one time an average
3542.56 -> pass doc now is of type set at the beginning we
add our vertex to it after the Lupu move it out to
3548.88 -> add it to all the stack. And in our main solution
function, we first need to build the graph
3556.32 -> because input will have the number of courses and
the list of prerequisites. Now the adjacency list
3563.84 -> to build the adjacency list, we know
the number of vertices so we create
3567.44 -> an array of N empty arrays. Each one
will contain neighbors of the course I
3573.04 -> know which are first prerequisites of the problem
says that prerequisite of one has to come before
3578.56 -> prerequisite of zero. So create an ad from
prerequisite of one two prerequisite of zero.
3584 -> In other words, who add prerequisite of
02 neighbors have prerequisite of one.
3590.4 -> Now that we've built the adjacency list, we can
start traversing but before we create the visit
3595.76 -> itself, the past arc which is also a set on
the order stack, For each and visited course,
3602.08 -> who added to visit, and if calling DFS with it
returns false, it means that we couldn't build
3607.28 -> the old, we found the cycle. So return
false, who can't study all the courses
3613.6 -> out of the loop doesn't return false, it means
that we could find an ordering because all
3618.24 -> the order courses return true. And we've been able
to solve our problem. For the time complexity,
3626.48 -> we're just performing dub for search on a graph.
And the time complexity of DFS is often for v plus
3632 -> length of E, will length of v is the number of
vertices and length of E, the number of edges,
3638.64 -> ie the number of vertices is the number
of courses and, and the number of edges
3642.64 -> is M for length of prerequisites list, who
got an off campus and found complexity.
3649.12 -> And for the space complexity, we have the space
for the adjacency list length of v plus length
3653.84 -> of E, the space for the visited set length of v,
the space for the path stack, and the older stack
3659.6 -> length of v and the space for the call stack
length of v in total, who got full times length
3665.44 -> of v plus length of v, which is an awful length
of v plus length of v, who does have apples.
3672.8 -> Know that you may find a similar solution. But
with collars each vertex can have the color white,
3677.68 -> gray or black. Compared to our solution,
what means and visited. Green means visited
3683.76 -> and in the past dark, and black means
visited add not in the past anymore,
3688.32 -> we've put it in the order. And if
we found the neighbor that is great,
3692.96 -> it means that it's in the actual path, and we
found it again. So we have a cycle return false.
3702.08 -> No implemented topological sort with depth
first search. But we can also implement it
3706.4 -> with breadth first search. Let me show you how.
If you don't know about breadth first search,
3711.6 -> I made a YouTube video about it, I recommend
you to watch it before continuing this one.
3718.16 -> The general idea of our second solution
is to split our directed graph into levels
3723.04 -> and the first level, we have vertices that have no
prerequisites, we'll conduct this thought studying
3727.92 -> them. Once we finish, we can remove them from
the graph by removing them from the graph. So
3734.56 -> vertices won't have prerequisites anymore, because
their prerequisites were courses we just started
3739.6 -> and they're satisfied. And these vertices
represent the second level, we'll put them in
3745.2 -> our ordering and remove them after removing them,
so vertices won't have prerequisites anymore,
3752.72 -> they represent the third level, we put
them in our ordering and remove them.
3757.92 -> And the process continues like that
until we have no more vertices.
3764.08 -> Both removing vertices from graph costs on time,
because we need to update the adjacency list.
3769.6 -> Instead, we'll keep track of
the integral of each vertex
3773.04 -> and when we traverse a vertex, we decrement
the integral of all these neighbors,
3778 -> the in degree of a vertex is the number of edges
that are entering it. For example, the integral
3783.2 -> of this vertex is to so when we remove a vertex
that is going to it would decremented in degree
3790.88 -> and if the integral of a vertex becomes zero,
it feels at all its perquisites are satisfied,
3795.84 -> who can traverse it, we put it in the queue. With
his graph, we call the integral of each vertex,
3802.48 -> we search for vertices with an integral
of zero, we put them in the queue and you
3806.64 -> apply classic BFS traversal. The difference
is that when we pop a node from the queue,
3812 -> who start by putting it in the ordering array
because it has no remaining prerequisites,
3816.72 -> also want to traverse a neighbor with
decremented in degree, and if it becomes zero,
3821.76 -> we put it in the queue. Last thing would
not need a visited set, because we're not
3827.2 -> putting a vertex in the queue until we finish
traversing all vertices that are going to it.
3832.24 -> So we don't have the risk of traversing a vertex
again. With this graph, this is what happens.
3859.84 -> Encode will create an array of an
empty arrays as we did with DFS,
3864.16 -> but we'll also add an array of N zeroes
to solve the integral of each vertex.
3869.28 -> Now when filling the adjacency list will also
increment in degree of prerequisite of zero
3874.24 -> because prerequisite of zero is the vertex
where the edge enters, so incremented in degree
3880.88 -> now we'll create an array where
we'll put our ordering and a queue.
3884.56 -> The queue initially contains
vertices hoes in degrees zero,
3888.64 -> after it will start traversing while the cool
still contains elements will pop a vertex we
3894.16 -> add it to ordering because it has no unsatisfied
prerequisites, and we traverse its neighbors for
3899.6 -> each With different methods in degree, and if it
becomes zero, we incue it as explained earlier.
3906.48 -> After the loop, the other array is not filled, we
return it. This time, we don't need to reverse it
3911.6 -> because we started by putting vertices of level
zero than one and so on. With this topological
3918.24 -> sort algorithm, we can also detect cycles.
When the graph contains cycles. What happens
3923.44 -> is that at some point of the process, we will
have no more vertices with an index of zero,
3928.56 -> which means that nothing will be inserted in the
queue, the process stops earlier, the array will
3933.04 -> contain less than the total number of vertices,
who will deduce that the process couldn't continue
3938 -> because there is a cycle. And in our problem, who
just want to know if we can make an ordering or
3943.92 -> not, this is why after the loop, who will just
compare the length of the order array with add
3948.88 -> the number of courses either equal, the
algorithm returns true, else it returns false.
3956.16 -> So we keep the same code who just changed
the return statement with a length of order
3960.96 -> equal to add. For the time complexity,
we're just applying breadth first search,
3967.04 -> which has an off length of the plus length of
a time complexity O of n plus m in our problem.
3973.36 -> And for the space complexity, we have length
of v plus length of a for the adjacency list,
3978.24 -> length of v for the in degree array, and
length of v for the queue of the ordered array,
3983.2 -> three times length of v plus length of
V gives offline for v plus length of E,
3987.2 -> which is of m plus m and our problem,
we get an off campus M space complexity.
3994.48 -> We reached the end of this video in this
one, we solve the CO schedule problem
3998.08 -> with two different ways. I hope that you
understood them both and seen the next one.
4009.44 -> Welcome back to the course in this lecture, we
will solve the Kieth permutation problem with
4014.8 -> a range of numbers from one to n in clause
IV, who can make n factorial permutations.
4020.24 -> by labeling them in order starting from one,
you're asked to return the Keith permutation.
4026.08 -> For example, with n equal to three and
k equal to three, here are the three
4029.92 -> factorial permutations of 123 labeled animateur K
is three, so we turn the third one to one, three.
4038.88 -> The first solution that may come in your
mind is obviously the brute force solution,
4042.88 -> generating all the permutations doesn't return
the case one, we give to the function the range
4048.72 -> from one to n in closet, then we return the one at
index k minus one. Remember that an array is zero
4054.8 -> indexed, so the Keith one is at index k minus one.
But the problem with this solution is that with
4061.44 -> n elements, we can make n factorial permutations
of lung add that it costs n times n factorial to
4067.2 -> generate them, we get n or m times n factorial
time complexity Soulshine, which is extremely
4072.72 -> slow. We did use the tree to solve this problem
is to be able to find the permutation without
4079.36 -> generating the permutations. And this is what
we'll see now. Let's take n equal to four. Now
4086.72 -> take a paper or notepad software, list all the
permutations of 1234 in order and tell me what
4092.96 -> do we notice, I want you to take some minutes
to analyze the structure of those permutations.
4100.08 -> Here are all the permutations we have a
total of four factorial permutations 24.
4107.12 -> Who can notice that these 24 permutations can be
divided into four parts. The first one contains
4112.64 -> permutations that start with one, the second
one contains permutations that starts with two,
4117.52 -> and so on. Let's suppose that we want to
find a 16th permutation k equal to 16.
4125.44 -> If we label them starting from zero, it means
that we want to find the permutation 15.
4130.24 -> Because 16 is one we label them starting from
one. The question now is, can we find what part
4136.48 -> among these four parts of permutation 15 will
be? The answer is yes, by using math. We know
4143.6 -> that the first part contains permutations from
zero to five in clause, the second one from six
4148.4 -> to 11 in closet, the third one from 12 to 17, in
closet, and the last one from 18 to 23. In Closet.
4156.96 -> To find which one we'll just divide K by the
length of a part, which is six in our case.
4162.96 -> 15 divided by six gives two so the permutation 15
won't be in the pot zero won't be in the pot one,
4169.6 -> but it will be in the part two. Now that
we're working with zero index labeling,
4176.88 -> we know that the part two contains permutations
that starts with three. So we already know that
4181.28 -> our Keith permutation will start with a three
and it will be one of these permutations.
4187.68 -> Let's continue. What's gonna happen now
is that the search space will be reduced.
4192 -> Now we know that our case permutation
will be in these six permutations.
4196.16 -> We need to update variables. K needs to be more
Initially we were searching for permutation
4202.64 -> 15 Among all the permutations, but in this
group of six permutations, we're searching
4207.76 -> for permutation three, why three, because 15
and model six, the length of the pod is three.
4215.28 -> Case 15, when we start from permutation zero,
but in this particular part it will label
4220 -> permutation starting from zero, whose solution for
permutation three, and also represents the number
4227.04 -> of remaining elements of the permutation to find
and found one, so we decrement and becomes three
4234.64 -> and factorial also changes it becomes three
factorial six. Same thing for pot length,
4240.96 -> it also gets updated six divided by three is two.
We also remove three from a news elements because
4247.84 -> we already found its place in the permutation,
and our permutation doesn't contain duplicates.
4255.12 -> Who can divide these six permutations into
three parts of two elements, the first part
4259.68 -> contains permutations holds the second element
is one, the second part contains permutations
4264.64 -> hosts the second element is to other third parts
contains permutations who is the third element is
4271.2 -> 41214. All the elements or two we
didn't use it in our permutation.
4276.64 -> Case three now can we find the pot case
permutation belongs to yes once again we divide
4282.48 -> by the pot length, three divided by two gives
one so the case permutation will be in part one.
4289.12 -> And we know that permutations of
Part One have to our second element,
4293.2 -> so the second element of our permutation will
be to, again the search space will be reduced we
4299.76 -> know that our kid permutation will be in these
two permutations. This is why we update the
4304.88 -> variables k gets modified as we did previously,
it becomes k models the length of part three
4310.88 -> models two gives one it means that among these two
permutations, we're switching for permutation one,
4318.08 -> and gets decremented it becomes two which changes
the value of n factorial two factorial is two.
4323.92 -> Which also changes the value part length,
and factorial divided by n is two divided
4328.56 -> by two which is one. We can divide these two
permutations into two parts of one permutation,
4335.52 -> the first part contains permutations
holds the third element is one,
4339.04 -> and the second part contains permutations
holds the third element is for,
4344.08 -> to know the path or case permutation belongs to,
who divided by the port land, the path length here
4349.36 -> is one and one divided by one gives one, our
permutation will be in part one. permutations
4356.8 -> of part one how for as a third element, so the
third element of our permutation will be four.
4363.44 -> We do use the search space we know that
our permutation will be in this part of
4367.28 -> one permutation, we update variables, k becomes k
models the port length, one model is one zero, and
4374.32 -> becomes one and factorial becomes one pot length
becomes one and we move for from a news elements.
4381.68 -> We divide this one permutation
into one part of one permutation.
4385.36 -> The first part will contain permutations host,
one is the fourth element, the length of a part
4390.16 -> is one, and k divided by one gives zero. So our K
permutation will be in pod zero. And permutations
4398 -> of pod zero have one is fourth element. So the
fourth element of our permutation will be one
4406 -> now and becomes zero and it gets
decremented. So we'll finish the process.
4409.92 -> The case permutation is 3241, who found it
without generating all the permutations.
4419.04 -> If you didn't understand what we've been doing
here, let me show it to you in another way.
4424.48 -> You first need to understand
how our permutations generated
4427.84 -> are the beginning who have no
choices forming this example.
4431.44 -> And because we want all the permutations, we try
all possibilities. When we add one when we add
4436.8 -> 212 and three, add one, add four, this is why
you're seeing four branches are the beginning.
4443.76 -> And we're talking about permutations without
repetitions. So when we take an element,
4448.16 -> we remove it from possible choices. This is why
when we take two other beginning for example,
4453.52 -> lat branch creates three branches only not
411111, a three and one one, we add four,
4460.48 -> you can see that we didn't add two
again. And when we take four for example,
4465.28 -> we have two choices left one or
three, we get two new branches only.
4469.84 -> Then when we take one of them, we have
one choice left, the one we didn't take
4475.76 -> part in our problem we want to find the case one.
The way we solve this problem is by using math
4480.96 -> to calculate what branch we should go from
to reach the combination we searching for.
4488.8 -> Imagine that you have 1000 books labeled from
zero to 999. Let's say that you're searching
4494.48 -> for the book 436 You remember that these books
are organized into Turn boxes have 100 elements.
4502.16 -> The first one contains books from zero
to 99, the second one from 100, to 199,
4507.76 -> and so on how to know which book to search, and
you simply divide the number of the book you're
4513.12 -> searching for by the size of a box, because here
they have the same size. 436 divided by 100 is
4520.64 -> four, we searched in box four, we still didn't
find the book, but we reduce the search space.
4528.08 -> Now, we will search for book 36 In this box of
100. Why, because 436 modules 100, the pot length
4536.4 -> gives the receipts. Once again, the 100 books
of the books four are organized in 10 boxes of
4542.96 -> 10 books each, the first one contains books from
zero to nine after for hundreds, the second one
4548.16 -> from 10 to 19, after for hundreds, and so on.
The book size is 1036 divided by 10 gives three,
4555.84 -> we search in box three. In that box three, we
search for book six because 36 modulus 10 is six,
4564.16 -> so on and so on until we found the
book without traversing all the books.
4569.2 -> And basically this is what
we did to solve this problem.
4573.68 -> Let's try to generalize or the beginning we'll
have n k add in us that contains elements in the
4579.12 -> range from one to adding clause if now while n is
greater than zero, who stopped by calculating the
4584.8 -> port length, it's an factorial divided by n.
After it, we calculate the index of the next
4591.2 -> element to put in the permutation. Remember that
we calculated by dividing cable the port length,
4597.12 -> after we calculated we add an use of either
the permutation either deleted from unused
4603.52 -> who add an use of oil because it represents the
common element in the if part. Then we decrement
4610.32 -> n and k becomes K model a spot length to get
its new position in the path that we choose.
4618.16 -> who keep repeating that and when a becomes
zero, we have our case permutation and we
4623.04 -> solve the problem. In code, we have a function
that takes as parameters and key the given input
4630.4 -> or create an empty array for the permutation
we're searching for. Then you create and used,
4634.96 -> it contains elements of the run want to
add in clause if afterward to avoid all is
4640.72 -> recalculating our factorial recruiting the very
fact we're factoring it represents a factorial,
4646.24 -> it contains n plus one elements to have the
values from zero factorial to n factorial.
4652 -> To fill it, we know that zero factorial is one.
And for remaining elements, we just take the value
4657.52 -> of the previous cell and we multiply it by I, for
example, with five who got 1126 24 120. Now we
4667.68 -> decrement k, because k represents the position
of the permutation with one index labeling,
4673.04 -> but we're working with zero index labeling, okay
becomes k minus one to fit. We're working with
4679.68 -> zero index labeling. To simplify the math, we get
the right result when we divide and use modules.
4688.48 -> Who can start the loop now, while n is greater
than zero, Portland is an factorial factor of
4694.24 -> n divided by an avant the index of the
element to take is k divided by potluck.
4700.96 -> After getting the index of
the next element, which is I
4704.16 -> who are unused of our to our permutation, and
we delete the element at index i from N used
4710.56 -> before moving to the next permutation with
decrement N, and k becomes k models pot length.
4717.84 -> After the loop, our permutation is built, we just
join its elements into a string and return it
4723.44 -> will return the case permutation
as required by the problem.
4728.72 -> Basically, the solution will may now use this
math to keep calculating the part of the case
4732.88 -> permutation belongs to, because by knowing it, we
know what is the next element to take from unused
4738.56 -> and use, which is the array of elements we
didn't use yet. For the time complexity,
4744.32 -> creating a news cost and creating factory
costs are plus one and film get costs. And
4750.72 -> then the while loop gets repeated while and
is greater than zero. And Angus recommended
4754.96 -> that each iteration, so the number of iterations
is equal to the initial value of an inside it,
4761.44 -> all operations are in all one, except popping the
element I found and used can have the case where
4766.88 -> we need to shift all the elements to the left
and entered all the elements of the permutation
4773.36 -> were four n plus n squared plus one who got an O
of n squared time complexity, way better than O of
4779.12 -> n times n factorial of the first solution. And
for the space complexity, we have n for a news
4785.2 -> and permutation and n plus one for fact array, two
m plus one gives us an O of n space complexity.
4793.6 -> Where is the end of this video? I hope that
you at least understood the general idea of
4797.36 -> the second solution, which is dividing the
perimeter Asians into pause with a common
4801.52 -> element and calculating which part of the key
permutation belongs to see you the next lecture
4813.68 -> Welcome back to the course in this lecture, we
will solve the minimum window substring problem,
4819.04 -> we have two strings SN T, and we're asked to
find the shortest substring of us that contains
4824.48 -> all characters of T. If such a substring
doesn't exist, return the empty string.
4830.48 -> For example, if we have this input as output, we
get C E A, B, E, ba, is the shortest substring
4837.28 -> of our salt contains all characters of t, in all
the words, two A's, one B and one C. First of all,
4845.28 -> how can we know that a string contains all
characters of another one who can't know it by
4850.08 -> having the counter frequencies of each string,
the one we use in the valid anagram problem,
4856 -> if record is the counter of as one and for to the
counter of as two, for every distinct character of
4861.6 -> as two for one of CH must be greater than or equal
to for two of CH in other words, as one must have
4868.32 -> at least the number of occurrences of CH and
s to encode will write for each CH in for two.
4875.04 -> If rec one of CH is smaller than freq, two of
CH will return false after the loop return true.
4882.8 -> Knowing this, we cannot really think of a
solution, the brute force solution, which covers
4887.6 -> all possible substrings of us while keeping track
of the shortest wall that has all characters of t.
4893.44 -> In Code, who can add an early exit condition. If
t is longer than us, we can't find the substring
4899.04 -> that satisfies the condition, there isn't enough
characters without glue join the empty string.
4904.96 -> Same result when t is empty,
who can return the empty string,
4908.4 -> because technically, the empty string contains
all the characters of the empty string.
4914.32 -> Else who first create a counter for T to
know the frequency of each character in it,
4919.28 -> let's name it for t. We also need the string
shortest that represents the shortest valid
4924.88 -> substring that we found until now, it initially
has amples one characters to be sure that it gets
4930.08 -> updated as soon as we found the valid sub train.
Now we start traversing substrings of us to do so
4937.68 -> we start by traversing the length, because we will
start by traversing substrings of one character
4942.88 -> than substrings of two characters and so on.
This is why learn goes from one to adding clauses
4950.48 -> inside it, whichever starting positions, because
with the same length, we have the substring the
4955.673 -> source at index zero, the water source at index
one, and so on. But it doesn't go until the end
4963.04 -> to avoid going out of bounds when adding the
length I goes from zero to n minus length in
4969.96 -> clause if we have the starting position, which is
I will have the length of the actual substring.
4976.48 -> So we can extract the actual substring is the one
between I in clause 11 i plus length fix clauses.
4984.48 -> Now that we got the substring, we'll create a
counter for it. Let's name it for us, after it
4990.88 -> will give the actual substring replaces
the shortest one who found until now,
4995.2 -> for that two conditions, the actual
substring must contain all characters of t,
5000.56 -> we can't know it when the function we made and
it must be shorter than the actual shortest one.
5006.48 -> The length of the actual substring is length.
So if length is smaller than length of shortest
5011.04 -> will replace shortest becomes the substring.
After the loop who don't don't quote on shortest,
5018.32 -> because it's possible that we didn't find any
substring that contains all characters of T
5022.96 -> to know that we took the length of
shortest. If it's still n plus one,
5027.2 -> it means that it doesn't get updated, we return
the empty string as required by the problem,
5032.48 -> else return shortest. Basically, we return
shortest one is length is at most n.
5039.44 -> For the time complexity, let's say that
n and m all lengths of Sn T respectively,
5044.56 -> will have N for building for T and n plus one for
creating shortest. Then we have n iterations for
5050.8 -> the outer loop animal's life plus one iterations
for the inner loop. And inside it the cost of
5056.24 -> extracting the substring. And generating the
counter depends on length. We also have the
5061.68 -> cost of checking if it contains all characters,
which is because in the function which covers
5066.4 -> characters of reg T, their number is at most m we
get this sum which is equal to one divided by six
5073.6 -> times n times m plus one times three M plus two
and plus four was simplify. And in the worst case,
5080.08 -> T is shorter than s. So M is smaller than
n. We're going off and coupon complexity.
5086.32 -> And for the space complexity, we have amphiphilic
T amples, one for shortest and for sub n n for
5092.72 -> fracas we'll get three and Paul samples one,
which gives them off samples and space complexity.
5100.24 -> This solution is obviously very slow is
not the best one. This is why we will move
5104.48 -> to the second solution. Inside the inner
loop, we have a cost of length to extract
5110.4 -> a cost of length who generate the counter and cost
of arm to check if it contains all characters?
5116 -> What if we try to reduce this cost to over one?
To get a constant cost per in a loop iteration?
5122.4 -> Follow me well, how can we extract
the substring and old one? In reality,
5127.44 -> we will need to extract the substring and our
second solution, who will just work with the start
5132 -> and end indexes of the substring? Which are i and
i plus length, we already know them. Second thing,
5138.72 -> how can we generate the counter of the actual
substring and oh one, the trick is to not always
5144.16 -> build the counter again, who will use the one
of the previous substring. Let me show you how.
5151.36 -> Emergent that we have this
string, US ABC a D CB AC.
5158.24 -> And the first sell triangle five characters has
this counter two A's, one B, one C and one T.
5165.76 -> Starting from this counter, how can we get the
counter of the next substring of five characters,
5170.4 -> which is this one? To do. So we'll just increment
the number of occurrences of the character that
5175.52 -> went out of the window and increment the number
of occurrences of the character that went in
5180.08 -> the window. The one that went out is a it was
in the first substring, but not in the second
5186.32 -> with decrement fracks of A, it becomes more
than the one that went in is he it's in the
5193.28 -> second substring, but not in the first one
who increment for x of e, it becomes one.
5199.84 -> And we got the new countering old one because
no matter the length of the substring,
5204.32 -> we need to work on two characters, only the
one that went out and the one that went in,
5209.68 -> there will always be only two because
we're moving by one position at a time.
5215.52 -> Then for the next substring. Same logic, the one
that went out is B so with the command for X of B
5221.36 -> and the one that went NTC. So increment for x
of C. And the process continues like that for
5227.92 -> all sub strings of length five. The technique
we're using here is called sliding window.
5234.48 -> In our example, we were using a window of length
five. Then to move to the next substring we don't
5240.64 -> start again from the beginning, we just move the
window by performing the necessary changes. And we
5246.48 -> just focus on what went out of the window and what
entered not what's inside because it won't change.
5254.08 -> Last thing to optimize the cost of
checking if it contains all characters,
5258.64 -> the cost is actually M because we need to
traverse characters of rec T Mobile let me
5263.36 -> show you how to optimize it. In our example, T is
ABC a it has three distinct characters A, B and
5270.96 -> C. So we have three conditions to respect to say
that our substring contains all characters of t,
5277.12 -> the conditions are at least two occurrences
of a at least one occurrence of b, at least
5282.64 -> one occurrence of C. The idea to avoid always
traversing all the characters, which can cause
5288.56 -> um, is to keep track of how many conditions
are satisfied. And for the actual substring,
5294.64 -> the number of satisfied conditions is equal to the
length of reg T, which has a number of distinct
5299.36 -> characters of t, then the actual substring
contains all characters of T It's a valid one.
5306.4 -> Okay, but some characters are going out of
the window and some of them are accurate,
5310.56 -> which means that when moving the window, some
satisfied conditions can become unsatisfied,
5315.6 -> and vice versa. Some unsatisfied conditions
can become satisfied how to handle that.
5322.8 -> To do so, after incrementing the number of
occurrences of the counter that went in,
5327.6 -> if it's in fact T and frakkers of want
n becomes equal to FRAC to point n,
5332.16 -> it means that we didn't have enough occurrences
of the characters that went in. And now we do
5336.96 -> so a new condition is satisfied,
who increments satisfied.
5343.04 -> And before decrementing, the number of
occurrences of the character that went out
5347.2 -> if it's in fact T and for us of one out is equal
to for active one out, it means that we had enough
5352.72 -> occurrences of the characters that went out, but
after decrementing, we won't because for us of one
5358.4 -> out will be smaller than what's required. This
is why we Diekmann satisfied, a condition that
5363.68 -> was satisfied before is not satisfied anymore.
And we decrement for x of one out obviously.
5371.12 -> For example here we have these strings SN t
and we have this window of seven characters,
5376.4 -> the conditions are at least two occurrences
of a at least one occurrence of p
5381.36 -> at least one occurrence of C. Here we have one
occurrence of a two occurrences of B and one
5387.76 -> occurrence of C. Only two conditions are satisfied
not enough. Let's move the window. Now he wants
5394.96 -> out but we don't care because it's not a character
of t with the command for X but nothing happens.
5401.6 -> And a went in who increment for X of A
and it becomes equal to fracture of A,
5406.48 -> we satisfied a new condition, the number
of conditions is equal to length of rec t.
5411.76 -> So the substring is valid, it contains all
characters of reg T, all conditions are satisfied.
5419.6 -> We move the window, now see what's out of the
window, and is number of occurrences in the
5424.56 -> substring is equal to the number of occurrences
in t. So, when we decrement because it's one out,
5430.32 -> the condition becomes unsatisfied.
We don't have enough C's anymore.
5435.44 -> And the answer is the window. But we
don't care. It's not a character of t.
5440.64 -> Now the number of satisfied conditions is smaller
than what's required. This substring doesn't
5445.36 -> contain all characters of t. And the process
continues like that. Once again, no matter
5452.56 -> the length of the window, we're dealing with two
characters, only the one that went in and the one
5457.84 -> that went out. So checking if the actual substring
is valid because of one we've been able to
5464.88 -> optimize extracting the substring, generating the
counter and checking if the substring is valid.
5470.56 -> We've seen how to do all these in old one. But he
didn't see the code yet. Let's move to the code.
5478.16 -> We keep the same old exit condition, we
generate the counter of t. But now we don't
5482.96 -> save the shortest string itself. We just save it
started and position. Initially shortest sources
5489.76 -> a string of samples one characters, so initialize
thought and and zero and amples one respectively.
5496.88 -> Now we start traversing lengths. What we were
doing in the example is to update frogs according
5502.88 -> to characters that went in and out compared to
the previous position of the window. But to do so,
5508.56 -> we first did an initial window that's
also zero and hose the length is length
5513.04 -> arrow, traverse it normally to fill frogs
and count the number of satisfied conditions.
5519.28 -> We create fracks and recreate satisfied a
variable to keep track of the number of satisfied
5524.16 -> conditions. It initially starts at zero because
we didn't start traversing characters of as yet,
5530 -> we didn't satisfy any condition. Then we
traverse characters of the first window,
5536.88 -> for each character ch will increment flux of
ch. And if CH is a character of T and flux
5542.96 -> of CH becomes equal to react, you have ch now
the number of occurrences of CH became enough,
5548.48 -> a new condition is satisfied, who increments
satisfied. After processing the first window,
5554.88 -> we check if it's a valid substring before moving
to all the ones and if it should replace the
5559.52 -> actual shortest one. If satisfied is equal to
length of reg t, the number of conditions and
5565.76 -> length is smaller than the length of the actual
shortest substring, which is add minus thought
5570.96 -> replace, start an N becomes zero and length
respectively, the boundaries of the first window.
5578.48 -> Now we can start traversing all the
sub strings are the same length,
5582.48 -> I start at one and zero
because the first sub string,
5585.6 -> which is the first window is already
processed, we start from the second one.
5592.08 -> We want to work with the character that went out
of the window and the one that went in bought,
5596.96 -> where are them. The actual substring is between
indexes I in clauses when I post length exclusive,
5604.32 -> the character that went out comes just before
the window. So its index is i minus one.
5609.84 -> And the one that went in is the last character of
the window, its index is i plus length minus one,
5616.48 -> we can start working, the character that entered
the window is opposition ai plus length minus one.
5622.24 -> So increment for x of s of Ai plus length minus
one. Now if it's a character of T and its number
5628.48 -> of occurrences and the substring became equal to
the number in t, it means that the new condition
5633.2 -> is satisfied, we write if as of apples length
minus one in fact T and flux of hours of eyeballs
5639.44 -> length minus one is equal to freq T of s of i
plus length minus one, we increment satisfied.
5647.52 -> After it, we work with a character that went out
the one at index i minus one if it's a cocktail of
5654.08 -> T and S number of occurrences and the substring
is equal to its number of occurrences in t
5658.56 -> it means that a condition was satisfied but not
anymore, because we will decrement for x of s
5663.12 -> of n minus one. So it will become smaller than
freq T of s of i minus one not enough occurrences
5668.88 -> of x of i minus one anymore. We write if as of i
minus one in fact T and for x of s of i minus one
5676.08 -> equal to T of s of i minus one with the
cumin satisfied will also satisfied condition
5683.76 -> after it with the CaroMont
for x of s of i minus one.
5689.92 -> Now that we know the number of satisfied
conditions by the actual substring the one between
5694.56 -> i and i plus Lang who can check if it replaces the
actual shortest one, we write If satisfied equal
5700.8 -> to the length of reg T and length is smaller
than n minus thought, we replace thought and
5705.6 -> by i and i plus length respectively, we found a
shorter string that contains all characters of T.
5712.16 -> After the loop, soften and represent the
boundaries of the shortest substring,
5716.4 -> but only found one. If underline his thought
is greater than n, then we didn't update
5721.68 -> start and end, we turned the empty string
because we didn't find any valid substring.
5726.8 -> Else, we told the part of us between starting
clause event and X closet. What about the time
5735.2 -> complexity, we'll have time for building for T
n iterations for the outer loop. Then inside it,
5741.2 -> we have linked iterations for the first loop,
and one is length iterations for the second bond,
5746.16 -> and all operations inside the mind of
one plus n for returning the part of us
5752.56 -> length plus and minus length gives n and we
can ignore M, we've got an O of n squared
5757.2 -> time complexity, the space complexity doesn't
change. You can see that now we've been able to
5764.64 -> reduce the time complexity from F and Q to off
n squared isn't enough. No, we can do better.
5772.32 -> When using sliding window, we have the case where
the window size is fixed. For example, if we have
5777.28 -> an array of integers and are asked to find the
key consecutive elements with the greatest sum,
5782.08 -> we use a window of size k, we will move
it but we won't change its size because
5787.44 -> we know that the array we're searching for
is of length k. However, in our problem,
5793.44 -> we don't know the size of the shortest
substring that contains all characters.
5797.36 -> This is why we tried all possible lengths,
which are sub strings of length one
5801.76 -> than those of them do, and so on, which
resulted in an O of n squared time complexity.
5809.36 -> But we have another way of manipulating the
window, instead of sliding the window by
5813.52 -> one position. In other words extended from the
right by one and reduce it from the left by one,
5819.12 -> what we can do is to extend it from the right by
one, but reduce it from the left by a number of
5824.16 -> times that is between zero and the length of
the window. Depending on what we want to do.
5830.4 -> Let's apply to our problem.
5834.16 -> Theory of the strategy that we're going to use
is to find the shortest substring that answer the
5838.88 -> actual index of write that respects the condition,
which is containing all characters of tea.
5845.52 -> Obviously keeping track of shortest one among
the more the one that will be returned our via
5852.24 -> let's start for the first index, we find an A
but no condition is satisfied, we need to as
5858.96 -> next index, we find d, we don't care about it.
Next index we find c a condition is satisfied.
5866.48 -> Next index if we don't care. Next
index e we don't care. Next index B,
5873.36 -> the second condition is satisfied, but not all
of them. Next index e we don't care. Next index
5880.4 -> see we have two Cs now, better condition is still
missing. Next index, he won't care. Next index
5888.16 -> a, we now have two A's, which is
enough to satisfy the last condition.
5894 -> All conditions are satisfied now, it means that
the substring from left to right in clause is
5898.72 -> valid. But is it the shortest one that answer
the index, right? Not true. Because we may
5904.56 -> have characters that we don't care about by
characters that we don't care about, I mean
5909.92 -> characters that we can remove without breaking
the validity of the actual string. And these
5915.12 -> characters are characters that are not in TRL and
calculus of t that are in excess in our substring.
5922.08 -> For example, if we need to see is only and we have
five C's in our substring who can remove the first
5927.52 -> three wants to make the substring shorter while
satisfying the condition. Remember that our goal
5933.52 -> is to get the shortest valid substring. Who cannot
remove from the metal because characters of a
5940.48 -> substring must be ages. And we cannot remove from
the right because we're searching for the shortest
5945.6 -> valid substring that answer the actual position
of right. So we can only remove from the left
5951.68 -> will keep removing while the characters position
left is a character we don't care about.
5958.88 -> Here the character off left is a
it's in T and it's not an excess.
5963.04 -> We need two A's and we have exactly two. So
this one is important. We cannot remove it.
5969.04 -> We finish removing from the left. So the
shortest substring that answer right is this one
5974.24 -> is length is smaller than the actual shortest
one, we update. We move to the next position of
5980.08 -> Freud who find the be the one at left is still
important. So the shortest one is this one.
5985.76 -> But we don't update because it's not the global
shortest one. Next position, we find an E the
5992.16 -> counter left is still important. Next position we
find to be the character left is still important.
5999.6 -> Next addition, we found in a and here is where
things change, because the character at left
6005.28 -> is not important anymore. The reason behind it
is that we found another A, which means that
6010.24 -> the character is now in excess, we can remove
the first one without breaking the Validate
6016.96 -> he will move a and with the
command is number of occurrences.
6020.96 -> Let's see if we can continue removing D is not
an important character is not in T, we move it
6027.92 -> C is in T but we have more than enough
we have two C's while we need only one
6032.8 -> we move and decrement is number of occurrences
of is not empty. Remove is not empty, remove it.
6040.72 -> These in excess we remove it is not empty, we
remove it. C is in T and it's not in excess.
6048.24 -> So we stopped removing. We found out that the
shortest valid substring that antithyroid is c
6053.92 -> e a b e BA and it's like the seven smaller than
the length of the actual shortest one replace.
6061.84 -> Let's continue. We'll move to the next position of
right. By the way, if you're wondering why aren't
6068.08 -> we going back to the beginning going to increment
right is because we know that characters before
6072.8 -> the actual position of love aren't important.
We don't need the for the actual substring.
6080.4 -> Who found the D the cow top left is
still important and we don't update
6084.48 -> because the length is not smaller than seven.
6088.4 -> Next position who find half the characters
left is still important and we don't update.
6094.24 -> Next position we find the seat which means that
the character at left is not important anymore.
6099.52 -> The character sees in excess we can remove it is
not in T we also remove it is important because
6107.44 -> it's in T and it's not in excess we stopped
removing we get a B e b a DFC, which is not
6114.16 -> shorter than the actual shortest. We don't update
we continue with on D and A still important.
6121.44 -> Next position we find f is still important.
Next position, we find c an ACL important.
6128.96 -> Basically it will continue like this for the next
five positions. And there is no update because the
6133.92 -> substring is getting longer. We're not being able
to remove from the left and in the next position
6140.88 -> we find an eight so the one on the left is not
important anymore, we remove it. These in excess
6146.88 -> we remove it is not empty, we move it be still in
Excel. So remove it is not in Excel. So we stop
6156 -> the substring is a DFC, DFC BFC BA, but not short
enough to update. last index, we find d and a
6166.32 -> still important, we don't update and we finish
traversing as the global shortest substring that
6172.64 -> contains all characters of t is the one between
indexes seven and 13 and clauses, it c a b e BA,
6181.2 -> take some seconds to process what you've
seen until now before continuing the video.
6189.6 -> Let's move to the code. We keep the same URL
the exit condition we build for it as we did
6194.56 -> previously, we initialize thought and add on
zero and respectively. We initialize satisfied
6199.92 -> zero regret for x which is empty at the beginning.
And we add a variable left that represent the left
6205.52 -> boundary of the window here and started on and not
n plus one because now Andrew presents the last
6212 -> nfo the window is in closet. Also, you can see
that we created frogs and satisfied outside the
6218.08 -> loop because we won't traverse lengths as we did
in the previous solution. We don't need to do that
6223.68 -> will darkly traverse positions of right the right
boundary of the window for each position right
6230.32 -> we increment the number of occurrences of the
character obviously, an objective is satisfied a
6234.96 -> condition as we did in the previous solution if
as of right is in fact T and flux of arthritis
6240.56 -> equal to for active as a Freud who satisfy the
condition so increments satisfied. Basically the
6247.2 -> path before satisfying all the conditions. This
is what we need to do only incrementing the number
6252.48 -> of occurrences and checking if we satisfied a
condition remember that we're expanding from
6257.28 -> the right only less remains zero. But once we
satisfy all the conditions which we can verify
6265.28 -> with this condition, satisfied equal to length
of FRAC t we can start removing from the left.
6271.76 -> We don't know how many characters are we going
to remove from the window. So we use a while
6276.16 -> loop. We saw that we keep removing characters
while the character has left is an important
6282.32 -> and a character that is not important. means
that either is not a character of the origin
6287.12 -> access means we have more than what's required. We
write while as of last noted for akti or flux of
6293.76 -> us have left greater than for active as of left.
Inside the loop, we move the car out which means
6300.88 -> that we decrement its number of occurrences
in frogs and move left to the next position.
6306.48 -> Now that we removed all unnecessary characters
who go the shortest valid substring? That answer
6311.52 -> the actual position of right is the
one between left and rotting clause if
6317.04 -> what do we do now, we check if it
replaces the actual global shortest one.
6322.56 -> The length of the substring, we found now is
right minus left plus one plus one because
6327.44 -> this time the right boundary, which is right
is included in the window. And the length
6333.44 -> of the actual global shortest one is and minus
thought plus one plus one for the same reason.
6339.92 -> So if right minus left plus one is smaller
than and minus that plus one, we update,
6344.64 -> start and end become left and respectively.
After the loop, almost same return statement,
6351.04 -> we just add plus one because and is included in
the window. Now, if we could update at least once
6357.36 -> we turned the part of ASP video installed and
adding clause if else return the empty string.
6364.8 -> By the way, you can see all of this time, we
weren't checking if we lost a satisfied condition.
6369.52 -> Because we stopped removing as soon as we reached
the minimum required occurrences will never
6374 -> go below it. This is why when the counter had
left was important. We weren't removing at all,
6380.56 -> not like in the previous solution when we were
removing no matter what. For the time complexity,
6387.28 -> we have an for building for T and
the outer loop does n iterations
6392.16 -> is true that we have an inner while loop where
the tricky part is that its number of iterations
6396.96 -> doesn't exceed n in total. I repeat in total.
Why? Simply because at each iteration of the
6402.88 -> while loop, we're removing a character and we
have n characters. remaining operations are
6408.88 -> owned over one. So the cost of the outer loop
isn't over. And yes, oh if and only not more,
6415.76 -> who else pause and for extracting the output.
And in total, we have ample of ampersand,
6420.72 -> we'll give some of ample time
complexity better than O of n squared.
6426.64 -> And for the space complexity, same as the previous
solution of m plus m. And we've been able to solve
6433.6 -> the problem in off campus m time only by
using a bunch of interesting optimizations.
6439.84 -> One was a tough problem, I hope that you
understood how we built our optimal solution
6444.72 -> that you will be able to use it to solve all the
problems. We've reached the end of this video,
6450.16 -> it was a long one. But I tried to detail
each operation to let you understand what is
6454.8 -> each line of code doing and how the algorithm
works in general. See you in the next video.
6466.48 -> Welcome back to the course in this lecture, we
will solve the largest rectangle in histogram
6470.88 -> problem. We are given an array heights that
contains the height of each bar in the histogram.
6476 -> And we're asked to return the area of
the largest rectangle in the histogram.
6480.72 -> Know that each bar has a width of one. For
example, if we have this input here is the
6487.2 -> largest rectangle. It's area seven times five,
which gives 35. How can we solve this problem?
6494.56 -> Let's for example, take this bar, it has a
height of two. Now, can you tell me what's
6499.68 -> the largest rectangle of high two that passes
from this bar? Is this one. But how did we know?
6506.48 -> Let's start from that bar and keep expanding? Can
we expand to the left? Yes, three is greater? Can
6512.32 -> we expand? No, because we have no more bar from
the left? From the right now can we expand? Yes,
6518.56 -> four is greater? Can we expand? Yes, five is
greater than two. In other words, this bar is
6524 -> higher so our rectangle can pass from it. Can we
expand? Yes, seven is greed. Can we expand? Yes,
6530.4 -> six is greed. Can we expand? No, we can't expand
from here because one is smaller than two. So if
6536.64 -> we expand, the rectangle won't be fully included
in the histogram is not a valid rectangle.
6543.52 -> We expanded as much as possible from both sides,
we go the largest rectangle that passes the
6548.16 -> initial bar is this one, it has an area of 12 Two
times six, the height multiplied by the width.
6556.72 -> And we can apply this strategy on each bar
while keeping track of the greatest area
6561.12 -> of the end who will have found the greatest
area, because the largest rectangle necessarily
6566 -> passes from a bar that has the same height as
itself. The reason behind it is that if the
6571.52 -> rectangle is shorter than all the bars it passes
from, it means that it's not the largest one,
6576.24 -> you can still make it bigger by increasing its
height. And if it's taller than at least one bar
6581.92 -> learn is not fully included in the histogram.
It's not a valid rectangle. With this example,
6589.28 -> with the first bar we get this rectangle with
the second bar we get this rectangle and so on.
6599.44 -> The end The greatest area that we
find is 35. The area of this rectangle
6607.52 -> encode we initialize Max area to zero because
we didn't traverse any rectangle. Therefore,
6612.8 -> each bar I expand from both sides from each side,
we keep expanding while the bar is still higher or
6619.6 -> as high as our bar. So we stopped when we found
the shorter one, or when we have no more bars.
6627.44 -> Left thoughts are the actual position, then
while the previous bar exists and is at least
6631.68 -> as high as the actual bar, we expand, we
move left by one position to the left.
6637.6 -> Same logic with the right side but
by incrementing, right starts on I,
6641.92 -> then while the next part exists, and is at
least as high as the actual bar, we expand,
6646.56 -> we move right by one position to the right. While
right plus one smaller than N and height of right
6652.16 -> plus one greater than or equal to height of
AI, we increment y to take it to the right.
6658.88 -> Now that we know boundaries of our
rectangle, we need to calculate its area.
6663.52 -> The area of a rectangle is the height multiplied
by the width, the height here is the height of
6668.16 -> the initial bar height of i, and for the width is
the difference between left and right plus one,
6674.48 -> right minus left plus one plus one because both
left and right are included in the rectangle.
6681.84 -> Now we check if replace Max area becomes
the most between its actual value and the
6686.32 -> area of the actual rectangle heights of our
multiplied by right minus left postponed.
6692.32 -> After the loop, we just return max area.
6696.4 -> For the time complexity, we're traversing the N
bars, and for each bar when searching for left
6701.92 -> and right boundaries, who may traverse the whole
histogram. This is why we get an O of n squared
6706.96 -> time complexity. In the worst case, the worst
case happens when all bars have the same height.
6713.12 -> And for the space complexity, it's
constant, we're just using eight variables.
6719.52 -> This solution is slow. Let's move to the next one.
There are interesting properties to know about the
6725.84 -> shortest bar. The first one is that by starting
to make a rectangle from it, we can expand it
6731.12 -> until the boundaries of the histogram because
there are no shorter ball to stop the expansion.
6737.12 -> Second one, the rectangle starting from
any other ball can't pass through it,
6741.52 -> except if it has the same height, but
we get the same rectangle in that case.
6746 -> So the shortest part is like a wall, any other
rectangle will either be on his left side or on
6751.44 -> his right side. From these two information, we
can make a solution based on divide and conquer.
6758.24 -> We search for the shortest bar, and we have a
rectangle that traverses the whole histogram
6763.36 -> will also recursively search for the
largest rectangle in the left side,
6766.96 -> the largest rectangle in the right side, and
we take the maximum among these rectangles,
6772.08 -> it represents the largest rectangle in the
whole histogram. The reason behind it is
6777.76 -> that because our bar is the shortest one, we
can't have a taller rectangle that joins the
6782.56 -> left on the right side, a taller rectangle will
either be in the left part or in the right part.
6788.16 -> So we don't worry about missing the larger
rectangle, we can search in each side separately.
6794.48 -> We also consider the rectangle host the height
is the height of the shortest bar, the one
6798.72 -> that traverses the whole histogram, because
it's possible for it to be the largest one,
6803.84 -> even if it has the smallest height, but its
width can make it the most interesting rectangle.
6811.12 -> Encode recruiter recursive function that
takes us parameters the array of heights,
6815.44 -> but also low and high the boundaries of the part
of the histogram we're searching in right now. Or
6822.24 -> the beginning we search the whole histogram. So
low and high will be initialized to the index of
6827.12 -> the first and the last bar. The first base case is
where the actual part is empty. While low exceeds
6833.92 -> right, we just return zero, we have no rectangle.
Second base case one, we have only one bar,
6840.88 -> one low is equal to high. In those case,
we just returned the height of that bar.
6846.16 -> Else, we have the recursive case, we'll start by
calculating the position of the shortest bar in
6850.96 -> the actual part. For that, we calculated
the smallest height in the actual part
6856.16 -> between low and high in clause IV, then we
search for its index in the outro part again.
6862.88 -> Now that we have it, we recursively search for
the greatest area and the left and right sides.
6868.72 -> For the left part, we put postman minus one
as the right boundary. And for the right part,
6873.76 -> we put postman postman as the left boundary.
URL for the short put wide rectangle, its height
6879.76 -> is the minimum height we calculated before and
its width is the whole path we're searching in
6885.2 -> high minus low plus one. So we turn the maximum
between from left form right and mean eight times
6892.24 -> high minus low plus one. This one represents
the area of the short but while rectangle
6898.72 -> we also need a long question function to call
this one, the initial values of low and high
6903.2 -> are zero and n minus one, the index of
the first and last bar respectively.
6908.8 -> For the time complexity, in the best case,
the shortest bar is always in the middle.
6913.68 -> So in recursive cases, we divide the input size by
two, we have infosearch. And for the men, and two
6919.92 -> times t of n by two for cursive calls, we get t of
n is equal to two times t of n divided by two plus
6925.76 -> n. By using the master method, this recurrence
relation gives off n log n time complexity.
6933.36 -> But in the worst case, the shortest bar is always
the first or the last bar. For example, when
6938.64 -> it's the first one, from the love, the input size
becomes zero, we get to zero. But from the right,
6944.32 -> the input size becomes n minus one, we get to
have animals one plus n to search for the minimum,
6950.72 -> we got t of n is equal to t of n minus one plus n.
And if we keep replacing, this recurrence relation
6957.12 -> gives off n squared time complexity, same as
the previous solution is like we didn't often
6964 -> what's slowing down the process is finding the
minimum its causes and to search for the minimum
6969.04 -> in the run who are searching for. But we can
optimize this by using a segment tree for example,
6974.88 -> you can reduce the cost of searching for the
minimum and arrange to look at the recurrence
6979.92 -> relation becomes t of n is equal to t of n
minus one plus log n, we get off n log n plus
6986.56 -> n to build the segment tree, we've got an O of n
log n time complexity, but if n over n squared.
6994.96 -> But we still have two solutions to discover.
6999.2 -> The strategy we use in our first solution is dot
for each bar, we search for the next shorter bar
7004.64 -> from the left the next shorter bar from the right,
and we calculate the area of the rectangle bar
7010.56 -> always traversing bars again to search resulted
in an O of n squared time complexity. What if we
7016.48 -> can traverse the histogram only wants to find the
next shorter bar of each bar? Yes, it's possible
7022.24 -> by using a stack, we can maintain a stack and
in increasing order. For example, we have 2478,
7030.56 -> then we want to insert five, but it wouldn't
be increasing anymore. So we'll keep popping
7035.76 -> until we find a smaller element. And we push
it remains increasing. Then again, we'll have
7042.48 -> six 910 12/3. To insert eight will pop 12 will
pop done, we put mine and insert, and so on.
7056.72 -> And we can use this principle for our problem
will work with heights will maintain a stack and
7063.12 -> to follow the next shorter bar from the left of
the actual bar who keep popping into the top of
7067.68 -> the stack becomes shorter after it will also
push the actual bar for the next iterations.
7074.56 -> Let me show you how it works with our example.
We can add two bars of height minus one at
7080.24 -> extremities to avoid having an empty stack minus
one to be sure that they will be shorted at any
7085.6 -> bar or the beginning, the stock contains
the bar zero, and will start from bar one.
7092.4 -> The top of the stack is shorter, who already
found the next shorter is at index zero. And
7098.96 -> we'll push the actual bar. Next index, the top
of the stack is higher Ooh pop. Now it's smaller,
7105.84 -> the index of the next shorter is zero, and we'll
push the actual bar. Next bar top of the stack
7112 -> is shorter, we already found next shorter is
the bar index two and we push the actual one.
7119.04 -> Next bar, same thing, top of the stack
is shorter. Next bar same thing. Next
7124.96 -> bar who performs and we find it next bar, we
have to pop all of them except the last one
7131.76 -> because they are all higher. Next bar, the top
of the stack is all really short, its index is
7137.2 -> seven, next bar are really shorter. And it
continues like this for the whole histogram.
7159.2 -> Now we got the index of nav shorter
bar from the left of each bar.
7162.56 -> But we still need the one from the right. So we
can apply the same process but from the right.
7169.04 -> The Start Now initially contains the rightmost
bar, the one we added from there, who is the
7173.76 -> height is minus one. First of all from the right,
the top is already shorter, and we push. Next bar
7181.04 -> we put once and we find the index we also push
next bar already shorter. We write and we push.
7188.88 -> Next bar, same thing we write and we push.
Next bar same thing. Next bar, same thing.
7196.24 -> Next bar we pop twice, we write and we push
next bar, we put once we write, and we push,
7203.68 -> next bar, we pump thrice, we write, and we
push, and the process continues like that
7225.2 -> now for each bar, we have the index of the next
shorter bar from the left the index of the next
7230 -> shorter bar from the right, we can calculate the
largest rectangle that passes from the actual bar.
7235.84 -> For example, for this one, next
shorter bar from the left is zero.
7239.68 -> From the right, it's seven.
So we get this rectangle
7244.4 -> to get the largest one in the whole histogram,
whichever is largest rectangle of each bar,
7248.96 -> while keeping track of the global largest
one, as we did in the first solution,
7253.36 -> but we don't need to search again here. And we've
been able to solve the problem by traversing the
7259.36 -> histogram only thrice instead of n times, which
will reduce our time complexity to O of n.
7267.28 -> Encode who first are those two bars of height
minus one not extremities, then we create an array
7273.2 -> from left or from left of it represents the index
of the next shorter bar from the left of the bar,
7278.16 -> I will also create a stack that initially
contains the first bar, the one we added.
7285.6 -> Now for each bar, except once on extremities, who
keep popping, while the bar on top of the stack
7290.48 -> is higher, or as high as the actual bar, we write
wild heights of stock of minus one greater than or
7296.8 -> equal to heights of oil, we pump stock of minus
one represents the top element. After the loop,
7304.48 -> the next shorter bar from the left is on top of
the stack, we assign it to from left, I will also
7310.56 -> push the index of the actual bar i. We finished
filling from left, who will do the same thing from
7317.2 -> the right, acquired from right, we initialize the
stock by putting the last bar only and we start,
7324.48 -> now we traversed bars, but in the reverse order.
Remember that we start from the right and we move.
7331.92 -> Same logic for what's inside the loop.
But we assigned to from right of it now.
7337.04 -> After having both arrays filled, we can start
working to initialize Max area to zero, then for
7343.12 -> each bar, who took it who replaced Max area, Max
area becomes the maximum between its actual value
7349.44 -> and the area of the rectangle of the actual
bar. The height of the actual bar is height
7354.32 -> of AI. And the width is fomite of i minus from
left of i minus one minus one. Because the next
7360.72 -> shorter bars are not included in the rectangle,
we don't count their width. So the area is height
7367.28 -> of I times from right of i minus from left of
i minus one after the loop return max area.
7376.32 -> For the time complexity, we have n to add those
bars and integrate from left. And now for the loop
7383.146 -> is true that we have a nested while loop where
the total number of iterations won't exceed
7387.68 -> and because each bar is pushed and
popped only once. And we have an bars
7392.16 -> so the cost is N. Same logic for the process
from right, and we add on to search for Max area.
7399.84 -> We're getting off on time complexity. And for
the space complexity we have and for heights
7406.56 -> and for the stack, and for from left. And and for
form, right we're going off and space complexity.
7415.52 -> In this ocean, whichever is the histogram
thrice, but we have a solution where we
7419.76 -> traverse it only wants let's talk about it. Okay,
imagine that we have this bar as a first bar,
7426.4 -> we can still expand it from the right because
we didn't find the shorter one. The next bar
7431.2 -> is this one, you can still expand them both,
we found nothing that stops them. Third bar,
7437.12 -> same thing. Fourth bar, same thing, you can still
expand them all because the hearts are increasing.
7444.72 -> And we're putting them in a stock by the way.
Both for example, the next bar is this one,
7450.48 -> this bar will love the previous three bars
stop expanding because it's shorter than them.
7455.68 -> In other words, all bars that
are taller than it in the stack.
7461.04 -> And because now we know where these bars stop,
we can't calculate the largest rectangle, the
7466.32 -> actual bars at index four, so they stop at index
three. For this bar, here's the rectangle for the
7473.6 -> next one of the stack. Two is the rectangle.
And for the next one, here is the rectangle.
7479.92 -> We stopped poppin because the top of the
stack is shorter, so it can still expand.
7485.84 -> You can see that what we're doing is that we're
pushing our bars into a stack. Then when we found
7490.56 -> the next shorter bar from the right, we know
where they stop, we calculate their rectangle.
7497.12 -> Now we push this point we continue this bar
Higher, we have nothing to pop without clear
7502.4 -> push it. But for this one is shorter. So we pop
this one, and we calculate the rectangle. The
7509.76 -> top is still taller, we pop on we calculate the
rectangle, put weight with this bar, the largest
7516.32 -> rectangle that we can make is not this one is this
one. The reason behind this one result is that
7523.6 -> the index of a bar is not necessarily for Maurice
largest rectangles thoughts, in reality is largest
7526.64 -> rectangle thought form where the last
popped bar thought iterations thoughts.
7534.16 -> For example, for this one, remember that we have
three bars, this one was the last one, it means
7540 -> that the largest rectangle starts from here. This
is why when we push bar, we keep the same height,
7545.68 -> both as index we put the index where the
rectangle of the last popped bar starts.
7551.92 -> Let's work with a greater example, the
one we've been working with in this video,
7557.36 -> we can add those two bars of height minus
one extremities to avoid having an empty
7561.52 -> stack. First bar, the bar on top is shorter,
we totally put it on the stack. Next bar,
7568.96 -> the bar on top of the stack is taller. So we
found the end of its rectangle, its Imani spawn,
7574.72 -> the top of the stack is not small anymore, who
stopped poppin. But now when we push this bar,
7581.12 -> as high throughput to both as index, we put the
index of the last pop bar, which is one let's
7588.24 -> continue for is taller, we just push with
this index because we didn't pop anything.
7593.76 -> Next bar, same thing. Next bar, same thing.
Next bar we need to pop. And we found the end
7600.32 -> of this bar here is it's rectangle. And
when we put six as index, we put five.
7606.48 -> Next bar, we need to pop here is the largest
rectangle of the pop the bar is beginning is
7612.48 -> the index we pushed and is and is i minus one, we
can calculate the rectangle and see if it replaces
7618.8 -> top is still higher, we pop top is still
higher, we pop top is still higher, we pop,
7625.2 -> you can see that for each prompt bar, you
can easily find his largest rectangle,
7630.56 -> top is not higher anymore, we stop. And the
starting index of the last pop node is one.
7636.32 -> So we put an index of one when pushing the actual
bar. The reason behind it is that from the left,
7642 -> our bar can extend until the index one from
the road we don't know yet. Next bar higher
7649.84 -> without the push, next bar, same thing. And
the process continues like this until the end.
7665.68 -> After finishing, we found the largest
rectangle is this one, we turn this area.
7672.24 -> And we've been able to solve the problem
by traversing the histogram only once.
7678.48 -> In code, we start by adding those bars
of extremities will create Max area,
7683.12 -> we'll create a stack and we'll start traversing
bars. The stack initially contains the first bar,
7690.16 -> the one that we added. And you can see that now
we're storing both the index and the height.
7696.08 -> In the previous solution, we stole the
index only because we could calculate
7699.52 -> the heart from the hearts array. But
this time, the pushed index is not
7703.76 -> necessarily the one where the bar is in the
histogram. So we store both. And this time,
7709.92 -> we need to traverse the bar of the right
extremity to empty the stack to calculate
7714.24 -> rectangles of bars that are still in the stack.
So I start from one and goes until the last bar
7720.96 -> at each bar, I will need a variable start that
indicates for more the largest rectangle of
7725.68 -> the bar our thoughts. Remember, that is the
starting index of the last bar we popped.
7733.52 -> But we didn't start popping yet. So we set it
to I now we start poppin while the bar the top
7740.88 -> of the stack is higher or as high as the bar our
we bought, we put the index and the height into
7746.24 -> variables. Remember that we need to calculate
the largest rectangle of the pumped bar.
7751.6 -> It's hard is the pushed height. It's taught
index is the pushed index. And it's an index is
7757.04 -> our minus one. So its width is i minus one minus
top index plus one, which is I'm on a stop index.
7765.2 -> We check if it replaces Max area Max
area becomes max between its actual value
7770.08 -> and top height times I'm on his top index.
7774.32 -> And we're searching for the start index of
the last pop bar. So start receive stop index.
7780.88 -> After the loop stock moves the start index of
the last popped bar and the height of the actual
7785.84 -> bar is height of I we push start heights of AI and
after the outer loop, we're done Max area thoughts
7796.32 -> for the time complexity, once again the inner
while loop will do a Most alliterations in total,
7801.84 -> because each bar is pushed and popped only
once we've got an O of n time complexity,
7806.48 -> and for the space complexity off, and
because of the stack and height array.
7812 -> We've reached the end of this video. In this one,
we've seen different solutions to this problem.
7816.4 -> I hope that you understood them all. And
that was the last problem of this course.
7824.4 -> Congratulations for finishing this course. I hope
that you learned a lot of new things from it,
7829.04 -> and we'll be able to apply them in all
the situations. To learn even more. You
7833.68 -> can check the other courses I made, like the
50 popular coding interview problems course,
7838.64 -> check the links below. Also, please tell
me what you thought about this course.
7843.44 -> If it's good, if it's bad, what should be
improved, etc. See you in another occasion.
Source: https://www.youtube.com/watch?v=Peq4GCPNC5c