# Ultimate DSA Revision Guide 2024 for Coding Interview | DAY 1 | Best way to revise DSA

https://www.youtube.com/watch?v=CyHgGm3NOmA

[00:00] hi everyone welcome to my channel code
[00:01] with bya so as you might have understood
[00:03] from the thumbnail we are here for the
[00:05] DSA revision guide but this is not just
[00:08] another video which will help you um
[00:11] which is going to tell you that how to
[00:12] revise DSA how to make notes while
[00:14] revising DSA this is not that video okay
[00:17] so what are we here for today let's say
[00:20] you have a tech interview planned from a
[00:22] week or two from now so we know the pain
[00:26] of sitting with your notes your Excel
[00:28] sheets and so many lead code questions
[00:31] and it is scattered everywhere and you
[00:33] have to all the things you have to
[00:35] consolidate and then sit for the
[00:37] revision so we are here to streamline
[00:39] that process for you by ourselves
[00:42] helping you directly revise the DSC
[00:44] questions by doing this multiart series
[00:47] and that is what we are going to do
[00:48] today uh I mean starting from today that
[00:51] this multiart series will consist of
[00:53] videos where we have handpicked certain
[00:55] DSA questions mixed and match with
[00:57] different data structure with different
[00:59] algorithm
[01:00] and using that it is like you just have
[01:03] to reserve maybe maximum 1 hour in a day
[01:06] to revise the questions and you'll be
[01:08] done so it will be a very streamlined
[01:10] process because we will talk about the
[01:11] code example solution U the approach The
[01:15] Brute better optimal time and space
[01:17] complexity we have a detailed
[01:18] documentation of that but what is this
[01:21] video for if you already have a
[01:22] documentation what is this video for it
[01:24] is going to help you in two ways number
[01:26] one the more you watch these videos as
[01:29] part of of this series it will help you
[01:31] gradually build a thought process
[01:33] because we are trying to make it more
[01:35] and more streamlined and make it more
[01:37] clear like we want to introduce more and
[01:39] more clarity because you have everything
[01:41] scattered we know that you have done the
[01:42] questions we know that you know the
[01:43] questions but everything is scattered
[01:45] everywhere okay now to sit with all of
[01:48] that on your own to revise can be boring
[01:50] and frustrating so we are here to help
[01:52] you with this process which will help
[01:54] you build a clear thought process when
[01:55] you're solving the question and the most
[01:57] important thing is to help you form
[02:00] patterns in your brain and this is very
[02:01] important like you might have heard
[02:03] about coding patterns coding interview
[02:04] patterns patterns in your brain is
[02:06] important because when you encounter a
[02:08] similar question before I mean later on
[02:10] in the interview you'll be like before I
[02:12] have done this question somewhere so
[02:14] this is how we had done it now I just
[02:15] have to tweak the approach a little bit
[02:17] so the videos if you watch this is going
[02:20] to help you in achieving these two
[02:21] things and if you have these two things
[02:24] revising DSA becomes a very smooth
[02:27] process it is not at all difficult so
[02:30] that is what we are trying to achieve
[02:31] with this and we help and we hope that
[02:33] we can achieve this objective of ours uh
[02:36] the only assumption is that you have
[02:38] done the questions before whatever we
[02:40] because we are not going to do a
[02:41] complete dry run of every question we
[02:43] have already done dedicated uh questions
[02:46] and the videos in our other playlist but
[02:49] this a quick and clear and crisper
[02:51] revision as soon as you can do it and
[02:54] that is why I'm saying like just reserve
[02:56] one hour in a day and try to revise the
[02:58] questions that is it you need so so too
[03:00] much of talking I don't want to waste
[03:02] any more time let's dive into it that's
[03:04] it very simple code so now with one
[03:07] question we see how did we structure our
[03:08] a thought process see the question the
[03:11] example The Brute Force the time and
[03:13] space complexity brute better optimal
[03:16] see the code wrap it up that's it you're
[03:19] done with the revision moving on to the
[03:21] next
[03:22] question I'm not going to take so much
[03:24] time for every question because this was
[03:26] the first question that is why I just
[03:27] tried to elaborate starting with the
[03:29] first question called contains duplicate
[03:31] so we are just warming up by doing some
[03:33] very simple easy problems and the best
[03:35] part is we're going to mix and match the
[03:37] questions okay so this is a lead quote
[03:39] question like many of you would have
[03:41] already done it practiced it before
[03:43] given an integer array uh you have to
[03:46] return true if it if the element appears
[03:48] twice in the array at least twice and
[03:51] you have to return false if every
[03:53] element is distinct so you know that you
[03:54] have to return a Boolean value you're
[03:56] given an array and you have to apply the
[03:58] logic accordingly
[04:01] now what is the first thing like you go
[04:03] through the question you understand the
[04:05] examples so when you sit for revision
[04:06] you see see the question you see the
[04:08] examples and then you start thinking in
[04:09] your mind what could be the way to solve
[04:12] it how how should you ideally do is you
[04:15] see the question run through the
[04:16] examples now because this is very simple
[04:19] it may take you 5 to 10 minutes hardly
[04:21] to try to think of the solution and
[04:23] maybe write the code but I'm just
[04:24] telling you in a very general way see
[04:26] the question go through the example
[04:28] pause the video and think about it what
[04:30] you can do to solve this question Take 2
[04:33] minutes 5 minutes replay the video okay
[04:36] resume the video now we will see what
[04:38] can be the approach we'll start to form
[04:40] a thought process around this so what we
[04:42] will do see I have tried to document it
[04:45] like this first we will see The Brute
[04:47] Force if there's a better way and then
[04:49] brute better optimal so what is a brute
[04:51] force the very first thought in a knif b
[04:54] would be maybe to have two arrays now
[04:56] I'm sure many of you would have done
[04:57] much better solution than this but just
[04:59] trying to give you an example of how
[05:02] things should be think of it like a
[05:03] complex problem how it would be like
[05:05] your brute force will be a very like a
[05:08] very naive way of doing the Sol like
[05:12] like the brute force will be the very na
[05:13] way of trying to solve it so in this
[05:15] case we have o of n Square we try to
[05:17] make it little better by trying to sort
[05:20] the array so when we try to sort because
[05:22] all the duplicates will get lined up
[05:24] adjacent to each other which will give
[05:26] us a Time complexity of n log okay
[05:30] and the next thing is we will have haset
[05:34] which is the optimal way of storing
[05:35] because set will only allow the unique
[05:37] elements not allow the duplicates so if
[05:39] I see the code for this code if you see
[05:41] what we are trying to do is we are
[05:43] trying to add to the set if the number
[05:45] is not there so so long the number is
[05:47] not there in the set it will keep on
[05:49] adding 1 2 3 4 but again if one is
[05:51] encountered so at that time it is not
[05:54] going to add so what it will try to do
[05:57] is it is going to say that hey I it's
[05:59] already existing so it will be returning
[06:01] false and then this condition will be
[06:03] true and we are going to return true
[06:05] that's it very simple code so now with
[06:08] one question we see how did we structure
[06:10] our thought process see the question the
[06:12] example the proot force the time and
[06:14] space complexity brood better optimal
[06:17] see the code wrap it up that's it you're
[06:20] done with the revision moving on to the
[06:22] next question the next question is
[06:25] product of array except s so what we
[06:28] have to do in this let's take a
[06:35] look so we are given an array integer we
[06:38] given integer array nums you have to
[06:40] return an array answer such that the
[06:43] answer of I is equal to the product of
[06:45] all the elements of the integer the
[06:48] array except the number itself product
[06:51] of any prefix or suffix is guaranteed
[06:52] okay so you must write an algorithm
[06:54] which has to run in O of n now when you
[06:57] see this you will like you will have to
[06:59] think of the solution in the optimal way
[07:01] but still even if you cannot think at
[07:03] first go what is the optimal way of
[07:05] solving this let's try to think what can
[07:07] be the Pro Force way of solving this
[07:09] pause the video for a while and think
[07:10] about it but yeah also let's see the
[07:12] question except the current number your
[07:16] I mean in the new array in the output
[07:18] that you have to give you are given an
[07:20] input array and you have to also give an
[07:21] output array so this output are at that
[07:24] particular index the product will be
[07:26] equal to the entire product except the
[07:28] current number like over here the entire
[07:31] product of this array is 24 okay so
[07:35] except this so if I just exclude one
[07:38] from it it is going to be 24 but for in
[07:40] case of two if I exclude two like 24
[07:43] divided by 2 it will be 12 that is why
[07:45] it is like that now take a pause and
[07:48] think about what can be the Brute Force
[07:50] way of solving this see The Brute Force
[07:52] way can be to calculate the product of
[07:55] all the elements of each element I mean
[07:58] product of all the other element
[07:59] elements for each element and then try
[08:01] to store that but we also have to handle
[08:03] the case of zero but the very first
[08:05] thought process will be again to have
[08:07] two Loops that is why the time
[08:09] complexity of of n square but if we can
[08:11] calculate the product of it at
[08:14] beforehand okay and also store count the
[08:17] number of zeros store the count of that
[08:19] and compute the total product with the
[08:21] help of that we can try to achieve it in
[08:23] one go in one iteration so let's see the
[08:25] code for that
[08:29] so here we need to Output this answer AR
[08:32] so we have initialized that initially
[08:35] let's have the product as one and now we
[08:38] are trying to Traverse through this
[08:39] array we are checking whenever we
[08:42] encounter a zero we will keep a track of
[08:44] all the zeros so that is why we need
[08:45] this count variable otherwise if it is
[08:48] not zero then we just going to multiply
[08:51] with our final product like we just
[08:53] trying to get the product of the entire
[08:55] array so that is what we have to do so
[08:57] this for Loop is just for calculating
[09:00] the total product of all the elements of
[09:02] the array and keeping track of the zero
[09:05] so this much this part is doing next we
[09:07] are again doing an iteration this time
[09:10] we are checking couple of
[09:11] things so there can be four cases so
[09:14] imagine this is the array we have 1 2 3
[09:17] we have zero and we have four so if the
[09:20] count of count of zero is Zer sorry if
[09:23] the count of zeros is one there's only
[09:25] one zero in the array the product at
[09:28] every position is always going to be
[09:30] zero because suppose you are over here 2
[09:33] into 3 is 6 6 into 0 is 0 so anywhere at
[09:37] every position at every nonzero position
[09:40] your answer will be zero but if you have
[09:44] only one zero but you have only one zero
[09:48] for the for the index where you have a
[09:51] zero present for that particular index
[09:53] the product is going to be the original
[09:55] product because for this zero the rest
[09:57] of the product is 6 into 4 is 24 so 24
[10:01] is going to be over here for everywhere
[10:03] else it is going to be zero this is very
[10:05] obvious to understand this two cases are
[10:07] covering that you have only one zero
[10:09] there can be two things now if there are
[10:12] more than one zero then very obvious the
[10:14] entire product I mean for every index
[10:17] the answer of the output array is going
[10:19] to be zero and what is the last option
[10:22] we have that okay that you have no zeros
[10:24] in the are it's a happy case so you will
[10:27] just divide it like we were seeing that
[10:28] particular example example let's say we
[10:29] do not have 0 1 2 3 4 at every place it
[10:32] will be total product divided by the
[10:34] number at itself like the number itself
[10:36] at that particular index that is what
[10:38] product by product divided by nums of I
[10:40] that's it and you just have to return
[10:42] the answer so these four cases is what
[10:44] you have to remember if there are one
[10:46] zeros if there is one zero what will
[10:48] happen if there are two zeros what will
[10:50] happen if there are zero zeros this is
[10:52] the only thing we have to remember
[10:53] that's it next question is three sum
[10:56] closes so let me open this particular
[10:58] question and there is a variety which is
[11:01] similar like three sum closes three sum
[11:03] and the two sum so these are similar
[11:05] questions we'll try to see the code of
[11:06] all of them and try to compare what is
[11:09] the question over here you will be
[11:11] required either to find out the sum of
[11:13] three integers or may be required to
[11:16] print the triplets so this is the
[11:17] triplet sum issue problem so you are
[11:20] given an integer array and a Target here
[11:22] you have to find the such a sum of three
[11:25] numbers or three integers Which is
[11:26] closest to the given Target in the some
[11:29] problem it was like the sum should be
[11:32] equal to zero over here it is like you
[11:33] have to find the sum Which is closest to
[11:35] the Target and this is the example which
[11:37] is over here you can take a pause and uh
[11:40] read the example so what is the initial
[11:42] thought process that we have to find out
[11:43] the triplets whenever you have to find
[11:45] out the triplets the thought process
[11:48] like you have to maybe uh use for Loop
[11:50] to generate the triplets and check that
[11:53] is the very initial BR Force way of
[11:54] doing it but we will be using two
[11:57] pointers to try to optimize the solution
[12:00] so our optimal approach is going to be
[12:02] sorting and using two pointers even in
[12:04] case of the three sum problem we will be
[12:06] able to do this but let me first show
[12:08] the code of the three sum so that we can
[12:11] find that a little bit relatable the
[12:13] three sums code and over here how are we
[12:17] applying the two pointer technique is we
[12:19] are first sorting the
[12:22] array so we first sorting the array and
[12:25] then we are doing the traversal we're
[12:26] skipping the duplicate because that was
[12:28] given in the
[12:29] leave that come to the main point the
[12:31] main point is we using two pointers we
[12:34] are using two pointers like this having
[12:37] the for Loop and we are generating a sum
[12:41] like this is the sum which we are
[12:42] calculating as a reference point whether
[12:44] this sum the first nums of I plus the
[12:48] left and right where is the left and
[12:50] right they are at the extreme ends of
[12:51] the array now if these three generator
[12:54] sum equal to zero we have found one
[12:56] triplet okay otherwise we will have to
[12:59] generating otherwise you have to shift
[13:00] the pointers and that is what is being
[13:02] done over here everything else is just
[13:04] to handle the duplicate so the main gist
[13:06] of this question is you will apply first
[13:08] of all you'll sort the array so that you
[13:10] can apply the two pointers and then you
[13:12] try to find if the sum is equal to zero
[13:14] if it is equal to zero you'll add it to
[13:17] your output list but if it is not you'll
[13:19] try to shift the pointers so this is the
[13:21] threesome problem above I have shown
[13:24] this because with the help of this this
[13:27] is going to be the foundation to now see
[13:29] the see and understand the code for
[13:31] threeome closes so now if we go to this
[13:38] question so what is the code for
[13:41] threeome closest it will be very much
[13:43] similar the only difference is now we
[13:46] will not
[13:50] be so the only difference is here also
[13:53] we sorting it here we will try to check
[13:56] which is closer so we have a reference
[14:00] point of the closest sum the first three
[14:02] numbers will take as the closest sum and
[14:04] then we continue generating the sum with
[14:06] the nums of I the left and the right and
[14:09] we check whether sum minus Target is
[14:11] closer or closest
[14:13] minus closest Su minus Target is closer
[14:16] whichever is the closer that becomes our
[14:17] new closest sum that is why closest sum
[14:20] is our reference point always and
[14:22] incrementing and decrementing the
[14:24] pointers of left and right Remains the
[14:25] Same so the structure of the code is the
[14:28] same for three sum and three Su closes
[14:30] the only difference is here we are not
[14:31] comparing with zero we are checking
[14:34] whether the given Target and the given
[14:37] sum which is closer whether my sum minus
[14:39] Target is closer or the previous closest
[14:41] sum that I have captured if that is
[14:43] closer that is the gist of the question
[14:45] that's all you need to
[14:48] know what is the time complexity for
[14:51] this are we using an extra space
[14:54] no we are not using an extra space
[14:59] but we are sorting the array so we know
[15:01] that when we sort the uh when we sort
[15:03] the array it is n log so the time
[15:04] complexity for this is going to be n log
[15:07] question is longest consecutive
[15:16] sequence so this is a medium L quot
[15:19] medium question uh like I said I'm going
[15:22] to mix and match Shuffle the questions
[15:24] so that it's not like we doing easy easy
[15:26] questions only or we are doing medium
[15:28] questions only so I'm just trying to mix
[15:30] it up okay so we are given an unsorted
[15:33] array integer nums return the length of
[15:35] the longest consecutive element sequence
[15:38] what does okay and you have to run it in
[15:40] or and time so what does it mean let's
[15:42] see the example the longest consecutive
[15:45] sequence you have to return what is the
[15:46] sequence the sequence over here
[15:50] consecutive sequence is four because it
[15:52] starts from one 2 3 4 so the longest
[15:54] sequence the length of that sequence is
[15:57] four so you have to return the length of
[15:59] that sequence and over here if I start
[16:02] from zero we have 0 1 2 3 4 5 6 7
[16:12] 8
[16:13] uh okay we have two zeros so it should
[16:16] be like two like z z so that is why okay
[16:18] that's why the output is so this is what
[16:20] you have to do over here you have to
[16:22] start from one particular number and
[16:24] make sure that there is a next it's like
[16:27] iterator do has next kind of a thing
[16:28] thing and if it has the next number that
[16:31] number plus one exists in the array then
[16:33] you'll just have to do it think about it
[16:36] take a pause think about it how you can
[16:38] solve it and then we'll discuss further
[16:40] so here's the Brute Force way of solving
[16:42] since I want to sort I mean since I want
[16:45] to have the numbers in consecutive
[16:47] adjacent order I can sort the array I
[16:49] can have a Max counter and just iterate
[16:51] through like 0 0 1 two just increment
[16:53] the counter as it goes now I will
[16:56] increment it only if the current element
[16:58] is one more than the previous like the
[17:00] num plus one and I can update the
[17:02] maximum counter value which can store
[17:04] the length of uh my current sequence and
[17:07] if it is a different number I will break
[17:09] that sequence what is the time
[17:11] complexity o of an login so this is the
[17:13] Bro Force way of thinking it this could
[17:15] be the group Force way of thinking it
[17:17] another way could be using a hashset
[17:20] which will be taking up more space but
[17:22] at least is going to give you a time
[17:24] complexity of O ofn so how are we going
[17:26] to see do this let's see the code for
[17:28] that Direct
[17:38] okay so we will use a hash set and we
[17:42] need to keep a track of the lens so
[17:44] we'll have a max length we will use a
[17:46] set set will not allow duplicates all
[17:48] the unique numbers are added to the set
[17:50] first once we add the numbers to the set
[17:52] we again iterate through every number of
[17:54] the set now try to pay attention over
[17:56] here this is important okay so we need
[17:59] to understand this we are checking if
[18:03] the number is already contained in the
[18:06] set if it is see I've written check if
[18:09] it is already in the set if it is skip
[18:11] the number what does it mean pay
[18:14] attention over here very carefully if
[18:17] there is a number I mean okay given a
[18:19] number at a num set if you have a number
[18:23] if you already have a previous number of
[18:24] that so num minus one is already
[18:26] contained in the set so you encounter
[18:28] two and you see that in your set you
[18:30] already have one so I'm going to skip
[18:32] two because I have to start the sequence
[18:34] from one only so I'm going to skip that
[18:36] that is why I'm doing this not contains
[18:38] if it doesn't contain only then I'm
[18:40] going to start from here otherwise I'm
[18:42] not going to start from here I'm going
[18:44] to start from the previous number now if
[18:46] I come across one and I see in the set
[18:48] that there is a zero I'm going to
[18:50] discard one but if there is no zero in
[18:52] the set then I'm going to start that my
[18:54] starting point is this and that is what
[18:56] we are doing over here if it doesn't
[18:58] contain if it doesn't contain only then
[19:01] I will say my current num my num becomes
[19:04] my current num and my length is one so
[19:06] now I I'm going to start my sequence and
[19:08] I iterate through the consecutive
[19:10] numbers checking if my current num like
[19:14] which my num became my current num if
[19:16] that plus one if the next adjacent
[19:18] element is contained in the set if it is
[19:21] contained in the set because look up in
[19:22] the set is O of one if it is contained
[19:24] I'm going to increment my number I'm
[19:26] going to increment my length two things
[19:28] I to do I have to increment the length
[19:30] very obviously I need the length of the
[19:31] sequence I have to increment the number
[19:33] because I have to check for the next
[19:34] number so if one is there I see that 1 +
[19:37] 1 2 is there in my set great I have to
[19:40] do now 2 + 1 I have to check if three is
[19:42] also there in my set then I have to
[19:44] check if 3 + 1 is four is also there in
[19:46] my set and so on so while that is why I
[19:49] put this inside a while condition you
[19:51] will keep on checking + one + one + one
[19:55] you will keep on doing on the numbers
[19:56] and you'll keep on incrementing your
[19:58] length
[19:59] okay and when you come out of this means
[20:02] you have exhausted your your particular
[20:05] chain or sequence of number is exhausted
[20:07] now you've got some other number so you
[20:09] will update your max length so this is
[20:11] how you may find short chains of
[20:13] sequence and whichever is the largest
[20:15] chain of sequence that length you will
[20:17] be storing in your max length that is it
[20:19] that is the question all about keep a
[20:21] haset to keep track of the numbers iter
[20:24] it through the haset because look up in
[20:26] the hash set see all the numbers are
[20:28] jump jumbled up over here right so all
[20:31] the numbers are jumbled up how can we
[20:33] achieve constant time we have to use a
[20:35] set that is why why are we using a set
[20:37] because I want to do a look up look up
[20:39] every time plus one num plus one num
[20:41] plus one check or maybe I'm doing a num
[20:43] minus one check every time I have to do
[20:45] a look up in the constant time only then
[20:47] I'll be able to achieve the time
[20:49] complexity of O of n that is the reason
[20:52] that is the reason why I have to
[20:53] maintain a set and because of that I am
[20:56] able to achieve the O of one that is one
[20:58] one thing secondly because I'm able to
[21:01] check that I'm also able to uh meet this
[21:04] condition inside a while loop and I'm
[21:06] doing the incrementing operation so it
[21:07] is like a win-win for me I'm able to
[21:10] check also and I'm also going to do my
[21:11] business logic and updating the max SL
[21:14] that's it so this is how your code will
[21:17] be and this is the optimal way of
[21:19] solving this particular
[21:21] question the next question that we will
[21:24] do is longest common prefix so let's
[21:27] check this question
[21:35] okay this is easy question uh we have to
[21:38] write a function to find the longest
[21:40] common prefix amongst an array of
[21:43] strings you given an array of string as
[21:45] the input you have to find out the
[21:47] length sorry you have to find out the
[21:49] string the string itself which is
[21:51] basically you have to find out the
[21:52] prefix which is common to all the
[21:54] strings inside the are so as we can see
[21:57] over here straightforward simple
[21:59] question simple looking question uh l l
[22:02] f l o is not okay f is common between
[22:05] flower and flow but not over here so the
[22:07] only common string prefix string is L so
[22:10] that is what you have to Output over
[22:11] here over here none of them is common so
[22:15] this is The Edge case so you have to
[22:16] return empty string if there is no
[22:18] common prefence that's it take a pause
[22:22] see how can you use the string
[22:23] manipulation methods think about it and
[22:26] then play the video again
[22:31] so here is the code for this first of
[22:34] all we check if uh like a sanity check
[22:37] if the length is zero if it is null we
[22:39] will return empty string and we uh try
[22:42] to return this particular
[22:46] prefix we first have a reference point
[22:49] over here what is our reference point
[22:51] the first element in that array Str Str
[22:53] of zero that becomes our first prefix
[22:56] okay
[23:01] now we take the we start iterating over
[23:05] this so this is my array over
[23:08] here I start the iteration from I equal
[23:11] to 1 now what I have to check this is an
[23:13] important condition which you have to
[23:15] remember if you're not very well vered
[23:17] with string manipulation or string
[23:18] Methods pay
[23:20] attention the number sorry the element
[23:23] in the array St strs one I the I ith
[23:27] element in the array dot index of prefix
[23:29] what does index of return the first
[23:31] occurrence the index of the first
[23:33] occurrence of this particular string
[23:35] whatever you pass within if the first
[23:37] occurrence of this is not equal to zero
[23:40] what does it mean but what does it mean
[23:43] like I said the flower and we had
[23:47] flow so if let's say flower is my prefix
[23:51] and I'm trying to check whether flow
[23:54] which is my St strs of I dot index of so
[23:58] is flower occurring somewhere in flow
[24:01] where it is giving me an index off of
[24:03] zero which means whether flower is
[24:05] contained in flow first of all it is not
[24:07] contain so let's say now I'm not
[24:09] checking flower I'm just checking flow.
[24:11] flow flow I can see that this particular
[24:14] string is already contained or let's say
[24:16] I'm checking FL I'm just checking FL so
[24:19] I'm checking if flow do index of FL does
[24:23] f start I mean IS
[24:27] F so what we're trying to check is
[24:29] within the string flow is the index of
[24:32] this particular string zero yes because
[24:34] it starts with e but if it was like I'm
[24:36] not checking L if I'm checking for Lo
[24:38] what will be my index of my index of
[24:40] will be one because L is starting from
[24:44] index one not from zero so I want to
[24:46] start the starting point the prefix that
[24:48] is why I'm discarding it before only if
[24:50] it is not equal to zero what I have to
[24:52] do I have to start chopping off so over
[24:55] here like I said first we had flower not
[24:59] not a prefix so I'm just going to remove
[25:02] the last character I'm just chopping off
[25:03] the last character and then I check if
[25:05] FL W is a prefix not again I'm chopping
[25:08] off the last so this is what I'm doing
[25:10] inside the while loop that is why I said
[25:12] said that pay attention over here first
[25:14] we're traversing but as long as my
[25:17] current element that is St strs of I is
[25:20] not giving me an index of zero I'm going
[25:22] to chop off the last character from my
[25:26] given prefix how am I doing it I'm doing
[25:28] a substring zero and the length minus
[25:30] one because this character will be
[25:32] exclusive so this character is removed
[25:34] and I'm only going to get the that like
[25:37] like minus the last character the rest
[25:39] of the string I'm going to do but while
[25:41] doing this if it happens that I have
[25:43] exhausted my entire prefix all the
[25:45] characters are gone it means that if the
[25:48] first two elements did not have anything
[25:50] common if these two elements didn't have
[25:53] anything common how will it have any
[25:55] common prefix with third or fourth if
[25:57] you see this particular question FL O W
[26:01] uh flower and flow have something in
[26:03] common at least FL these three
[26:06] characters are at least common so that
[26:09] is why we proceeded with the next but if
[26:10] there was like dog and race car nothing
[26:12] is common it will stop over there only
[26:14] the prefix is going to be empty that's
[26:18] it that is what the question is about
[26:20] very simple looking code it's a very
[26:22] lead code easy uh lead code easy
[26:24] question but you have to understand the
[26:26] playing of the string man you have
[26:28] remember it also that what are we doing
[26:30] and why we are doing why are we using
[26:31] the index of and why we are using the
[26:33] substring substring to chop it off index
[26:35] of to find the index that's
[26:39] it so my new prefix is going to be
[26:44] this next question is largest
[26:55] number so what does this question talk
[26:58] about given a list of non- negative
[27:00] integers arrange them such that they
[27:03] form the largest number and return it
[27:05] now the number result may be very large
[27:07] so you need to return a string instead
[27:08] of an integer okay you given an array of
[27:11] integer now from this integer array you
[27:13] have to return a string what by how
[27:15] you're going to return a string by
[27:17] rearranging the numbers in this integer
[27:19] array such that they form the largest
[27:21] number that is what you have been asked
[27:23] to do input is an array output is a
[27:25] string see this question 10 is there two
[27:28] is there but if you just do integer
[27:30] comparison it won't work you have to
[27:31] arrange it in such a way that it forms
[27:33] the largest number okay so now when you
[27:38] try to concatenate such a large number
[27:40] it is going to not going to fit into
[27:42] your integer uh data structure so that
[27:44] is why we are going to return it as a
[27:45] string so 10 and two if I just group
[27:48] this I can get 102 or I can get 210
[27:51] which is larger 210 so I have grouped it
[27:54] and found that this is my answer 210 now
[27:56] it becomes trickier when you have more
[27:58] than two or like three four five numbers
[28:02] in the array so there can be a lot of
[28:03] permutations that you can do so in that
[28:05] case it becomes tricky to write the code
[28:07] for this so it's it is simply not just
[28:10] going to be concatenating a plus B and B
[28:12] plus a so we have to think of it in a
[28:16] different way pause the video try to
[28:18] think about the
[28:24] solution yeah so the Brute Force way
[28:27] could be like I mentioned permutations
[28:28] you have to generate all different
[28:30] permutation by looping through it now
[28:32] when you generate permutations as we
[28:34] know it will going it is going to be
[28:36] like a recursive call and going to be
[28:38] exponential time complexity all of that
[28:40] stuff so that is why it is better to
[28:42] avoid it best we'll try to use the
[28:45] concept of comparators in string and
[28:47] let's see how we can use it okay there
[28:49] is one catch in this question remember
[28:52] that if at all by doing the
[28:54] concatenation we find that the first
[28:57] number uh is coming to be zero we will
[29:00] have to return zero like it cannot be
[29:03] like uh something like let's say uh
[29:06] after rearranging you got something like
[29:08] 0 2 3 4 5 so 0 2 3 4 5 it cannot be
[29:14] something like this so we have to just
[29:16] discard that kind of a number so that is
[29:17] a special case we have to handle when we
[29:20] have zeros as one of the element in the
[29:22] integer array so anyway let's see the
[29:24] code for this it will be more
[29:26] clear and let's
[29:28] understand now step by step how we are
[29:30] trying to form the answer for this so
[29:33] what is the input for me the input for
[29:35] me is an array now if I have to return a
[29:37] string I have to convert these integers
[29:39] into string so what is the first thing I
[29:41] have to do is I have to create a string
[29:42] array I have to do is I have to create a
[29:44] string array so that in my string array
[29:47] I'm going to do a string dot value
[29:48] convert my integers into string and
[29:50] store it that is the first thing step
[29:52] number one is this Step One is this to
[29:55] convert the integer to string now I have
[29:57] to create a comparator and this is what
[29:59] I was talking about if you do not know
[30:00] about comparators I have done a detailed
[30:02] video on comparator handson demo in my
[30:05] channel so you can refer to that so
[30:07] comparator will help me to define a
[30:09] strategy on how I should be able to sort
[30:11] these uh integers not integers the
[30:15] integer to string converted numbers okay
[30:17] so what it is trying to do this is the
[30:19] comparator it will take in two values
[30:21] now it is going to use this compared to
[30:23] Method where we are trying to put the
[30:26] large number like the large concatenated
[30:29] Value First followed by the small
[30:30] concatenated value that is why we are
[30:33] doing St we like we have a and b right
[30:36] we have a and b check if B and A and A
[30:39] and B do a comparison of these two so if
[30:42] B and a DOT compared to a and b and if
[30:45] this is greater okay put this one first
[30:49] followed by a and
[30:52] b and when we are trying to sort our
[30:55] this array of string we are going to use
[30:57] this comparator which we have defined
[30:59] over here because if you just reverse
[31:02] this it if it was like Str str1 plus Str
[31:04] str2 dot compared to Str str2 do Str
[31:06] str1 that would have been the normal way
[31:09] of approaching where you will have the
[31:11] ascending order like the smaller first
[31:13] followed by the larger that would have
[31:14] been the normal comparison but in this
[31:17] case the catch is that we will use a
[31:21] comparator the the catch is that we are
[31:24] trying to put the largest string so we
[31:25] are trying to do it in the descending
[31:27] order okay so that is why we are using
[31:29] Str str2 plus Str str1 do compared to S
[31:32] str1 Plus Str str2 we have sorted this
[31:35] array using this comparator now we have
[31:37] to handle the leading zeros if the if
[31:40] after doing this sorting now my new
[31:42] string array has a zero like a zero
[31:46] something like this then I have to
[31:48] return zero because I cannot have any
[31:50] largest number which starts or proceeds
[31:53] with a
[31:54] zero next we have to concatenate the
[31:57] sort string so now we have a string
[31:59] where we have the largest number first
[32:01] like 23 followed by let's say 14 and
[32:05] then five we have something like this so
[32:08] then I have to conat it so I can use a
[32:10] string Builder I'm going to conat
[32:12] through the array and I'm going to get 2
[32:14] 3145 this is going to be the new the new
[32:18] string that I have to return so we using
[32:21] this SV do2 string to return this output
[32:23] string so what were the steps that we
[32:26] have done
[32:28] first we used this first we converted
[32:31] the integer array to string array we
[32:32] used a comparator to sort our string
[32:35] array step number two and step number
[32:37] three was to handle the scenario of zero
[32:39] starting preceding zero and fourth was
[32:42] to concat so there was like one two
[32:44] three four steps and this is how the
[32:47] main gist was to create this
[32:49] comparator this comparator was the main
[32:51] important thing so this is how we can
[32:54] solve this question of finding out the
[32:56] largest number our next question is
[32:59] longest substring without repeating
[33:01] characters so let's see this
[33:03] question what are we going to do over
[33:05] here is we are given a string s and we
[33:08] have to find the length we have to find
[33:10] the length of the longest substring
[33:12] without repeating character so if you
[33:14] see this example uh we have the string
[33:17] now there are multiple substrings
[33:18] possible which substring has the longest
[33:20] length which also doesn't have any
[33:22] repeating characters which means I have
[33:24] to find a substring which has only
[33:26] unique characters number one and I have
[33:28] to make sure that the length of that
[33:30] substring is the longest so what is that
[33:32] substring over here as we can clearly
[33:34] see is a b and c or it can be even C A
[33:38] and B okay so these substrings have the
[33:41] longest l so we don't have to return the
[33:42] substrings we have to return the length
[33:45] Okay now take a pause think about it
[33:49] what can we use to solve this how can we
[33:51] actually try to find out the length so
[33:54] like I said there can be multiple
[33:56] substrings possible so the very first
[33:58] thought process I'll generate the
[33:59] substring check number one if it has
[34:02] unique characters for that I have to
[34:04] Traverse the substring and then I have
[34:06] to Ma I have to mark the maximum length
[34:09] that I have captured so far when I do
[34:11] that then only I'll be able to
[34:13] understand that if I have got the Max L
[34:15] at the end of the traversal so that
[34:17] again involves two Loops one Loop you
[34:19] have to just start at one point and then
[34:22] you have to generate all the substrings
[34:23] inside that in the Inner Loop is going
[34:25] to generate the substring of uh
[34:28] and the inner loop is going to keep on
[34:30] generating substring so basically this
[34:32] is going to give you o of n Square time
[34:34] complexity so this is where we will talk
[34:37] about sliding window algorithm so
[34:39] talking about the optimal approach we
[34:40] need sliding window so that we can
[34:42] optimize the time complexity and bring
[34:44] it down to O of n what are we doing we
[34:46] need a set we need to we need to have a
[34:48] set to keep a track of the unique
[34:50] elements and the two pointers now what
[34:53] are we going to do is we will try to
[34:59] we will add to our set only if the
[35:01] current element is not present so let's
[35:03] say I start with this example I have a I
[35:06] added to the set B I added to the set C
[35:08] I added to the set this is my substring
[35:11] and I've captured the max length is
[35:13] three I'm going to add to the set only
[35:15] when it is not contain this is what is
[35:16] this part is doing and I'm incrementing
[35:19] my J pointer the right pointer and it is
[35:21] happening inside a while great now let's
[35:24] say I encounter another character B so I
[35:27] was is going so far captured Max now I
[35:30] encounter B so J is over here I is at
[35:32] zero now because B is already contained
[35:35] in my set what am I going to do I'm
[35:38] going to remove from the set the
[35:40] character which is pointed by I now why
[35:43] why am I doing that because when I see
[35:45] that it is already contained in the set
[35:47] I have to reach to that
[35:51] point where my character of J is no more
[35:55] present because in my set B is already
[35:58] present so now I'll start chopping off
[36:00] from the left the characters because it
[36:02] is in my current substring it is B is
[36:05] already getting repeated so from the
[36:06] left side I have to start chopping off
[36:08] so that I get a current substring which
[36:10] doesn't have any repeating characters so
[36:12] now see I will remove a I'll remove a
[36:15] and I'll increment I point and this is
[36:17] my current substring now see the fun
[36:19] over here my current substring again has
[36:22] a repeating character when I check over
[36:25] here does the set contain the character
[36:27] of J yes B is again contained in this
[36:29] substring and that is what we are trying
[36:31] to prove right in my current substring
[36:33] there shouldn't be any dup there
[36:34] shouldn't be any repeating character
[36:36] there shouldn't be any duplicate so what
[36:37] will I do I'll again remove from the
[36:39] left hand side so I'll try to remove
[36:41] this B also okay now I ined now my J is
[36:45] still over here now it is going to check
[36:47] okay now B is not there in my in my uh
[36:51] current set so now because B is not
[36:53] there I can add B to my current set so
[36:56] at every given point in time notice we
[36:58] are also keeping track of the size of
[37:00] the set and now when I added B now my
[37:03] current size became two so you see that
[37:06] this is my current substring when I'm
[37:08] over here and my current substrings
[37:10] length is two which is C and B are two
[37:13] unique character so what is what are the
[37:15] unique character subst we got so far
[37:17] first we had got ABC we tracked the
[37:18] length as Max then we got BCB where
[37:21] again we have duplicate characters then
[37:24] now when we have this particular
[37:26] substance C and V this is my my correct
[37:27] substring which has two unique
[37:29] characters so I got c and b and I got
[37:32] ABC and I kept a track of the max so I
[37:34] captured that this particular length is
[37:36] greater so just give you a small dry run
[37:39] of what we are doing in trying to
[37:40] achieve number one we using a set number
[37:43] two we adding to the set if it is
[37:44] already not contained incrementing J
[37:46] pointer or the right pointer number
[37:48] three if already contained start
[37:49] removing from the left until and unless
[37:52] your set doesn't contain this particular
[37:54] duplicate character until and unless set
[37:57] doesn't contain this duplicate character
[37:59] you're going to keep removing that is
[38:00] why we are doing over here we will check
[38:02] if it contains no if it if it not
[38:05] contains add it if it contains remove
[38:07] from the a PO till you reach that
[38:09] particular till you reach that
[38:11] particular point where you can form a
[38:13] substring where it doesn't have any
[38:15] repeating character hope I'm able to
[38:17] make the point clear if not I also have
[38:20] a very detailed video on this and uh you
[38:22] can watch that video also as part of the
[38:24] sliding window playlist so these are the
[38:27] only things that we doing and we done
[38:28] with the code and we returning Max very
[38:30] obvious very small and simple
[38:35] code okay so the so the next question
[38:38] that we will be doing is Peak index in a
[38:41] mountain array so let's see what this
[38:42] question is
[38:44] about okay so an array is a mountain if
[38:48] the following properties hold that there
[38:50] should be at least three elements in the
[38:51] array and there exist some I where the
[38:54] elements before I is like in in
[38:57] increasing order and the elements after
[38:59] I is in decreasing order okay so given
[39:02] such a mountain array you to return an
[39:04] index such that this property is
[39:06] satisfied and we have to run it in O of
[39:09] log n complexity so whenever there's a
[39:12] binary search question few hints are
[39:13] very important one the array is sorted
[39:16] partially sorted number two you have to
[39:19] you have been asked to solve it in of
[39:21] login complexity okay so these are some
[39:23] of the hints that you can pick up so
[39:25] this is a clearly an example of the
[39:26] binary search algorithm and if you see
[39:29] this example 0 1 0 so it's like a peak
[39:33] so it has to be like something like this
[39:35] not sure if you can see this so it's
[39:38] basically like a peak so it goes from
[39:41] here till here and then it comes down so
[39:43] you have to find out what is that Peak
[39:45] and return that particular index so over
[39:47] here 0o then one and then Zero from here
[39:50] 0 2 and then one and zero so it's like
[39:53] two is the peak but you don't have to
[39:55] return the element itself but just the
[39:57] index of it okay now how essentially are
[40:00] we going to solve this question so
[40:02] here's the code which is written very
[40:04] small simple Speed code now binary
[40:07] search if you have done again the
[40:08] expectation is if you have come for
[40:10] revision you have at least done a couple
[40:11] of binary search we have these two
[40:13] pointers which we commonly call low and
[40:15] high one it's at the end of the extreme
[40:17] ends like start and the end of that and
[40:20] we calculate the mid while we're
[40:22] retreating over the low to high every
[40:24] now see either there are two parts right
[40:26] it's partially sorted this is the
[40:28] increasing order this is the decreasing
[40:31] order so your elements when you
[40:33] calculate the mid either it can be in
[40:35] this place or it can be in this place so
[40:37] that is what we are checking over here
[40:38] if the after calculating the mid you get
[40:41] to the mid of the array now you see
[40:43] whether that element and that element +
[40:46] one like if this is the mid and this
[40:49] these two are then the increasing
[40:51] sequence we at least need some hint are
[40:53] they in this sequence or in this so if
[40:56] they are in this sequence then where is
[40:57] my Peak if it is I am in this my Peak
[41:00] will obviously lie just ahead of me so
[41:03] that is why I have to increment my left
[41:04] or the low pointer so low will be mid +
[41:07] one otherwise I will be in this part but
[41:11] there's a catch you may be exactly at
[41:15] the
[41:15] mid so if you are exactly at the mid the
[41:20] number which is mid + one will be
[41:22] smaller than U and youu will be greater
[41:25] then this condition gets violated that
[41:27] mid is not lesser it is greater than
[41:30] this now because this condition gets
[41:32] violated it is possible that your
[41:33] current mid is the answer itself I mean
[41:35] your current mid is the peak itself
[41:37] because it can be at just at this
[41:40] boundary that your Peak and the peak
[41:42] plus one or it can be somewhere later
[41:45] whatever it is I'll capture the mid I
[41:46] don't want to take risk I'll capture the
[41:48] mid and I will just decrement my high
[41:51] because I have gotten to the decreasing
[41:53] part now I just have to go leftward
[41:55] because I do not know because CU I know
[41:57] that the peak will not be ahead it will
[41:59] be somewhere towards the left so I will
[42:01] shift my or Shrink my high pointer or
[42:04] the right pointer you can call it low to
[42:06] high or left to right whatever suits you
[42:08] that is it and finally you have to
[42:10] return the answer because I have
[42:11] captured now the possibility is that
[42:13] either your mid was the answer or it was
[42:15] not the answer if it was not the answer
[42:17] your mid will again change to another
[42:19] answer and you will decrement the height
[42:21] at some point you will break the loop
[42:23] and whatever answer you have captured is
[42:24] the correct answer that's it
[42:28] that is the question that is the
[42:31] answer so what are the things we did we
[42:34] had low to high simply we calculated M
[42:36] and the only thought process was either
[42:38] you find out whether your array whether
[42:40] your elements are in the increasing
[42:41] sequence or in the decreasing sequence
[42:44] and take the action accordingly which is
[42:46] justifiable based on the logic we gave