hey everyone welcome back to the channel I hope you guys are doing extremely well so this is another lecture from the Strivers A to Z DSA course so just in case you're for the first time here this is world's most in-depth DS algo course why do I say that because you can go over the entire internet buy any of the paid courses none of them will have 456 modules in this course alone we will be solving 400 plus problems on DS algo so at the end of the course you will be so well versed with Ds algo that you can clear any of the DS algor rounds in any of the interviews in any of the companies in any part of the world so till now we have completed till step two today we will be starting with step three which is nothing but arrays so in order to understand arrays what we will be doing is we will be solving 41 different problems so before moving into the problems let's understand some basic stuffs about array so when I say array what is an array so array is nothing but a data structure which contains similar elements now what do I mean by similar elements it can be integers but remember one thing if it's a data structure it has to contain integers only it cannot contain integers string it has to contain one particular type of data so imagine is integers so the array can contain all of them as integers or maybe as character or maybe as string or maybe as paired so array is a data structure which can contain any kind of data type but one thing has to be clear that all of those elements has to be of the same data type so now moving to the next Point how does an array look generically if I have to draw an array array is represented like this now what is the size of this array one two three four five six so the size of this array is 6 in order to declare an array of size 6 what what you can do is you can write ain't array 6 that will do if you're following Java it should be int array something like this new int and size 6 this is how you can Define in Java now if you are defining an array of size 6 whenever you define something like this what happens is an array of some garbage values is defined if you are defining it inside the main function like if you're writing something like int array and six so all of these six positions like this position this position this position all of them will be stored with some garbage values you cannot predict those garbage values but in case instead of declaring it inside the intervene if you decide that Hey listen I am not going to declare it inside the intervene I will be declaring it before the intervene this is what we call AS Global this is what we call AS Global so if you're going to define the array globally then all of them will be filled with zeros this is what happens in C plus plus Java okay I am not sure about python but should be something similar now you might be thinking then striver you have defined an array of size 6 what is the maximum size of array that we can Define so the maximum size of array that you can Define is 10 to the power 6 you can go ahead and say int array of 10 to the power 6 this is the maximum length of array that you can Define but there's a catch over here this is the maximum size when you declare it inside yes inside intervene this is the maximum size imagine you say that okay listen I am going to declare the array globally so if I go ahead and say okay over here is where I'll declare the array so if I declare the array globally then it will be 10 to the power 7 it will be 10 to the power 7 so the max size is 10 to the power 7 if you go ahead and declare it globally remember this now the next thing how do you access an array so there is is something known as index so in an array the first index is 0 followed by one then two then three then four so the last index is nothing but size minus 1 and the first index is nothing but zero so the array indexing is from 0 to n minus 1. in order to access any of the elements of the array what you can do is you can just loop from I equal to 0 because 0 is the first index you can go ahead till n minus 1 because n minus 1 is the last index and you can run the loop as I plus plus so if you go ahead and do a print of array of I what will happen is this will one by one first the value of this will be array of 0 so whatever you have stored at array of 0 imagine this is an array of integers and I'm storing like two three one four seven six so what will happen is first two will get printed then three will get printed then 1 then 4 then 7 6 this is how you can easily really access an array so before moving on to the problem solving let's understand where is array stored in the computer memory so can you predict it no can I predict it no so whenever you declare an array something like this it basically goes into the computer's memory creates a block of like size 6 block and the first block is stored in some random X address location so this address location no one can predict random X address location and this x is where it stores the zeroth index element but something we can predict is if this is X the next first index will be stored at X Plus 1 memory address the next as X plus 2 the next at X plus 3 the next at X plus 4 and the next at X plus 5 so contiguous memory locations is where all the corresponding indexes will be stored but we cannot predict X thereby accessing an array by address is not possible hence we address it by an index so this was about the basics of the array now let's move on to the problem solving so coming to step 3.1 the first problem is largest element in an array so before moving on to the problem I want you to tell something now whenever you go to an interview the interviewer will give you a question but if you know the solution should you say the solution directly the answer to that is no there is a reason why you are preparing you might know the solution but you should not tell it you should build the interview it's you who should drive the interview when I say Drive the interview now this is a very easy question but when I said write the interview imagine you have been asked a hard question and you know the optimize like the most optimized solution in terms of time complexity and space complexity should you see it directly whenever you are given the question no you should write the interviewer at first you should ask him about test cases then once you've understood the question properly you should give him the Brute Force solution which is the like the most normal solution that comes to your brain at first that is what you call as a Brute Force solution then you go ahead and maybe optimize it and maybe get something as a better solution now for every problem better might exist might not exist but a brute usually does exist you get a better one by optimizing The Brute then you optimize the better to get the most optimal solution so again there can be several other flows as well like brood better more better optimal it's you who will drive the interview let's see you who will decide how that 30 minutes or how that one hour is driven so if you know the solution and you're just saying it in the first two minutes it might be an issue so please drive the interview show that you can think right from the scratch you can build it sometimes you have to fake it but that is how the interviews go in DS algor rounds so in harder problems you have to follow this for easier problems do not follow it but in all the easier problems I'll also be following this pattern why so that you get used to this pattern and this gets into your blood so that when you get into an interview you actually are kind of always speaking group better optimal okay so coming to coming back to the problem finding the largest element in an array what does the problem mean obviously given an array of integers give me the largest integer in it so over here the largest integer is five so I want you to give me five how can you do this very simple if I have to ask you what is the Brute Force solution that comes to your mind it'll be like striver The Brute Force solution is I will be sorting it and if I sort it what will happen is it will be looking like one two two three five the moment I sorted the last element did I tell you what is the index of the last element I did so if the size over here is 5 the last will be array of n minus one can I say if I print this after sorting this will be my largest element obviously because once you have sorted it it is sorted in an ascending order so the smallest will be at first and the largest will be at last so if you sort it and you print it you will be getting the largest element now what will be the time complexity of this solution you know in order to sort if you apply more short quick shot anyone any one of them the time complexity will take n log n and the space complexity if you apply quick sort will be big go of 1 and I'm ignoring the recursive stack space but I'm still taking a Time complexity of n log n to sort it so this is why this is a Brute Force solution because this is the most like normal solution that comes to your hand this is why this is the Brute Force solution because this is the most like generic solution that will come to your head when you hear this problem so once you've given the Brew to the interview you can have a better solution or you might not so in this case we do not have a better solution so we'll move to the optimal solution now what is the most optimal solution for this one obviously we have to optimize and login so what we will do is we'll say okay let's let's keep a largest variable and I'll say largest to be the first element because I know one of the elements of the array will always be largest so I will say first element you are the largest assume you are the largest and then I start traversing I say okay three you can travel from three or you can travel from two as well that is okay I say three are you greater than the largest so largest is currently stored as three three are you get greater than three it says no so I see okay move ahead two are you greater than three he says no move one are you greater than three no this is move five are you greater than three yes so this will be five next two are you greater than five no so after this the iteration is over once the iteration is over the largest is storing the largest element and it's very simple if I have to code it it'll be like largest is a of 0 and then you start the for loop from I equal to 0 you go something like I n i plus plus and you say if array of I again I am writing the pseudo code can be written in any of the languages array of I that's it and at the end of the day you can say print array of sorry print largest is what you'll print simple as that now you can also run the loop from one because you have stored the largest of a of zero doesn't matter not a not a big optimization so what is the time complexity we're just running a loop for B go of n so can I say the time complexity over here is B go of n now this is much much better than the Brute Force solution this is why this will be categorized as an optimal solution because you kind of optimize the time complexity somewhere because big of n is definitely better than bigger of n log n so this is how you can easily solve this problem in case you want to submit this problem the problem link will be in the description so remember one thing we are talking about arrays but in a lot of places you might find something like a vector and in Java you might find arraylist or list so as long as it's a data structure which stores similar elements like vector is also a data structure which stores similar elements it is okay like it will be considered like it's not an array but the problems can be solved using arrays using list using vectors because it's a data structure which is storing similar integers so you might find something like a vector got it other the problem link is in the description so when you go to online compilers you don't have to print it usually they will be asking you to return it so you can easily go ahead and return it like this so going to the next problem it states second largest element in an array without sorting this question might look very very simple but this question is very very commonly asked in an interview because a lot of people do not know how to solve it so they might ask you a second largest or they might ask you a second smallest so the pattern that you have to answer in an interview is you start from root then you go to better then you go to Optimal that's how you will be solving it when I talk about brute and you have to find second largest element what will be the Brute Force The Brute Force is going to be very simple I will say hey I'll be sorting the array and if I sort the array it will look something like one two four five double seven and I know one thing for sure my largest element will be array of n minus 1 that is something which I'm very very sure about but can I say that the second largest element will be array of n minus two can I see this I cannot because the largest is seven and yeah there is another seven but that's not second largest that is largest the second largest is five so what you have to do is you have to start from the N minus 12th index and you have to kind of go like okay seven are you equivalent to largest because as of no larger system that is what you have stored because you've got this and you've stored it in largest now you go at seven and you say are you same as seven he says yes so definitely you are not second largest it then goes back five are you same as largest no so you are my second largest so you are my second largest that's how you can do it so it's it's more like you have to start from the back since I know that the largest is array of n minus one I can probably start from n minus 2 because that is the second last index and I can go like greater than equal to 0 I minus minus and what I can say is if array of I is not equal to largest can I say this will be my second largest second largest equal to array of I and then probably I can break out because there's no need to go any further can I say this will be my code so at first what did I do at first I did something like a sorting so sorting ended up taking a n logarithmic of n correct because sorting is sorting definitely takes that much of time and then these are the worst case what is the worst if I think properly if I give you an array something like this one seven seven seven seven then what will happen you will start from here no this is equivalent to logs this is also equivalent to largest this is also equivalent to largest this is also equivalent and this is also equivalent sorry this is not so you Traverse the entire right from then like n minus 2 until the beginning so this is the worst case can go for a big go of n there might be a case where your second largest might not exist might not exist in that case you can keep it as minus one might not like if this is seven there is no second largest element in that day but that is that might not happen you you should tell the interviewer by yourself these cases so I can say the total overall complexity of the brute force relation is first I sought and the worst case I might travel the entire way in order just in case all of them are largest elements so that's how you'll be telling the Brute Force approach so what will be a better solution a better solution will be like we will do a first is first pass and we'll find out the largest element if you remember we did find out the largest element before this problem so what I will do is I'll at first keep largest as one which is this guy then I'll start from two I will like two are you greater than one he says yes then I'll go to 4 or are you greater than 2 he says yes then I go to seven seven are you greater than four he says yes then I again go to seven seven are you greater than seven he says no Then I go to five five are you greater than seven no so the largest on the first pass is stored as seven and the code will be similar to the first one so you have figured out the largest over here by doing a first pass now what you will do is you will say okay let's keep second largest as minus one let's again try the same thing one a one are you greater than minus one he says yes and are you not largest he says yes so I'll take one and that will be my second largest okay let's go ahead he says two are you greater than one he says yes but are you not largest he says yes so thereby I take two then I go to 4 and I ask four are you greater than 2 he says yes but four you are not largest now he says no so four next seven seven are you greater than four yes but are you largest yes I am largest so do not take me do not take me so he'll not take him next the seven seven are you greater yes but I am largest five are you greater than four yes are you largest no so 5 comes up then the second pass you got the second largest as five so if I have to write the code can I say the code is very simple I start from zero I go until the end I plus plus and I say listen if array of I maybe you can store second largest as minus one just in case there is none and you can say second largest if it's greater and if array of I is not equal to largest then you can say second largest equal to array of I quite simple this will be a second pass first you write this this piece of code then you can write this piece of code and at the end of the day you can easily go ahead and print second largest if I have to ask you the time complexity of this now you can say that it's a big oven but you should not in an interview you should say okay the first pass takes B go of n the second pass takes we go of n so the algorithm is taking two passes and it's like n plus n that's actually running for two passes so it's a big O of to n approach so we have got a better approach of big go of 2N where we have to run twice through the array and we can get the largest in the first pass and we can get the second largest in the second pass now it's time to understand the optimal approach so in the optimal approach what you will do is you will say hey my largest will be the first cat which is array of 0 and my second largest will be nothing but minus one so I am saying okay the first guy is my largest version so I'm kind of take taking one as my largest and I'm saying second largest is minus one assuming that this array does not contains any negative numbers that is an assumption I'm working at in case the array contains negative numbers you can probably take this as integer minimum integer minimum in all the cases that I have told in case the array contains negative numbers you can take it as some very small number like integer minimum or a very very negative number got it so I've largest is assigned as one and second largest is assigned as minus one now what you do is you simply go ahead and say okay fine let's scroll this so we know the first guy we should not do anything why because that's the largest as of now so we will not do anything to it we'll go to the two we have two so two is like okay two are you greater than largest he says I am dude I am greater than largest for sure I'm like okay you're greater than largest so definitely you should be the largest but can I say if someone becomes the largest am your properly If someone becomes the largest in the previous largest will go second isn't it if you are in a class and you are always first and if someone comes up and says gets better marks than you then he will be the first guy and he will be the second right the same logic if 2 is greater than largest then what will happen is this will go to the second largest right because there is someone who is now the largest and we will replace the largest by two perfect now we go to four four says am I greater than largest he has C1 so now the largest goes to second largest goes to second largest and this one becomes four now I have seven seven says I'm the largest so this will take the largest and this will become the largest again seven nothing to do because we need to be very careful we have a 7 which is equivalent to largest so do not do anything if it's equivalent to largest do not do anything next we have five this is why you have to understand one thing we got five now this five is not greater than largest but we need to check is it greater than Second Law he says yes I am so just replace the second largest so apparently you got the largest as seven and the second largest as five very simple make sure do not do anything in terms of equivalent do not if it's lesser then only compare with second largest otherwise do not so let's now quote this up by the way you can find the problem Link in the description so over here what they're asking is you have to return the second largest and the second smallest so you have to find both of them so something like you have to find second largest right and then you have to find second smallest and then you have to return the array of this and in what order yeah first the largest and then the smallest this is what you have to do so maybe we can write a function which Finds Me second largest where I pass in the array and the n and similarly I can write a function which finds me the second smallest remember in your coding interviews all rounds you have to code using these kind of variable names you cannot give x y e b c you have to have proper variable namings you have to have proper function namings so that you stand out in an interview so let's quickly write the second largest second largest is taking the array and the N so what did I say at first what do you need to do you have to kind of say someone is the largest and maybe we can call it as a of 0 and we can say second largest and against the second largest as minus one now let's quickly see if they're stating anything about uh like okay they have clearly stated the array will be of minimum of length 2. so we are sure that every array will have two numbers that is something which we are sure about and the other thing if we read properly it states that it has unique unique non-negative integer so it's kind of saying that it doesn't have duplicates so if the array size is 2 and it doesn't have duplicates so every array will have a second largest element every array will have a second largest element got it so we can just go across from 1 till n and we can say Hey listen if a of I is greater than largest then the second largest guy well clearly yes there's no doubt in this will will take the largest guy and the largest will be replaced by array of I make sure you first take the largest and then replace the largest otherwise there will be a problem and then we can say Hey listen if a of I is greater than largest and an a of I because it has to be it has to be less of the largest by the way and AFI is greater than very important is greater than second largest in that case use the second largest can you please take care this is that's it and against the return second largest similarly let's write the second smallest as well the second smallest will again take the same vector and the n and you can say smallest equal to array of 0 and again the second smallest the name is kind of weird not an issue over here please make sure you give into max why into max the reason being you're finding smallest so it has to be a very big number as the array will be from zero so minus one will work for minimals like for largest it will work but for this you have to give into max because it's 10 to the power 9 had this been greater than you have to take a bigger number than this got it and now let's start with one and let's go till here that's something which we know and now we know one thing we need the smallest if a of I is smaller than the smallest then the second smallest takes the smallest quite obvious and and the smallest takes the array of I and what f array of I is not equal to small that means it's known but it is smaller than the second smallest I'm like okay if you're smaller than the second smallest then that's perfect the second smallest well just take array of I and once you have done this return smallest once you have done everything you can just go ahead and run it and it should be running absolutely fine thus and let's quickly submit this and see if it is submitted or not but the problem link is in the description make sure you try it out by the way what is the time complexity of this we go of n because you are just doing one pass or finding second largest it is B go of n the optimal solution to find second largest as just takes one pass and the time complexity is we go of n that is why it is better than the better solution and hence it's called the optimal solution so we are done with the second problem as well let's go on to the next problem which says check if the array is sorted so coming to the problem check if the array is sorted very simple problem given an array you have to see if it's sorted in a non-descending order what does it mean one okay two two is kind of greater than equal to 1. 2 is greater than equal to 2. 3 is greater than equal to 2 3 is greater than equal to 3 and 4 is greater than equal to so it's okay now let's check out the next array one okay two okay because greater than equal to 1. one not greater than equal to 2 not so this is not sorted this is sorted how will you do it very simple just travels in the array from the first element do we have a brute better optimal for this I don't think we need approved better optimal for this it's a very straightforward problem so what you'll do is you will start from the first index and you'll be like let's check with the previous is the previous smaller than equal to it is then you will go to the next and again you will check with the previous is it smaller than equal to then you'll go to the next then you'll go to the next and similarly you can check for everyone very obvious isn't it that's like if I have to write the pseudo code it'll go from one I'll go to Ln you don't need to check for the first element no need to check for the first element you say Hey listen if array of I is actually greater than equal to array of I minus 1 that should be the case for non-descending non-descending it's okay but if it is not then there is a problem they say return false stating that is not sorted and if the entire iteration is over if the entire iteration is over and I completes the entire iteration and reaches the step which means the end of the for Loop then you can say return true in the function stating this this array is sorted so if I try the same code in the online compiler by the way again the problem link will be in the description you can see you can simply write like this and we'll pick and leave the if as blank and again in the else just return the moment you find someone who has a problem that means that is not sorted just return a false if it completes the for Loop which is the step then you return a true this is how easy it is in order to write if an array is sorted or not what is the time complexity again takes a single pass so big O of n is the time complexity in order to check if the array is sorted let's move to the next problem which is the remove duplicates from a sorted array so coming to the problem remove duplicates in place from the sorted array what is the problem tell you about so you will be given an array which is definitely a sorted one and it will be containing integers if you see there are duplicates over here and you need to remove it so if I ask you what are the unique elements in this array a black one two and three that's what you have to write the first three pieces if there are three unique elements and you take up the first three bases and put those unique elements over there like one comma two comma three and the remaining places they do not care what you are putting they do not care you can put whatever you wish to you cannot put that as your choice but what they care is if there are three unique elements sorry if there are if there are three unique elements in the first three places should be filled up with those three unique elements once you fill up like once you modify the given array again you cannot create any news array you have to modify the given array itself once you have modified the given array you just tell them how many unique elements are there so you have to return so over here there are three so you have to return three modify and return the number of unique elements that is what the problem us is asking you to do so whenever this question now this question has been asked in a lot of interviews if this question comes up to you should you be saying the optimal approach directly the answer to that is no to write the interview and the first approach that you should always say is the Brute Force what is the brute force that comes in into your head it's like I need unique elements whenever I hear the term unique what comes into my head set kind of a set data structure and like yes so let's define a set data structure so I'll be defining a set data structure let's iterate in the array one put it into the set again one if you take this one and you put it into the set will the set accept one no it already has a one there will be no new addition in the set next go to two if you take this two and you put it into the set there will be a new addition perfect next go to two if you take this 20 put it into the set will there be a new addition no take this two no new edition take this three and put it into the set there will be a new addition take this three and put it into the set no new addition so at the end of the day the set after one iteration very very important after one iteration the set will be containing three elements so this is how the code will look like after one iteration like very simple declare a set and then pass on and insert everything so the set will be something like this after one iteration now what you will do is you will say okay I need to put everything into the like the unique elements in the starting of the array right let's go to the set let's keep a pointer here which is the zeroth index like if I have to write the index it's like 0 1 2 3 4 5 6. let's keep an index at the zeroth index and let's go to the first element of the set and that's one let's take that one and place it into the zeroth index done once I've done this let's move index one step ahead because my first place is occupied let's take the next element of the set and put it into the first once I've done that let's move it next three put it done that let's move does the set have any more elements no the set doesn't have any more elements if the set doesn't have any more elements what will happen obviously there'll be no further insertion into the array if there is no further insertion thereby you can say wherever the index stops because it's a zero based indexing array this will be the size of this particular array and you can return this particular index and this is what the brute force will be so if I have to write the code I'll quickly just show you the code the code is very simple declare index as zero this is how you iterate in the set just an iterator auto is something which is automatically assigning it to integer because the set is containing integers by the way the set stores everything in ascending order the first it will be storing one then two then three okay so I Twitter so every time you get one it gets into the index then index plus plus very simple code if I have to analyze the time complexity what will it be so the set in order to insert takes logarithmic of n the set okay so it'll be like n logarithmic of n for this particular first pass again this one is n so the overall time complexity for The Brute Force approach is n log n to insert into the set and a big O of N and what space are you using using a big O of n space Y in space imagine all of those very unique elements all of those were unique elements so the set would have taken everything into it that's why that's why the extra space is there there's an X cross space of bigo of n being used as well so this is the TC this is the space complexity so definitely this is a group for solution let's try to improve on it in order to optimize this Brute Force solution you have to apply something as a two pointer approach very simple and then you will get the optimal approach why did I say very simple let's think so the array is sorted right and we know one thing for sure first element is this and the next L like the first element will always be at its first place because that's unique in itself the next place will be taken by someone who is not equivalent to one because we are talking about unique right so the next element will be someone who will be not equivalent to this one so can I say I will go go and check which element is not equivalent to this first and I'll get this the moment I get this I'll just put it into the next index and then again I'll go and find who is the next who is not equivalent to this guy and then I'll put it into the next and then again I'll try but I'll not find so this is how you can easily enter everything got the thought process it's about you know one thing for sure this guy will always be at its first place so you don't need to change it you don't need to change it you just keep a pointer here stating I and now you co-write and say who's different than one that's it so you probably can keep a pointer G and you say one are you different than one and he says no so I'll go ahead I said J are you different than one he says yes yes I am so I says you can take the place in front of me so you will take the place here and since he has taken the place here the eye pointer will move here I'll just erase this so that you have better Clarity I pointer will move here now this is done so what you'll do is you'll move j and he'll say two are you equivalent he says yes not no use let's say again two no use three are equivalent no another unique if you get another unique where will it go in front of two so if it goes in front of two there's three will uh no need to Omit this three will come here perfect and if there's three comes here what will happen to I the I will also move from here to here now again you will find the next guy who is not equivalent to three that's equivalent and then over the iteration is over once the iteration is over do you notice the first three places are filled with the three unique elements and your eye is standing at which index if I write the indexing 0 1 2 standing at the second index so what will be the size of the unique like hotel with the number of the unique elements definitely I plus one quite simply so if I have to write the code how will the sudo code look like can I say I know one thing the first unique element is I equal to C and then I know I'll start from 1 and I'll go until n that's for sure and I need to figure out someone who is not equivalent to my current one if array of J is not equivalent to array of I take my take my front position take my front position so I'll be like okay let's give him the front position front position I plus one please take your front position once you have taken your front position what will you do okay let me go to that front position because now if I go to the front position if I go here then only I can now do the future I can get the next future element which is not equal got it so this is how it will work so I'll go to the front position done very simple two point once this for Loop is complete I know the size will be I plus 1 because I at the end of the day will be here which is 2 but the size will be one more so thereby we will be returning I plus one this is how the two pointer approach will look like and if I have to ask you the optimals time complexity simple one pass week often space complexity we got one why because one pass and you're doing everything in that particular array as it was being asked in the like if you remember the problem statement it's stated in place and that is being done this is the optimal solution for this problem just in case you want to submit the problem the problem link will be in the description and I've written the same code now let's quickly submit this and see if it is running fine or not yeah it does run so with this I can say that I've completed the fourth problem as well so for this video we will be keeping it till here because I don't want to solve a lot of problems and make the video long because that might scare you in the next uh video again we'll be solving probably the next five problems that is what we will be targeting in the next video so with this uh I will be wrapping up this video but if you have understood everything that I've taught in this particular video to follow out Edition do comment understood if you are new to our what are you waiting for please please consider subscribing to us because that is the only thing that keeps you motivated to make these kind of content and yeah hit that like button and if you haven't followed me on Instagram the idea is over here do follow me on Instagram LinkedIn and whatever social media links you'll find in the description with this I'll be wrapping up this video and explain some other videos [Music] don't ever forget your golden I will find the light