Transcription
Hey everyone, welcome back to the channel. I hope you guys are doing extremely well. So, this is another lecture from the Striver's A2Z DSA course. So, just in case you're here for the first time, this is the 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 Algo 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 arrays. 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 integers. So, the array can contain all of them as integers, or maybe as characters, or maybe as strings, or maybe as pairs. 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? 1, 2, 3, 4, 5, 6. So, the size of this array is six. In order to declare an array of size six, what you can do is you can write `int array[6]`. That will do. If you're following Java, it should be `int[] array = new int[6]`. This is how you can define in Java. Now, if you're defining an array of size six, whenever you define something like this, what happens is an array of some garbage values is defined. If you're defining it inside the `main` function, like if you're writing something like `int arr[6]`, 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 `int main`, if you decide that, "Hey, listen, I'm not going to declare it inside the `int main`, I will be declaring it before the `int main`." 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++, 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 six. 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 arr[10^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 `int main`. This is the maximum size. Imagine you say that, "Okay, listen, I'm 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^7 if you go ahead and declare it globally. Remember this.
Now, the next thing, how do you access an array? So, there is something known as index. So, in an array, the first index is zero, followed by one, then two, then three, then four. So, the last index is nothing but size minus one. And the first index is nothing but zero. So, the array indexing is from 0 to N-1. In order to access any of the elements of the array, what you can do is you can just loop from `i = 0` because 0 is the first index. You can go ahead till `n-1` because `n-1` is the last index and you can run the loop as `i++`. So, if you go ahead and do a print of `array[i]`, what will happen is this will one by one. First, the value of this will be `array[0]`. So, whatever you have stored at `array[0]`, imagine this is an array of integers and I'm storing like 2, 3, 1, 4, 7, 6. So, what will happen is first two will get printed, then three will get printed, then one, then four, then seven, six. This is how you can easily 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 six 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+1 memory address, the next at X+2, the next at X+3, the next at X+4, and the next at X+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.
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're 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 say drive the interview, imagine you have been asked a hard question and you know the optimized, like the most optimized solution in terms of time complexity and space complexity. Should you say it directly? Whenever you have given the question, no. You should drive 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 brute, better, more better, optimal. It's you who will drive the interview. It's you who will decide how that 30 minutes or how that 1 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 algorithms. 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 brute, better, optimal.
Okay, so 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? You'll be like, "Striver, the brute-force solution is I will be sorting it." And if I sort it, what will happen? It will be looking like 1, 2, 2, 3, 5. The moment I sorted, did I tell you what is the index of the last element? I did. So, if the size over here is five, the last will be `array[n-1]`. 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'll be getting the largest element. Now, what will be the time complexity of this solution? You know, in order to sort, if you apply merge sort, quick sort, anyone, any one of them, the time complexity will take N log N. And the space complexity, if you apply quick sort, will be O(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 brute to the interviewer, 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 N log N. So, what we will do is we will say, "Okay, let's keep a largest variable." And I'll say, `largest = arr[0]`. 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, are you greater than the largest?" Largest is currently stored as three. "Three, are you greater than three?" It says no. So, I say, "Okay, move ahead." "Two, are you greater than three?" He says no. "Move." "One, are you greater than three?" No. He says, "Move." "Five, are you greater than three?" Yes. 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 = arr[0]`. And then you start the for loop from `i = 0`. You go something like `i < n; i++`. And you say, "if `arr[i] > largest`". Again, I am writing the pseudo code. Can be written in any of the languages. `arr[i] > largest`? Then `largest = arr[i]`. That's it. And at the end of the day, you can say, "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 `arr[0]`. Doesn't matter. Not a big optimization. What is the time complexity? We're just running a loop for O(N). So, can I say the time complexity over here is O(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 O(N) is definitely better than O(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're 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, it 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 lists, using vectors, because it's a data structure which is storing similar integers. You might find something like a vector. Got it? But 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.
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 second largest, or they might ask you second smallest. So, the pattern that you have to answer in an interview is, you start from brute, 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 the 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 1, 2, 4, 5, 7. And I know one thing for sure, my largest element will be `arr[n-1]`. That is something which I'm very, very sure about. But can I say that the second largest element will be `arr[n-2]`? Can I say 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-2` index and you have to kind of go like, "Okay, seven, are you equivalent to largest?" Because as of now, largest is seven. 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're not second largest. He then goes back. "Five, are you same as largest?" No. So, you are my second largest. You are my second largest. That's how you can do it. So, it's more like you have to start from the back. Since I know that the largest is `arr[n-1]`, I can probably start from `n-2` because that is the second last index. And I can go like `i >= 0; i--`. And what I can say is, "if `arr[i] != largest`". Can I say this will be my second largest? `secondLargest = arr[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 O(N log N), correct? Because sorting is sorting, definitely takes that much of time. And then this, at the worst case, what is the worst case? If I think properly, if I give you an array something like this: 1, 7, 7, 7, 7, 7. Then what will happen? You will start from here. No, this is equivalent to largest. This is also equivalent to largest. This is also equivalent to largest. This is also equivalent to largest. This is also equivalent to largest. And this is also equivalent. Sorry, this is not. So, you traverse the entire array right from the end, like `n-2` until the beginning. So, this, at the worst case, can go for O(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 an array. But that is that might not happen. You should tell the interviewer by yourself these cases. So, I can say the overall complexity of the brute-force solution is, first I sort, 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 pass. Yes, 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 = 1` (which is this guy). Then I'll start from two. I'll be like, "Two, are you greater than one?" He says yes. Then I'll go to four. "Four, are you greater than two?" 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'll say, "Okay, let's keep `secondLargest = -1`." And let's again try the same thing. "One, hey, 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. "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 four. And I ask, "Four, are you greater than two?" 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, go seven. "Seven, are you greater?" Yes. "But I am largest." Five, "Are you greater than four?" Yes. "Are you largest?" No. So, five comes up. In 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++`. And I say, "Listen, if `arr[i] > secondLargest`". Maybe you can store `secondLargest = -1` just in case there is none. And you can say, "if `arr[i] > secondLargest` and `arr[i] != largest`". Then you can say `secondLargest = arr[i]`. Quite simple. This will be a second pass. First, you write 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 `secondLargest`. If I have to ask you the time complexity of this, now you can say that it's O(N). But you should not. In an interview, you should say, "Okay, the first pass takes O(N). The second pass takes O(N)." So, the algorithm is taking two passes. And it's like N + N. It's actually running for two passes. So, it's a O(2N) approach. So, we have got a better approach of O(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 guy, which is `arr[0]`. And my second largest will be nothing but minus one." So, I'm saying, "Okay, the first guy is my largest for sure." So, I'm kind of taking one as my largest. And I'm saying `secondLargest = -1`. Assuming that this array does not contain 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, have `largest = arr[0]` and `secondLargest = -1`. Now, what you do is, you simply go ahead and say, "Okay, fine, let's traverse." 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, "Hey, two, are you greater than largest?" He says, "I, 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, hear me out properly. If someone becomes the largest, then 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'll be the first guy and you'll be the second, right? The same logic. If two is greater than largest, 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?' Yes, you are. So, now the largest goes to second largest. It 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 seven 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? He says, "Yes, I am." 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 code 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. 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 or rounds, you have to code using these kind of variable namings. You cannot give X, Y, AB, BC. 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. `secondLargest` 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 as the largest. And maybe we can call it as `arr[0]`. And we can say `secondLargest`. And we can say `secondLargest = -1`. Now, let's quickly see if they're stating anything about, like, okay, they have clearly stated the array will be of minimum of length two. 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, non-negative integers. So, it's kind of saying that it doesn't have duplicates. So, if the array size is two 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 one till N. And we can say, "Hey, listen, if `arr[i] > largest`". Then the `secondLargest` guy will clearly, yes, there's no doubt in this. We'll take the largest guy. And the largest will be replaced by `arr[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 `arr[i] > largest` and `arr[i]` because it has to be, it has to be lesser than largest, by the way, and `arr[i] > secondLargest`". In that case, you, `secondLargest`, can you please take care of this? That's it. And you can return `secondLargest`.
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 = arr[0]`. And again, the `secondSmallest`. The name is kind of weird. Not an issue over here. Please make sure you give `INT_MAX`. Why `INT_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 minimums. Like for largest, it will work. But for this, you have to give `INT_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 `arr[i] < smallest`, then the `secondSmallest` takes the `smallest`. Quite obvious. And the `smallest` takes the `arr[i]`. And what if `arr[i]` is not equal to `smallest`? That means it's not. But it is smaller than the `secondSmallest`. I'm like, "Okay, if you're smaller than the `secondSmallest`, then that's perfect. The `secondSmallest` will just take `arr[i]`." And once I've done this, return `smallest`. Once you have done everything, you can just go ahead and run it. And it should be running absolutely fine. Does it? 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? O(N). Because you're just doing one pass for finding second largest. It is O(N). The optimal solution to find second largest has just takes one pass and the time complexity is O(N). That is why it is better than the better solution and hence it's called the optimal solution.
So, we're 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? 1, okay. 2, two is kind of greater than or equal to 1. 2 is greater than or equal to 2. 3 is greater than or equal to 2. 3 is greater than or equal to 3. And 4 is greater than or equal to 3. So, it's okay. Let's check out the next array. 1, okay. 2, okay, because greater than or equal to 1. 1, not greater than or equal to 2. Not. This is not sorted. This is sorted. How will you do it? Very simple. Just traverse in the array from the first element. Do we have a brute, better, optimal for this? I don't think we need a brute, better, optimal for this. It's a very straightforward problem. So, what you'll do is, you'll start from the first index and you'll be like, "Let's check with the previous." Is the previous smaller than or equal to it? If it is, then you'll go to the next. And again, you'll check with the previous. Is it smaller than or 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? So, it's like, if I have to write the pseudo code, it'll go from one. It'll go to N. You don't need to check for the first element. No need to check for the first element. You say, "Hey, listen, if `arr[i]` is actually greater than or equal to `arr[i-1]`". That should be the case. But non-descending, non-descending, it's okay. But if it is not, then there is a problem. You say, return false, stating that it 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 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 can leave the `if` as blank. And we can 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, O(N) is the time complexity in order to check if the array is sorted. Let's move to the next problem, which is "Remove Duplicates from a Sorted Array".
So, coming to the problem, "Remove Duplicates in place from the Sorted Array". What does the problem tell you about? So, you'll 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? It'll be like 1, 2, and 3. That's what you have to write in the first three places. If there are three unique elements, then you take up the first three places and put those unique elements over there, like 1, 2, 3. And the remaining places, they do not care what you're 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, then 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 new 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. Over here, there are three. So, you have to return three. Modify and return the number of unique elements. That is what the problem 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. Drive the interview. And the first approach that you should always say is the brute force. What is the brute force that comes 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. I'm 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. 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 two and you put it into the set, will there be a new addition? No. Take this two? No new addition. 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. 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." Fine. Let's go to the set. Let's keep a pointer here, which is the zero 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 index. Once I've done that, let's move it next. Three. Put it. Done. 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. Code is very simple. Declare `index = 0`. 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. First, it will be storing one, then two, then three. Okay, so iterator. Every time you get one, gets into the index, then `index++`. 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 will be like N log 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 O(N). And what space are you using? Using O(N) space. Why in space? Imagine all of those were 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 extra space of O(N) being used as well. So, this is the TC. This is the space complexity. So, definitely, this is a brute-force 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, the first element is this. And the next element, 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 and check which element is not equivalent to this, 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 go right and say, "Who's the guy who's different than one?" That's it. So, you probably can keep a pointer `j`. And you say, "One, are you different than one?" 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, he will take the place here. And since he has taken the place here, the `i` 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 you'll say, "Two, are you equivalent?" He says yes. H, not no use. You'll say, "Again, two, are you equivalent?" He says yes. Ah, no use. "Three, are you equivalent?" No. Another unique. If you get another unique, where will it go? In front of two. If it goes in front of two, this three will, no need to omit. This three will come here. Perfect. And if this three comes here, what will happen to `i`? The `i` will also move from here to here. Now, again, you'll 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 `i` 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, what will be the number of the unique elements? Definitely `i + 1`. Quite simple.
So, if I have to write the code, how will the pseudo code look like? Can I say I know one thing, the first unique element is `i = 0`. And then I know I'll start from one and I'll go until end. That's for sure. And I need to figure out someone who is not equivalent to my current one. If `arr[j]` is not equivalent to `arr[i]`. Take my, take my front position. Take my front position. So, I'll be like, "Okay, let's give him the front position." `i + 1`. 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, only then I can now do the future. I can get the next future element which is not equivalent. Got it? So, this is how it will work. So, I'll go to the front position. Done. Very simple two-pointer. Once this for loop is complete, I know the size will be `i + 1`. Because `i` at the end of the day will be here, which is two. But the size will be one more. Thereby, we will be returning `i + 1`. This is how the two-pointer approach will look like. And if I have to ask you the optimal time complexity? Simple, one pass. O(N). Space complexity, O(1). 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 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 have 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 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, I will be wrapping up this video. But if you have understood everything that I've taught in this particular video, to follow our tradition, do comment "Understood". If you are new to our channel, what are you waiting for? Please, 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, and yeah, if you haven't followed me on Instagram, the ID 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. Let's be in some other video. Till then, bye-bye, take care. And forget your golden rule. I will.