Binary Search Interview Questions | Search Insert Position | First and Last Position of Element

Hey everyone, I hope you all are safe and doing good. So now you are aware about linear search, binary search, and lower bound and upper bound concept. How to implement lower bound upper bound with the binary search. Got it? Now in this lecture we'll see some questions, lead code questions. And these questions has been asked in those top tech companies even, fine companies, Amazon, Facebook, Netflix, and these companies. Right? Okay, now very first question. The prerequisite for this lecture is you you you should have knowledge of binary search and lower bound upper bound. So if you haven't watched those lecture, please go through those lecture first, the previous lecture, then come to this. When once you go to Google and you just search lead code questions on arrays and you just click on the first link, lead code, and you when you once you click on that link leetcode.com, there would be problems related to arrays. Now we will see we are not going to you know, in that much like hard problem right now. We'll see basic one. But see, go for this one. Search insert position, lead code 35. If you click here, you will be redirected to this page. So there is a problem, search insert position. What is the problem? First read out this carefully. So the problem given is see given a sorted array of distinct integers. Distinct integers. Integers are not duplicate in this case. Now what you need to do? And a target value. Return the index if the target is found. Return the index if the target is found. If not, return the index where it would be if it were inserted in order. And see the condition is you must write an algorithm with log n run time complexity. So we know binary search is log n. But first we'll see brute force because if you don't know the optimized approach, then and in interview also if you go through this thing first you can tell the brute force approach, then how you can optimize that thing. So the interviewer will come to know that okay, you know everything. It's not like that you have just like um cram these things and all. You know the logic. Okay? So first go through the brute force approach, then optimize that, go for better approach, optimal approach, and tell the time complexity and all. So this will really help you in interview. So first, let's see. Now what is the question? See example, if input is array is 1 3 5 6 and target given is 5. So if if see, return the index if the target is found. So here we have the target 5, so return the index. Index of this is 0 1 2. 2. 1 3 5 6, target is 2. But here there is no 2. Means where you can insert this 2? Without disturbing the order because this is sorted array. It's not unsorted array that you can insert at end or front or specific position or no. You have to find out that particular position. So where we can insert if the array is this 1 3 and 5 and 6? So where you can insert this? Uh target is 2. So obviously this is 1. After 1, see the element is 3. So it is greater than 2. So definitely I can say that 2 would be somewhere here. After 1 before 3, something like this. So index is 0 1 2 3. So I cannot say some between 0 and 1 there is is there any other index like 0.5 or something like this? No. So where you can insert? Obviously after 1, so at this index. So we can insert 2 here. 3 would be here, 5 would be here, and 6 would be here. This would be the array. Right? If suppose in the same array target is 7. See 1 3 5 and 6. So same array is given and now at this time 1 3 5 and 6. Target is 7. So first brute force approach is simply we start searching from here. See, this is 1. Okay, it's less than 7. Move next. 3 less than 7. 5 less than 7. 6 less than 7. Now end of the array. So definitely it is greater than everything, so here you can insert. So whatever the array of length, that would be returned in this case. The index would be that. Right? So how to write down? Just think the logic. One by one you go through this. If here suppose we were we were supposed to insert 2. Insert position you have to find out. So 2, what is the position? It's 0 1 2 3. Index would be 1 because here only we can insert 2. Yes or no? If suppose you want to insert 4. The target is 4. 1 2 it is 5, so somewhere here we can insert 4. But there is no 1.5 kind of index. So after 3 we can insert here. Here we can insert 4. 5 would be here and 6 would be here, 7 would be here. If 7 is there, 7 would be here. So index would be 2. So can you just um frame a pattern or the logic? We are searching, we are starting from here. Once you find the index, uh sorry, the element which is greater than the target element. Here the target element target was 2. 3 is greater than the first element which is greater than 2, the first element. Or you can say the smallest index. Where the smallest index where the element this element of the array is greater than greater than the target target is like whatever the target. Yes? Or here here it is given there are distinct integer means there is no duplicates. But suppose suppose there are duplicates. The array is something like this, 1 3 3 5 6 7. Right? I want to insert again 3. This is the case. What will happen? There are duplicates. Or even in this case also you can take this. I want to insert 3. Where you can insert this 3? Obviously at one at this index, no. Then index one. It's 3. So I can insert 3 here, yes? Yes or no? Because this is equal to 3. So I can insert this 3 here, this would be here, this would be here, and something like this. So index would be 1. If in this case I want to insert 5. This is the array. Okay? Let me just clean this and uh 1 1 3 and 5 6. This is the array suppose and I want to insert 5. Now duplicates are allowed. Okay? So you have to find out the position where you can insert. So same position. 1 Okay, check this element is less than 5. Right? Now go for the next element. 3 go for the next element. Yes, it's 5. So it is equal to 5. Here we can insert. We can If you go for here, 6. Maybe you say that here also ma'am we can insert 5 and there would be 6. Okay, that's also fine. But why to go further? Why to go for more competition? Because just find out because obviously here also we can insert and here also we can insert. But in terms of like the time execution time if you insert here, I'll not compare the next one, so definitely it will take little bit less time, little bit you can say. But it would be yeah, definitely better. That's why I'm saying that the smallest index where the element is you have to find out the smallest index where element array of element is Now we can say either greater than or equal to target. Now this 5 is equal to 5. Yes, I can insert this 5 here, this 5 would be here, and this 6 would be here. So you have to find out you can say the smallest index where where this element of the array this arr of i greater than equal to the target. That's it. Yes? And this is nothing but we have discussed this is lower bound. Lower bound concept. In lower bound also we got we we find out what? The smallest index where the array element is greater than or equal to the target element. That is lower bound. But suppose if you don't want to apply lower bound, simply with linear search also we can do this thing. How you can do? Let's write down. Now loop in linear search. We start searching from here. We don't go for binary search at all. So I would be 0 and I is less than whatever the array.length. And then I++. Yes? Now where to stop? You have to if check if array of i is greater than the target element. Target is whatever the target element, target element. Either greater than or equal to. Then simply return i. Simple. Yes? That is the insert position. Where you can insert this. Here you can same thing. If I want to insert here again 3 so where you can insert? Obviously in this place. So search this is this element greater than or equal to target element? No. Is this element greater than equal to target target element? Yes. So, here I can insert. Just return this I. Simple. If I want to insert 13 here, so there would be no like here this element check this and here we have suppose seven. Check this is it greater than equal to target element? No. So, end of the array. Now, we return what? Whatever the array length. Here 1 2 3 4 5. So, array length is five. So, here I can insert at fifth index. So, at last at last after this you can simply return whatever the array.length. Just to handle that case. array. length. If this condition satisfied, okay, return the index. Otherwise, if this condition not satisfied, if that element is not there and it is you can say the greatest of all the element, greatest of all the element because 13 is largest element here. So, simply we know that 13 we can insert here itself. So, simply return array.length. Yes. If I want to insert here same, you can say just check two. Or you can say here I want to insert four. So, four I I can say that definitely I can say four would be here. So, check is this one greater than equal to target? No. Next, is this greater than equal to target? No. Is this greater than equal to target? Yes. So, as soon as you find the first element which is greater than or equal to the target, just return that index. We know that this is my insert position. So, here insert this I. So, 0 1 2. It will return simply two. So, definitely here you can insert four. Five would be here, six would be here and something like this. Okay, but we just have to find out the insert position. That's it. So, this is the linear approach. But, the thing is they want you must write an algorithm with log n run time complexity and this will take because the loop is running from zero till length of the array. Okay. So, basically you have to check the loops and number of comparisons. Number of comparisons means basically how many times comparison we do the this comparison. Or you can say this condition is being you can say executed. If array length array is five, so we check this loop will run till five. If array is of 10 elements in worst case, in worst case I'm talking. Okay. In worst worst cases, I want to insert here 13. So, definitely I have to check all the elements and at last I can insert. So, you have to go through traverse all the elements. So, it depends on the size of the array. So, basically the loop will run n times. It depends on the array length. Okay. Simple if statement is not it's not like that this loop is will run for n times and this will also run n times. No, and it's n square. This comparison would be done. It depends on the this only. Simple if statement is going to take constant time complexity. Okay. It's simple if statement within the for loop. So, now you have to check how many times these statements has been executed. Obviously n number of times. So, linear in this case order of n. But, now you have to cut cut down this. Now, better approach is go for binary search, find lower bound. Simple. And that thing we have seen. How to find lower bound? Okay. You can go through that lecture. Just copy paste that lower bound code and you will get the insert position. Because lower bound is nothing but same. Lower bound is what? The smallest index where where the this array of I is equal to greater than equal to whatever the target. And this is exactly my search insert position. You got it? So, see this lead this is the lead code question. But, if you are aware about the concepts binary search, lower bound, upper bound, these concepts will really help you to solve many lead code questions. Now, let's code this. So, in our project this data structure and algorithm, let's uh create a new Java class search insert position. Right? And let's take an array here. So, let's take an array. So, we just have a method insert position and we're passing array and whatever the target is. Right? So, let's here define this method. It will return the index. So, return type is integer insert position and we're passing your array. So, arr and whatever the target. Suppose x I'm taking here. Go for linear search at first, suppose. So, simply this is the naive approach. If you are not you have just a beginner, so simply at the brute force approach what anyone can think is this one. Right? So, this is the simplest one. Loop will run till zero till the end of the array and if whatever the array element if greater than equal to whatever the x, your target. Simply return that index. That's it. Otherwise, if this condition not satisfied, in that case, after completing this for loop, you simply return here whatever the array.length. Simple. So, if I'm returning this here, so let's just store this into a variable, suppose position is equal to this. And we can just simply print this position. That's it. Let's run this. And for two, what it will give? Let's run this. It should give zero and one because at one first index we can insert two after one. So, see the position is one itself. Now, again if I go for suppose zero, where I can insert zero? Before one. So, it's like like at zeroth position. So, position is zero. If I search for three, see. I can insert here at one. Because here itself I can insert. Or we can say that if element exists, then also it will return the you can say what according to that uh definition, return the index if target is found. So, if target is found, here we got the target, so it will return that index only. Or if you want to insert then the same position is there. Here also you can insert this three. If suppose one more three I have, let's run this. It will again give you the same like three only. Although the question is saying array of distinct integer. So, this is not according to the question. We have taken duplicated value. So, let's remove this. Now, if I want to insert 13 or 31, so definitely it is the largest among all the all the array elements, so at last we can insert. That is four fourth index. 0 1 2 3 fourth index. You got it? Or if suppose the target is six, then what it will give? If the target is six, then 0 1 2 3. Here I can insert the six. So, position is three. But, yeah, we know that it's taking the linear time, so uh you have to solve this in log n. If you want to submit this this you can say code there, so let's submit. Let's just copy paste this. I didn't search position this thing and paste here. So, sorry. It's the see the array name is here the nums. So, please you have to do the required changes nums. Target is it's not x. Here the name is target. So, it should return nums.length. I'm I'm going for linear search. But, obviously you must write an algorithm with log n. So, let's see what happen. If I run this, then hopefully it will run. Compilation error and reached out of file while parsing. Okay, we have just removed this parenthesis there. So, run this. Now, see. >> [clears throat] >> Now, it will run. Oh, got it. This is not arr. This is the array name is nums. Sorry, you have to change everything here. Here the array name is nums. So, now run this. Now, see. Accepted all the cases. If you submit, okay, it is fine. But, if you submit, then the algorithm is taking order of n time complexity. Right? And we have to write in order of Sorry, that is in log n. Okay. So, now you have to change it. If you analyze the complexity, then this the time complexity is order of n. It's a linear line. Right? Here here there you will get analyze complexity and you can analyze that. Now, I'm I'm going to change my solution. So, simple you can go for that lower bound. I have done that thing also. We have done. This is the lower bound approach. We have done how to find out lower bound. Okay. So, just copy paste this thing. And first let's just try to comment out this and we now take one more method. The same static insert position I want to find out. And here I just want to the that approach, lower bound approach. So, I'm just going to copy paste this code. Whatever the lower bound code. This thing we have already discussed. So, just copy paste this. Right? Return low or if you are not comfortable of returning low if you're not getting I've told you you can simply take an answer at first the position. What is the position? Suppose I'm taking here just delete this if and here I'm taking int pos is equal to at first whatever the array.length. Hypothetical value at last. Because if it's greatest of all the elements and definitely we can set at the last itself. Low greater than equal to high, find out mid. I hope you know the simple concept of binary search, find out mid. If array of mid is greater than or equal to x See, it's greater than or equal to x. Then means we can say this may be our answer. So, our position, let's update the position is equal to whatever the mid. Because this is either greater than or equal to. Right? So, if it's equal to x then you can just one one thing we can do we can just if it's equal to x then we can return the index according to the question. Right? But here still we cannot return whatever the mid is. Because if it's equal to x and array are of having some duplicate value then we cannot return. But if we know that arrays are of distinct values then we can definitely return that thing. So, here rather than this we can just return. So, here if I want to go search for three suppose. So, as soon as it find three it should return. Okay. So, we can write down one more if here. If this array are of mid is equal to is equal to whatever the x value then simply return mid. That's it. This is the situation when array is having distinct integer, distinct. No duplicate, no duplicate elements are there. Else, now in else part else if array of mid is greater than x greater than x then we can say that x would be definitely in the left side, left portion. Right? So, if it's greater than x then I can say that it may be my answer. Okay, because it's greater than x. It may be my answer but I'm not sure because I have to find out the smallest index where our mid or the element is greater than x. Then high would be mid minus one else low would be this and at last we can simply return whatever the position is. That's it. Right? Here. So, for same for three if I run this it will give you the target is three. Sorry, it's one. Because see one. Here itself I can insert or three is already there so it will return simply this thing. And if I want to insert here suppose four then it will give me 1 3 after this 0 1 2 2. Yes? If I insert here 41 then it will give me obviously 1 2 3 4. Array length, it's four. So, it's running. Right? Now, if you copy paste this code there at so, you just copy paste this thing in my lead code. So, here rather than writing this just remove this and copy paste this. But here you have to change array length so, just change here if you have nums. So, I have changed everything. Let's see. Let's run this and see if it's working or not. Okay, we have just the one thing that's here. We have just removed one this curly bracket so, you have to insert one curly bracket as well. For the class let's check. Okay. Passed with all the cases and now if I submit this now if I submit this then Okay, fine. But here one more case uh maybe they can say there there we are not having integer we can say there we are not having distinct elements. Suppose I'm having here something like this. The array is this. And the target is again three. Target is equal to three. So, if you go for this lower bound and if you run this right now if I run this so, we are we are finding out the insert position so, it is giving me four. Why four? Because I can insert three here itself after one. I mean zero at one index only. Why I would compare next next next till four? Uh till fourth that's useless kind of thing. So, in this case if array is having duplicate elements array sorted then obviously we cannot say that if array of mid is equal to x return mid. No. Yeah, in this case see it's mid is 0 1 2 3 4 5 6 7 8 9. So, suppose array is something like this and our target element is again I want to insert three. So, where is the position? Obviously here itself. Index is I can say that index here is it's 0 then 1 then 2 then 3 then 4 5 6 7. Index is this. Right? Now I want to insert three. So, in the previous case it was giving me the output is four because here I can say that low and high we are going for binary search to find out that lower bound. So, low is zero high is equal to I can say that is seven. So, 0 + 7 / 2 it becomes three. So, here we have our mid. So, definitely it's three. It's equal to mid so, it will return the index that is in this case it's four it's three. In the previous case in our program we are having one more three. I've just taken one less three here. There are 1 2 3 4 5. Five elements are which are three but there we are having almost seven elements see which are three. Okay. So but I don't want to insert obviously three here. At third index I can insert here itself three. At one index. Okay. So, now what we can do is Okay, it is equal to three but maybe we want smallest index. So, smallest index would be to the left hand side. It may be our answer. Answer at first answer was eight. The length of the Now answer is updated to three. Maybe our answer but I want smallest index. So, there may be three here or three here or something like this. So, let's do go to the left part as well. So, now we will go to the left part. We will not simply return mid. Yeah, it may be our answer but it's not the answer. I cannot say. So, go to the left part so, high becomes it's two. So, now 0 + 2 becomes divided by 2 is it's one. So, now mid is here. It is again three. So, it may be my answer. So, update again this to index is now for this index is one. So, it may be my answer but I cannot sure. I want the smallest index. Smallest index would be in the left hand side. So, zero again it would be zero. So, 0 + 0 / 2 it's zero. Yes? So, low mid and high both are here. Now see, this element is this greater than or equal to our target element? No. It's less than. It's less than so, it is greater than. So, I can found three to the right hand side. So, move to the right hand side. So, if you move to the right hand side then low becomes mid plus one. Mid plus one is one. High is zero. This is termination condition. Because now low is high low is more than high. So, there is no search space. It will return simply one. And that's exactly the answer. Right? So, you can change it a little bit in this case. This is the case. I cannot simply return it this case. Just remove this. If it's greater than equal to both are in the same thing. Position maybe equal to this but I'm not sure. We can go for high is equal to mid minus one. We want smallest index so, high is equal to this. Now, if you run this then for three it will give target uh sorry, the index is one. See, it's one. Right? Okay, so whatever question is given to you according to that you have to you can say frame your um this uh approach. The approach is same. You have to change a little bit. We know binary search if sorted array then you have to apply binary search that is for sure. Search insert position so, if you get lower bound then you can get the insert position. The difference is what you are given. Distinct elements are there or what they want. According to that you have to answer. You have to write your code. Right? And for this we know it's log n time complexity would be log n for binary search because we are going for binary search in this case. Okay, one more question is this. Find first and last position of an element in a array sorted array and this question is an interview question. Has been asked in many top tech companies even in Meta. See the level of question they ask. So, you don't get afraid of the name Fang or Mang. No, they ask these questions itself. If you know the concept, if you know the approach, you can easily easily solve the questions. Maybe some questions are tough, but not all the questions. So, this is the Facebook level question. Find first and last position of element in sorted array. Sorted array? Apply binary search. Given an array of integers nums sorted in non-decreasing order means ascending order, find the starting and ending position of a given target value. If target is not found in the array, just return minus one minus one. When the array returning minus one, first occurrence is minus one, last occurrence is also minus one because element is not there. You must write an algorithm with log n complexity. We know binary search is taking log n. So, it's not that much tough. You can easily write. Now see the input. Nums nums the array is this. Right? And they are not saying that the array is having distinct integer. It's non-decreasing ascending order but it can have duplicate values. Right? So, this is the array target is eight. First occurrence of eight. We know. This is first occurrence, this is last occurrence. So, index is it's 0 1 2 3 4. Three and four it will give. Yes? This is the array target is six. We know that there is no six here. So, just return minus one minus one. In this case nums it's nothing. Target is zero. So, if array is empty then obviously it will return minus one minus one. Right? How to solve this question? Let's see. So, this is my array and the target is eight. You have to find out first occurrence and last occurrence. Right? Okay, first we are not aware about like we are beginner and I'm not aware about lower bound or binary search and all. So, what is the brute force approach? What is that naive approach? First comes in your mind. How to find out first occurrence of a letter? So, very simple. Start searching from this. Is this eight? No. Is this eight? No. Is this eight? No. Is this eight? Yes. So, at first what we can do is for first occurrence I can say at first the first occurrence is minus one and last is also minus one. Because if element is not there then we have to return minus one minus one. So, let's say both are minus one minus one. Now I got eight here. Equal to eight? Yes. Okay. Now we have to change this first and last. So, check. First occurrence is first this element minus one? If it is minus one change it. So, now change it to here 0 1 2 3 4 5. With three. It's three, last is also three. Change both. Both are minus one, change. Right now. Next element. It's again eight. Yes? So, can we change both first and last? No. First occurrence would be this only. Last occurrence is whatever the last occurrence like this. So, you change you check. Is first minus one? Then only change. Now in this case is first minus one? No, it's three. So, we'll not change it. But we will change last every time. Because obviously last will be maybe like right now four then maybe five here also again we have eight. So, last you have to change. Now last change, it becomes four. The index is four. Go for next element. Is this eight? No. So, we are this like the end of the array is this. Right? So, now return first and last three and four. This is the answer three and four. If suppose the target is in this case only target is 10. Yes, at first same. Let's take first and last minus one minus one. Check. Start with first five. Is it target? No. Is it? No. Is it 10? No. Is it 10? No. Is it 10? No. Is it 10? Yes. Once you get the element is equal to the target element check. First is first minus one? Yes. Change it. Now it becomes whatever the index five. Last we always change. Change it. It's five. Now is the next element? No. So, terminate the loop and it will return five and five. First is also five and last occurrence is also five because only one element we have. Suppose I want to search for 12. At first last is minus one, first is minus one. Check from this. Is this 12? No. Is this? No. No. No. No. No. And end of the array. So, loop would be terminated and first and last are still minus one minus one. Just return first and last minus one minus one. That's it. So, this is simple approach. You can say linear search you are applying. Brute force approach. But obviously we are going from first element to last element in the worst case so it will take order of n. That is not a good time complexity. Linear. Can we solve it with less than order of n? Yes, we can. But for for now let's write down how to go for how to write down this thing. So, see. We simply write at first we are having what? So, at first we can have simply rather than taking like two variables first and last. What we can have? We can have an array because we have to return it in form of like array, no? Three four minus one minus one. So, it's an array having two elements. It's not a single variable. So, we can have an array suppose result is equal to at first minus one minus one. Simple. This is my array result. Now the loop would be zero till this is pseudo code. I'm not writing the exact code here. Right? Less than whatever the length of the array and I plus plus because we are following from zero till the end of the array. Now check if if array of I is equal to is equal to whatever the target, whatever the target element. If this is true then we check if again this this this is obviously first and last. So, how to access this element? We know this is array. So, array of zeroth index, array of first index. So, if result of zero is equal to is equal to minus one is minus one then change it. Now it becomes result of zero becomes whatever the I value is. Simple. And last we change every time. So, after after this if this is the case, after this we change the last. So, result of one is equal to I. It's one. Is equal to I. So, every time every time we change this and I guess that's it. This is the simple logic. So, like if we are having this array so at first zero array length is we are having 1 2 3 4 5 6. Array length is six. Condition true. Enter here. ARR of zero. ARR of zero is five. It's five. Is five equal to equal to target? Because target in this case is eight. Target is eight. Is eight equal to five? No, this condition is not true. Right? So, if this is not true we are not going to enter into this part. We are not going to change anything here. Okay? So, this is like maybe closing of this if. This. So, we'll not enter there. Now I plus plus. Now I becomes one. I is one. One less than six? Yes. Again enter here. Is this equal to target? No. So, we'll not enter here. Again I plus plus. Now I becomes two. Is this equal to this? No. Now again three. Yes. Now when once I is three this condition true. ARR of three. So, here we have 0 1 2 3 4 and 5. So, ARR of three is eight. Yes. Now this condition is true. ARR of three is equal to target that is eight is equal to eight. Now if this condition true again enter here. Now see. Result of zero. So, result of zero. How to access this? Obviously zero and one. Is this minus one? Yes, it's minus one. So, result of zero is equal to I. I right now is three. So, update it with three. And irrespective of this because we are not writing this in else part. So, after this if directly control will go to the next statement whatever is written after this if block. This is not in else part. Take care of this thing. Don't write this in else part. Like if this is true then then only go here, else go here. No. This last we will update every time. Once you go once you find out this. As soon as you find out this you have to update the last because we want to find out the last occurrence. So, keep moving. Keep updating this last till you get the last occurrence. So, this becomes also I. So, it becomes three. Three and three now. Now I plus plus. I I becomes now four. Is this condition true? Yes. Enter here. ARR of four. Is this true? Yes, it's again eight. So, this condition also true. Control will enter here. Now if this condition true, result of zero equal to one, result of zero is not minus one. It's three. So, control will not enter here. We will not update this. Control will go out of this if whatever is written. We are We have written this statement. Result of one, result of one is this is equal to I. I is now four, so update this to four. First index would be as it is. I plus plus. Now, I becomes five. Five less than six, yes, enter here. ARR of five, it's 10. Is this condition true? No. We will not enter here. I plus plus. I becomes now six. Is this condition true? No, out of the for loop. Just return this three and four, and we know the answer is three and four. But this we know that taking order of n complexity. Linear in worst case. It's not great. You have to find out You must have to write down algo with log n time complexity, logarithmic. Okay, so we know if array is sorted, sorted array is given. Second thing you have to find something. Find means you have to search something. Searching in a sorted array, apply binary search. Time complexity would be log n, simple. Okay, but now Okay, apply you have to apply binary search in this case. This is the brute force approach. Now, go for the optimal approach, better approach. Simple apply apply binary search. Still we are not aware about maybe lower bound, upper bound. We know only binary search. Okay, so this is first approach. Second, let's solve this with binary search. Okay. Now, we have this array. You know the concept of binary search, simple. Low zero, high is five. Zero plus five by two, it's two. Mid is here. Now, we can't in simple one binary search, we cannot find out both first and last occurrence like in the previous case. So, first you find first occurrence, then again apply binary search, and we go for last occurrence. Two thing Two time you have to call binary search. Okay, so first let's find out first occurrence of target is eight. First occurrence of eight, let's find out. Right? Now, binary search. This is the case. Now, mid is Now, mid is like two. So, is this seven, mid element? Check. Is this seven Because this is seven, this is eight. So, mid element is we know less than less than our target element. So, we can for sure we can say that we will find our target element in the right half because array is sorted. That is for sure. So, we just cut down this thing. You have to move. The array is now this. So, move to the right half. So, this low becomes this. Now, low would be mid plus one, that is three, five, and mid is again same approach. It's four. Mid is here now, four. Check for this. Now, eight is equal to eight. Okay, fine. Eight is equal to eight, so we get one occurrence. So, we can say that it may be our answer. Maybe. We are finding first occurrence only. So, at first let let's assume first is equal to minus one because if you don't find anything, you have to return minus one minus one. Don't assume first is equal to array length. And return array length. No, here you have to return minus one. So, please uh you can say uh understand or read the question carefully what you have to return, minus one minus one. If element is not there. So, at first let's assume first is minus one. Now, this mid is equal to eight. So, this may be my first occurrence. Maybe. I'm not sure that it is my first occurrence because maybe to the left hand side we can have more eight because array is having duplicate data. Array is not having distinct integer. We can have more eight here. So, it may be my answer. Maybe my answer. So, I can just update it to four. But now, I I'm sure that at index four now I get eight. If I want to find out first occurrence of this, so definitely the first occurrence I can get to the left hand side only if there are more eight exist. So, the first occurrence is definitely to the left hand side. So, that is like the smaller index, obviously. So, now move to the left hand side, left array. So, just remove this, and search space is to the left side only. So, if you move move to the left hand side, then high would be mid minus one. Low would be as it is, high would be four minus one, that is three. So, three plus three divided by two, that is three itself. So, we are having this search space. High is also here, low is here, and mid is also here. Now, check. This This is again equal to eight. Yes? So, if it's equal to eight, so it may be my answer because we are definitely If you're moving to the left hand side, so this is definitely the smaller index. And that exactly you want. The for first occurrence, the smaller index smallest index where first time this element you know, occur in that array. So, we just update this with three. This may be my answer. Maybe I can have more eight to the left hand side. I want first occurrence. So, again move to the left hand side. So, now low would be as it is, high would become three minus one, that is two. Now, stop. You have to run till the termination of the loop. Now, see. Here low is greater than high, so we are we don't have any search space now. Because the condition is while low less than equal to high, till then you have to search because answer exists always between low and high. Once low becomes greater than high, there is no search space. So, now at last, what is the first value, three? Return this. That is my first occurrence of eight. And that's exactly we have. Yes? So, this is how we can apply binary search, simple binary search, and uh go for this. Now, if you want to find out last occurrence, in that case, what we will do? Okay, let's see. I hope this is clear to you. Same thing. We are going for obviously binary search here. But right now, last occurrence. Low and high, and mid is divided by two, so it's two. Right now is this, seven. So, in first occurrence, if I want to write down that it's like the smallest index where the element is greater than or equal to the target element. That is the first occurrence. Can I say something like this? But there are some cases. It's like exactly lower bound, but there are some edge cases. That also we'll see. Okay, but right now we are just going for no lower bound, upper bound. Just forget that thing. We are just applying binary search here. Now, if If suppose if the target in this case is seven, suppose same. First occurrence I want to find out, not last, still seven. Seven is my target. So, first is at first minus one. Yes? Go for two. Mid is now two. [clears throat] At two, we are having seven. Yes? I can say that yeah, this may be my first occurrence. So, let's let's update this to index two. Right? But first occurrence is definitely in the left hand side. So, maybe there can be more seven to the left hand side. Because I want Maybe seven are here itself, but for first occurrence, you have to move to the left hand side. That is common sense. So, just the becomes high becomes now mid minus one, that is one and zero. So, search space is right now this only. We have eliminated this thing. Zero and one. So, zero plus one divided by two, it's zero. So, mid is here. Five. Five is what? Less than our target element. Target element is The target element is right now seven. Five is less than target element. Right? So, we will not update that. So, we can say that seven Our target element is seven, so we can say that surely seven would would be to the right hand side of this. We can say this? Yes? So, move to the right hand side. To move right hand side, low would be obviously mid plus one. So, it becomes one. High is as it is, one. One plus one divided by two, it's two by two, it's one. So, everything is pointing to this one. Search space is only we are having one element. Right? Now, check. Seven. Yes, equal to seven. It's target element. So, we can say that yes, it may be my answer because definitely if you are moving to the left hand side, that is like the smallest index. So, we just update this. Index is now one. First is now one. It may be my answer because loop is still running, but I cannot surely say that it is my answer. Right? It is equal to seven. Now, to find first occurrence, we can say that first occurrence of the smallest index would be definitely to the left hand side. So, now move left side. Remove the right part. If you move to the left half, then high would be mid minus one. Now, high becomes one minus one, that is zero. Low is one. But now, condition is not true because now low is greater than high, so terminate the loop, and at last, first is one. So, it is my first occurrence. That's it. Yes? Suppose target is 11. Target is 11 or target is suppose six. Not 11. My target is right now six. Right? So now, my target is six in this case. But six is obviously not there, so first occurrence, last occurrence will be -1 -1. Okay. But right now we are finding only first occurrence with binary search. Same. Low plus high is equal to mid, that is two, so mid is now two. Check seven. Seven is the element is greater than the target element. Yes, it's greater than. So we can surely say that if it is greater than or equal to a target element, we can surely say that first occurrence would be definitely to definitely to the left side. Right? So it's seven, it's six, so six always exist, we know it, left hand side. So high becomes now 2 - 1, that is one. It's zero. Now search space is this. Right? 0 + 1 / 2, that is zero itself. Mid is here. Check for five. At mid now we have five. Five five is less than six. It's not greater. Five is less than a target element. If it is less than, so we can say that the target element definitely exist to the right hand side. Yes, because it's already direct. So now to go for right hand side, we just move our low. So low becomes mid plus one. 1 + 1, 0 + 1, that is one. It is one. 1 + 1, that is it's one. Now one one one. Low, high and mid is pointing to this. This is only my search space seven. Now compare the seven with six. Now our target this mid element is greater than six. Yes, if it is greater than the target element, so I can say that six is definitely to the left part. So again, divided by two. If you want to move to the left side, search left side, then high would be mid minus one. High becomes zero, mid minus one, this is one. But stop. Because this is termination condition. Because low is greater than high. So loop will search space is exhausted and it will terminate. At last, what is the first? It's -1 itself, so it will return -1. Because we haven't updated this. Because we know we didn't get any case that we have to update this. So it remains -1. So it will return -1. That's exactly we want. If element is not there, return -1. This is the first occurrence we are checking. Now go for last occurrence. Now if you want to go for last occurrence, see. Same, I'm taking target is eight and go for last occurrence. Apply binary search. So same, we know the funda of binary search, we have to find out mid every time. So low is zero, high is five. 0 + 5 / 2, that would be two. Mid is here. Now check seven. Target is eight. Mid element is in this case less than eight. If it is less than, so we can surely say it would be to the right part. So to go to the right part, this side, low would be mid plus one. So it's three and five. 3 + 5 / 2, that is four. Now mid is here. Check this. It is eight. Yes. It is now our mid. Element is equal to eight. So we can say I'm finding last occurrence. So at first we are taking a variable last is equal to -1. Yeah, we can say that this is my answer. First time we got eight, so this may be my answer. But maybe to the right hand side we can have more eight because you have to find out last occurrence. So maybe array is something like this. I'm having eight here, eight here and then 10. So we cannot say that just return this and this is my answer. No, you have to find out last occurrence. So last occurrence is this. Okay? So let's just make it as it is, same array. It may be my answer, but I'm not sure it is the answer. So let's update this to four. At least we got one thing that eight exists, so four. Last is four. Now if you want to find out last occurrence, so definitely I can say last occurrence of eight would be to the right part. Yes. Because if you move to the left part, it you will get maybe first occurrence you can get, not last. To get last occurrence, last position, you have to move right. Okay. To move right, you have to do low is equal to mid plus one. So it becomes 4 + 1, five. Five. Now this is my search space only. So 5 + 5 / 2, that is five. So mid is high here. High and low are here itself. Check eight, 10. 10 is less than uh sorry, greater than eight. Yes. So eight can exist to the left part itself because it is greater. So eight can be to the left hand left part. Not to the right of the 10, but left of the 10 in sorted array. So now you have to search in left side. So to go to left side, you have to do high is equal to mid minus one. So high becomes mid minus one, that is four. It is five. But this is the termination condition because low becomes greater than high, so terminate the loop. Yes. At last now right now last is four, so return four. And that's exactly my answer. Four. Yes. More cases also you can take. If you want to find out the last occurrence of suppose here seven. So our target is suppose seven. Last occurrence for seven. Same, we have to apply the same thing. So 0 plus it's five, it's two. So here we are having two, so target is equal to this. ARR of mid. At first last is -1. So it may be my answer, but I cannot say that it is the surely the last occurrence of seven. It may be my answer, so update this with index two. So now for the last occurrence of seven, I can surely say that last occurrence would be to the right hand side. So move to the right. To move to the to the right, low becomes mid plus one. So three, it's five. 3 + 5 / 2, it's four. Now mid is four. Low is here, high is here. So we have this search space now. Mid is here. It's eight. Eight. The element is eight is greater than the mid element there. Array element is greater than the target element. It's greater than. So we can surely say that our target would be to the left part of the array. So to move to the left part, high becomes mid minus one, that is three. Three. 3 + 3 / 2, it becomes three itself. So search space is this only, only one element. Low, high and mid are pointing to this. Now eight. Mid is three, so at this we are having eight. Eight is again greater than seven. So we know that our target element is less than the array element, mid element, so it will lie definitely definitely to the left part. Yes. So now again, if you move to the left part, then high becomes mid minus one. So it becomes two, it becomes three. But this is the termination condition because this is two, this is three. So low is greater than high. So there is no search space now. Low is high. Sorry. Low is here and high is here. So in between there is no search space. Okay, at last now last is two. So just return two. So we can say that definitely this is the last occurrence of seven. This is first occurrence, this is last occurrence. So this is how using a binary search you can simply find out first occurrence, last occurrence. If you want to write down this thing in code, so how you can write? See. So we are having here low is equal to zero and high is equal to we know whatever the array.length -1. This is for sure. Right? And int first, we are going for first occurrence. First is equal to at first -1. So this is the method. It will return int something int type of thing. Array and we are having target is equal to X. Now while we know the condition is less than equal to high, loop will run and in this loop at first obviously you have to find out mid, that would be low plus high minus low divided by two. Simple. Now if if this ARR of mid equal to equal to whatever the target element, then what you will do? If it is equal to X, mid is equal to X. You are going for the first occurrence. It may be your answer, we can say. So we just update this. First is equal to whatever the mid is. It may be your answer, but first occurrence would definitely lie to the left part. So what you have to do now? High is equal to mid minus one. If this is the case. Yes. Else if this ARR of mid is greater than if it is greater than X, greater than our target element, so mid is greater, our target element is smaller. So we can surely say that our element lie in the left part. So you have to do again high is equal to mid minus one. Simple. Else, if this is not the case, then in else part simply we can do low is equal to mid plus one. That's it. This is where applying simple binary search to find out first occurrence. Got it? So, we only change first if you get that element whatever the mid element is equal to X, we change this, but still we check in the left part, so we change high as well. Again, if it is greater than X, so we move to the left part, we'll not change uh that first uh this this variable. If this is the case, greater than then high will change, otherwise low will change, we change uh we uh search in the right half. If this condition is not true, in that case our element would be definitely you can say less than this mid. Because if it's equal to mid, then this condition would be hit. If it's greater than then this, if less than then low becomes mid plus one. Sorry, in this case uh in that case our X would be greater than. If this condition is not true, then X would be definitely greater than mid, so it would be in the right half. So, we'll go low is equal to mid plus one. So, this is how you can get first occurrence. Now, if you go for last occurrence there would be a little bit change. This would be as it is. Rather than this, first we are having last is equal to minus one. I hope you can change it, so you can right now pause the video and try this out. For last occurrence, you can just write down this code. Pseudo code. So, name we can change it's last occurrence. This condition would be as it is. Mid would be as it is. Now, if this is equal to X fine. Now, you have to change here. It's not first, it's last equal to mid. But now if a target element is equal to mid then it may be our answer. It may be the last occurrence because element may be one only in that array, but if there are duplicate elements so last occurrence would would definitely lie in the right half. Yes? So, in this case, now you have to change here. It would be low is equal to mid plus one. The condition. Just you have to change a little bit. Right? Now else if equal to then this would be executed else if array of mid greater than X array of mid is greater than our target element. So, we can surely say that our element would be if this is greater than, our element is less, so it would lie in the left part. So, high would be mid minus one, otherwise low would be mid plus one, simple. So, you have to change a little bit here, this these two lines. These conditions would be same. This is we are applying simple binary search to find out first and last occurrence of the element. So, two approaches we have seen. And you can also get with lower bound and upper bound what a first occurrence and and last occurrence. So, I hope till now it is clear to you. Now, let's discuss I'll code this also. This is pseudo code, simple. So, let's clean it. And now this is the array. See, 5 7 7 8 8 10. If you want to uh eight, target is eight, lower bound for eight is definitely this. And this is the first occurrence. Upper bound for eight is here. If you want to find out upper bound for eight then this would be upper bound. The first element which is greater than the target element, that is 10, so this is upper bound. So, that to get the last occurrence, we can simply do whatever upper bound minus one. Simple. So, if you know how to find out lower bound upper bound, simply you can use the third technique as well to get first and last occurrence. Yes? For same, but here uh one situation is suppose uh here I have six, target element is six. Right? And I want to get the lower bound for six. So, if you get the lower bound for six, then it will return the smallest index I know smallest index where this ARR of I is greater than equal to X. It is lower bound. And upper bound is smallest index where this ARR of I is only greater than X, not equal to. We know that these two things we have discussed. Right? So, six, if the target element is is six, so smallest index this condition where this condition satisfied, ARR of I is greater than equal to X. So, if this is six then what is the smallest index where this condition satisfied? This. Because in this case, five is five greater than equal to X? No. Seven greater than equal to six? Yes. So, while lower bound, it will return in this case 0 1 1. Lower bound for six is one. But I cannot say that lower bound will give first occurrence, upper bound will give last occurrence, but here it is not true. If it is six it should give minus one, but lower bound is giving us something. And same, if X is suppose 50 or 15 then what lower bound will give us? The first smallest index where this element would be greater than equal to X. So, if you go for lower bound, it will return at last the low and low would be at last here. If element is greater than all the element, then it will return uh whatever the length of the array that is in this case 0 1 2 3 4 5 uh it's six. Three and three six. So, in this case, it will return six. So, these are some edge cases. You cannot simply just copy paste lower bound upper bound and it will give you first occurrence and last occurrence. Upper bound is fine. Just do upper bound minus one, it will give you last occurrence. Lower bound, there are two edge cases. So, you have to check this thing. After getting lower bound, you have to check if if this lower bound is equal to is equal to length of the array, suppose N. Length of the array is N. If lower bound is equal to length of the array, in this case six, in case of five. In this case, element doesn't exist, we know. Right? One more case you have to handle this, six. Or or now lower bound in this case, if target element is six, it will give this one. So, you have to check the element is this one, is this the target element you are you are searching for? If it is six, then it's fine, otherwise element doesn't exist. Or we can say ARR of lower bound not equal to the target element. You simply print here element doesn't exist, return minus one. This, minus one. For first, because lower bound will give you first occurrence. Right? Lower bound for eight is this, upper bound is this. So, lower bound will always give you first occurrence. First occurrence is nothing but obviously same. The smallest index where the this this element existed first. Right? Smallest index. So, this is the smallest index where eight occurs first time. Right? But these are two edge cases. Using this condition, we can handle these edge cases. If this is the case, after getting lower bound, you have to put one more condition, this is the case then return minus one, element doesn't exist. Right? So, now let's just code this, how to find out first and last occurrence and all the techniques, linear search, binary search and with lower bound upper bound. Three techniques. And these are we know uh we are getting lower bound upper bound and binary search, that is log in time complexity, so yeah, that's it. Let's code it. So, in lead code, we are having this question, first and last. So, we'll uh simply take there also the same thing. Nums and target, the same name, so that we can easily uh copy paste that here. Right? Now, let's just create a new Java class here. First and last position. So, let's take this uh only the same name array that we have taken the previous case. And here I'm taking target is three, so first occurrence and last occurrence of three. Right? Okay. Let's go for now linear search. First. Simple, the brute force approach. We check with every element. Right? So, let's name it first and last position and target. So, we have a static, so it will return an array. So, the return type would be an array. And first and last, the name is this. Because minus one minus one it should return. Let's name it nums and this target. At first let's just have a array of like you can say result is equal to at first we are having minus one and minus one. Right? Now the loop would be till we know zero. I is equal to zero till I less than whatever the length of the array. Sorry, we are taking here nums, not array, nums. length length and I plus plus. Now, you have to check. If Okay, go for the first ARR of sorry, not ARR, nums of I is equal to is equal to whatever the target element, target element. Then we check if this first, so result of zero is equal to is equal to minus one then update this. This becomes result of zero becomes whatever the I is right now is equal to I. Just update this. And after this if simply not in else part simply update this result one is equal to I. Okay, this will give you the last occurrence of every time update this if you get next occurrence of that element. Simple? And at last after this for loop after for loop we're going to return because we're going to return array so just return here. Return whatever the result is. That's it. Result is an array. So we are returning an array so definitely here also you have to take an array variable to accept that thing. So suppose I'm taking array of answer is equal to this. And now you have to print. So we cannot simply print answer because you have to print we know that two string with two string. So arrays dot two string and within this we just pass the answer. It will give you you know that array format. So this is how it will give the content of this array. Whatever the content in this array in string format so it will give minus one minus one if required. If element doesn't exist. So here we have three so it will not give you minus one minus one. Let's try to run this and it should give you zero and one. First first occurrence is one and the last is two three four five six seven. It's seven one and seven. If you go for an element five both first and last occurrence are I think eight and eight. Yes. If you go for an element 50 element doesn't exist here so it will give minus one minus one in both the cases. If you go for any element like two two is also not there so it will give you minus one minus one. But you know the time complicated of this that is not good. But this is how like you have to move. First directly don't jump to the optimized approach. Try to code the naive approach as well which is you can say the brute force approach. Second thing let's go for now binary search to get first and last position. So you have to first see in this case in simple one method you got first and last position. But when you go for binary search there you have to call two times. Binary search first you get first occurrence then last occurrence two times. Let's run let's code that thing also. So we just comment out this thing and so we are having this first and last position. So in this case I'm having first occurrence and last occurrence different different. So one method is having for first position for first occurrence there I'm just passing whatever the nums sorry it's nums and whatever the target is. And second is last position. I'm just passing nums and whatever the target is. Yes? So let's code these two also static first position so simply int there's no array it's only first position so int and first position. So here we have same name I'm taking nums and target. And like this we'll be having one more for last. Two methods we're having. One is first one is last position. Now we have to code this. So here suppose we are having an array or don't take an array. Let's see that. First let's code first and last position. So first position. Now simple you have to apply binary search so simply we take same low is equal to zero and high is equal to nums dot length minus one and int first is equal to at first I'm taking minus one. Now check. While condition would be I know less than equal to high till then the loop will run and you have to find out mid as well. So same you have to write here. So this is the case. Right? So now you have to put the condition. You are getting first occurrence first position first occurrence. So if this sorry not here I'm nums the array name is nums. Nums of this mid equal to equal to your target element. If this is the case then it may be your answer. So we can change first is equal to whatever the mid is. But we cannot surely say that it is our answer. Our answer lies we know that for sure now in the left half because mid is equal to our element so first occurrence of our element would be definitely if there is more element and you get the first position so that would be definitely to the left side. So to go to the left side you have to move high. High is equal to mid minus one for sure. Else else if if that element it's mid is you can say less than or let's say greater than or less than in any name you can take any operator. Because we will take we will take both the things. If it's greater than our target mid is greater than the target means target is our less than mid. So target definitely lie in the left half if target is less than mid. So you have to move to the left half. For left half again high becomes high is equal to mid minus one. And one more case that would be easily handled by by else. Else low becomes mid plus one. Simple. And at last here we can simply return whatever the first is. Like this. I hope you got it. Now code for the last position. Pause the video and now you try this out for last position. So for now let's just copy paste the same thing because we have to change a little bit. You don't copy paste you just try out this. Okay? You have to write everything. Last position. So low high this first rather than first now you got the last position so last is equal to minus one. Condition would be this only. Mid is this. Now if this is equal to target then we have to change last. It may be our answer may be our last occurrence. So last is mid but we are not sure. To get the last occurrence you have to move to the right half now because last occurrence would definitely be to the right half. So to move to the right half low will become mid plus one. So now we have to change this. Now low is equal to mid plus one. Yes? Else if this mid is greater than target this would be same because target is less so we have to move to the left part. To move to the left part high becomes mid minus one else low is equal to mid plus one. These condition would be same only you have to change this thing. Yes? Now return last. Simple. Now we got both first and last. So we have one more we can say here. So now first and last position this is the method again which is calling both first and last position. So in this suppose suppose we take an array we take here an array. At first both are having minus one minus one. So we have this result of zero. Or we can say suppose we are having here element int first a variable int first is equal to this. I'm storing that in first and last. So int last the same name I'm taking. Last is equal to this. I'm not taking any array suppose. Let's take an array as well. So the thing is if see first is minus one I think about this. If first is minus one I have called this first position this method and this returned minus one. Minus one means element is not there because there is if there is no first position then element is not there. So why to call last position this method? No need to search for last occurrence if first occurrence is minus one. Okay? So this is like you have to think smartly. If this first is minus one no need to call this. So you have to just make a check here. If this first is equal to is equal to minus one then what to return? What to return? Simply return minus one minus one and result is right now minus one. I mean the array is minus one minus one so simply return this. No need to call the last. If this condition is not true then we call last. Then we can simply return either you can we can simply return here what? At first whatever the first is given or the lower bound. Sorry not lower bound it's first. We are not going for lower bound upper bound in this technique. Whatever the first is there, comma, call the last position. And pass here nums, comma, target. Simple. But in Java, you cannot write down something like this. Maybe in C++ it's allowed. You cannot simply write down array initializer something like this because this is array initializer. You have to write down here new int. New int something like this and then you can use array initializer. Right? So here also, if you don't want to take this result, here also you can return simply -1, -1. We know but this is array initializer. We cannot write down something like this. So you can just add new int this. Return new int. Uh you can say that um locate memory to the array. New means yeah, we are allocating some memory to the array and then obviously array initializer we can write. So first and first is as it is and last position would be call this last position here. Whatever it will return, that would be your last and simply return this. Right? So it is returning array. So we are having an answer this. Whatever this method will return, we are storing this into this answer and we are just printing answer to string dot answer. Let's run this. Target element is two. Two is not there in this array. So it will give you -1, -1. See. Yes. If target element is three. And we are having suppose 0 1 2 3 4 4 3 itself. Let's run this. So it will give you one two three four five one and five. One and five index. Yes. If the target element is suppose one, it will give you zero and zero because only one is there. Zero and zero. I hope you got this. So this is how you can go for simple binary search. You have just applied simple binary search to get first and last position. So the time complexity for this would be you're calling two things, first position, last position. For both you are calling binary search. So log in for this, log in for this. Two log in. Two into log in. Time complexity. Big O of two log in. Okay. And space complexity is are you taking any extra array to get your answer? Yes, you are taking an extra array. Here I'm not taking any extra array. Here I'm not taking simple variable you are taking. So for that space complexity would be constant order of one itself. But uh yeah, here we are having some array. Right? Here also we are having this array. So space complexity would be but this array actually doesn't depend on the um you can say that array size whatever is given. It's constant. It's two only. So the time complexity is also constant in this case. Right? If you want to copy paste, if you want to submit your answer here. So let's copy paste this. If you are having search range. So in this first position, this is last position and this is our first and last position. If I run this, let's see what is happening here. You got an error. So in this it is returning what? Search range. It is returning an array. So let's copy paste this thing there. Let's copy paste this and for first occurrence and last occurrence first and last position. Just copy paste this code as well in this class out of this method, obviously. Here. Okay. Let's try to run this and see what is happening. So yeah, we got it. Accepted. Every case we have passed every case. So if you submit it, let's try to submit this and see what is happening. So yeah, we got it. Accepted. Right? So you can analyze the complexity as well. But for that you have to take the premium uh you get subscription for this LeetCode. Right? It will show you that thing also. Let's find out lower bound, upper bound and that's it. Lower bound will give you first occurrence, upper bound minus one will give you last occurrence. Right? So let's if you um change the name or don't change the name. Let's just uh comment out these things. And we'll simply go for first lower bound. So we just copy paste whatever the here the code of lower bound. And we simply copy paste the code for upper bound. After this for upper bound. Right? Now first and last position. So uh let's have the same method here. The same thing. First and last position and this method will call upper bound and lower bound rather than first position and last position. So at first I'm calling lower bound to get the first position, right? And then I'm calling upper bound. Upper bound but it will give you upper bound minus one. At last you have to do minus one to get the last occurrence. So same if first or the lower bound is zero, uh sorry, minus one, we cannot change it. But the thing is here you have to take care of that edge cases as well. So what are those edge cases? Here in the lower bound, obviously you change delete this. And at first we are having suppose lower bound is equal to minus one. Then this mid is equal to this. If it's greater than equal to this, then obviously lower bound means uh that that the first smallest index. That would be greater than or equal to this. So smallest index would be in the left half. So high is equal to this. Else this is equal to this. And then return whatever the lower bound at last. So if this is the case, then it may be an answer. So here we can just update lower bound is equal to whatever the mid is. It may be an answer first. It may be the first occurrence. But we are not sure. Otherwise, if you don't want to take this LB as another variable just to save the space, you can go for return low as well here. That is also fine. Right? And um upper bound is upper bound is array dot length minus one. No, we change it. Upper bound should be minus one at first. So or let's keep it as it is because if you're going for lower bound, upper bound, in that case we know that we take the hypothetical value array dot length. So rather than minus one, you can change it. Better to take it same like array one whatever the length of the array. We know this happens when you go for lower bound and upper bound. It's not correct to get to write here minus one. So in upper bound also this is the case. If this is greater than, then maybe an answer. But upper bound maybe in the your answer maybe in the left part. Right? So high is equal to this and this is low is equal to mid plus one in this case and return UB. But here now after calling this lower bound, let's suppose I'm taking not first here. I'm just taking here lower bound. So LB. Simple. You have to check the edge cases as well. If this lower bound equal to equal to array dot length. Sorry. It's nums dot length. Nums dot length or second case is this nums of LB. Whatever the lower bound you will be given, at that it's not equal to the target element. In that case, we can say that element does not exist. It will simply return -1, -1. So same case you can take here new -1, -1 or if you're not if you're not getting why this new int -1, -1, simple method is okay, let's take an array -1, -1. Return result. Simple. Return this array result. This is -1, -1. Fine. If this is the case. Right? Otherwise what you need to do? Don't need to check this thing. Otherwise simply return here we have lower bound upper bound minus one. Or if you don't want to return this thing, if you're not getting why new int and all. Now if lower bound is not this, then obviously in lower bound we have some value. So this call the upper bound as well. So int take a variable upper bound is equal to let's call here the method upper bound passing the array names and nums and target. So it will give you upper bound. Now we have two values. One is in this LB, one is in UB. So what we can assign this. So what we can do? Result of sorry not return it's result result of zero is equal to whatever the lower bound and result of one is equal to whatever the upper bound. And then simply return result. That's it. But yeah, if you don't want to take this much of headache like this and this simply in one line you can return this. Okay, sorry not upper bound upper bound minus one. Take care of this thing. Last occurrence will be upper bound minus one. Now return result. And that's it. If you're returning result it will it will give you we'll get this in the answer and uh simply print this. Okay, if you don't want to take a secondary simply here also you can take system.out.println. I don't want to take a answer array here. Arrays.toString and here here I can simply pass I can simply call this. So here just call this. So don't need to take a another array. If you want to like you can say minimize the space in that case. Right? Okay. So I'm calling here first and last position this method and this is calling again lower bound and upper bound. Let's run this and see. Target is one lower bound upper bound for one is we know it's 0 0. So it will give you 0 0. Okay, it's working fine. Let's check for three. Let's run this and it's one and one two three four five. One two three four five one and five. Okay, it's working fine. If I go for 31 let's run this. If it's 31 then minus one minus one. Yes. And if it's supposed two then also it's minus one minus one. If you want to check how this thing is running you can just dry run this. First you can just debug this. You know how to debug just add some breakpoint and step over step over and you can see how this program is running or better way is dry run this. Write down on a piece of paper and you have to be your own debugger. Dry run that. You will get the actual working of this thing. So this is that you can see the third uh way to get first and last occurrence. You can also submit this. Right? So I I told you how to submit. Okay, just run that first check the test cases and then submit. Okay, now see one thing. We were using binary search to find first and last position. So first position is this method for last position is this and in first and last position in this method we just call first and last position and that's it. But the thing is the thing is there's so much duplicacy of the code. See, everything is same in both the if you check here first and last position only the only the difference is see in this part if mid is equal to target in this case first is equal to mid and high is equal to mid minus one. In last position if mid is equal to target then last is equal to mid low is equal to mid plus one. Only this is the difference. Else if this condition else if this condition is same else this part is same and we are returning here first and here we're returning last. So can we call only one method? Can we just remove this redundancy why to write down both two methods? Can we call can we do something like this? One method only and just apply some check there. If you want to find out first occurrence then apply this condition. If you want to find out last occurrence then apply this condition otherwise all the other conditions are same. Yes. So pause the video and try this out. Now let's see. We are just doing what we just copy sorry comment out this thing. In first and last position this is the case and here I'm calling not first and last. Here I'm simply calling int first is equal to I'm just taking the name here. Comment out this. Taking the name here int. First is equal to uh find position that's it or search position. Search position. And I'm passing the array that is nums and the target. And one more thing you have to find out if you're finding the first occurrence so you have to find out you have to pass yes I'm finding first occurrence. So you can pass some value like uh 40 something like true like finding first position finding first index true. Right? So let's have a method here search static int and search position and here I'm just taking first is arrays nums then int target and boolean. Boolean find find first occurrence or first position we are taking here position so let's take find first position. Something like this and again if you want to go for see go for the last so int again call the same method search position but here just find first position no so pass here false. Based on that just update this thing search position. Right? So here everything would be same. Uh this this this while this condition mid is same so let's just copy paste this only. We are having low high and don't take last is equal to minus one delete this. Low is less than equal to high then mid is equal to this okay fine. Now we cannot directly write down this condition first if mid is equal to target then this this because these two conditions are different in both the cases. These two conditions are same else if this and this so first write down these two conditions. So we can write down this thing if this nums of mid nums of mid is greater than the target. If it's greater than then you have to do you can search obviously in the left half so high is equal to mid minus one that we know. If this is the case then this thing. Else if this nums of mid is less than the target then we know the target is definitely in the right half. In that case so low becomes mid plus one. Now one case is still left. Else if it's equal to mid else if it's equal to mid these two cases are different. In first case if it's equal to mid then first occurrence should be definitely in the left half. In last if you want to find out last position then if it's equal to mid then last occurrence is definitely definitely in the right half. So now you have to apply the check else else now check if if this find first position is true or you can simply say is equal to is equal to true but don't need to write down this thing. This line is come enough for this. If it's true means you have to find out first position. In that case in else part okay sorry in else part first we know what is the situation. If this is not true this is not true then mid is equal to target then it may be an answer. So first you have to change first you have to change. Suppose we have here answer. Int and we have suppose here POS position position at first. So else POS is equal to whatever the mid is it may be an answer we are not sure. Now change it if this is true find first position is true then first occurrence would be definitely in the left half. So you have to change you have to do high is equal to mid minus one. Yes. Else just do low is equal to mid plus one. Simple. And you're changing the position here. And at last we just return this POS. Yes. So when you're calling search position with this true it will return first if first is minus one so you can just write down here this condition. Don't need to go for the don't need to call second time the search position. So if it's minus one we can simply return here we can just take it suppose we just take result is equal to minus one minus one. And you simply return here whatever the result is simple. If it is not minus one in that case at first we can say here the position is minus one. In search position at first let's initialize position is minus one because if you'll not get anything that definitely position would be minus one. So you have to initialize it with minus one. And at last now then after this return whatever the position is. Once this uh loop is over. Return position. And that's it. Now if this first is minus one or you can say whatever position it will return it's minus one, then return simply the result that is minus one minus one. Otherwise we call last for search position and here we uh obviously pass false. And then if you don't return something like this, comment out this. So we can do one thing. Result of sorry not return, it's result of zero is equal to whatever the first and result of one is equal to whatever the last. And now we simply return the result. Simple. That's it. So we have just called only one method now based on this check. Right? That's it. No first position last position two methods. And in main we are just calling here first and last position and it will return some array obviously so we are just calling arrays.toString first and last position. Let's search for two. Let's run this and uh it will it should give you minus one minus one because there is no two. So minus one minus one. Fine. Let's search for three. So it will give you the value. The index value one and five. So one two three four five. Yes, correct. If you go for uh seven it will give you obviously the index is zero one two three four five six seven seven seven. Yes, it's So this is how you can optimize it a little bit. Rather than calling two method, only one method you pass just based on some uh pass some uh checking condition. Whether you're finding the first position or the last position, that's it. Okay, now there's one more question, see. You have to find out number of occurrence. Number of occurrence means you have given a sorted array or list of integer I ARR of size n and an integer x. You have to find out total number of occurrence of x in the array. And this question is being asked in these the companies, even Amazon. So these are the companies where this question has been asked. Right? So it's very simple I guess. You can easily answer this question. Till now we have seen whatever questions based on that only also already you can give give this answer this question, see. Input any seven x is three. Array is this. So how many times three is there in this array? One and two. Output is two. Yes? So see how can you You can easily I guess solve this. If you know the first occurrence of three and the last occurrence of three then last minus first plus one. That's it. Is it or not? Yes? See. Suppose I have this array. And my x is equal to 20. My element is 20. I want to find out how many times this 20 is there in this array, number of occurrence of 20. So we know the array is something like this five six seven eight nine. The index is something like this. Now if you want to find out number of occurrences then the very simple approach it's naive approach that brute force is what? You start searching from first. Is this 20? No. Is this No. No. No. No. No. Yes. This is the first 20 you get. As soon as you get 20 just take a count variable at first zero. At first suppose we have count is equal to zero and then we'll do count is equal to one count plus plus. Then go for next. It is 20? Yes. Again count plus count plus plus. Is it 20? Yes. Again plus. Is it 20? No. And I'm the last of the array till the last of the array and now at last count is equal to three. That's it. Yes? If suppose I want to find out x is equal to my x is equal to two. So again check from the first. Is this two? No. Is this two? Yes. So count would be at first count was zero. Count will will become one now. Is this two? No. Two two two. You check for everything every uh element and count is now one. So it's like linear search we are doing. But obviously the time complexity in this case is order of n. Because it's linear search. We are searching each and every element from first to last. Right? Or you can do one thing like after this 20 once you get 25 and here I'm having 30 31 and something like this. So once I get the element greater than this 20 maybe you can stop. And if you can just put this kind of condition and break the loop and all. But still still you are going from zero till like one by one you are checking all the elements so s- it would be considered as order of n in worst time. Because it will increase linearly something like the graph would be linearly something like this. Right? But we want a better solution. Log n. Can we do this with log n? I guess you can do this. If you think a little bit you can easily do this. If you know if x is 20 suppose and if you know the you can say the first occurrence of 20 and the last occurrence of 20. If you know this index six at six this is the first occurrence of 20 first position eight is the last position of 20. Then I can easily find out the occurrence. I don't I think don't need to explain. Eight minus six then plus one simple two plus one that is three. Simple. Yes? Same here x is two. x is two. Right? So first occurrence of two is one last occurrence of this two is one itself. So both are one one. So how you can get one minus one? Last minus first plus one. So that would be one itself. And we know that number of times two is in this list is array is one time. So and we have already done how to find out first occurrence, how to find out last occurrence. So you have to update that a little bit. Just add a count method as well. And then last occurrence minus first occurrence plus one, that's it. So let's try out this. So let's create here a new class. What we are doing? We want to count occurrences. Count occurrence occurrence of elements. So we'll follow now the linear search first. Right? So let's have an array. Array we'll take this one only and the target is seven. So let's take this array only. Target is seven. Occurrence of seven I want to find out. Right. Now first I'll go for the linear search. So uh let's have a method itself is equal to count. Count occurrence in this ARR array and the target is whatever the target you pass there. And we can simply print at last the result. Okay, fine. Now let's define this. So it will return a int value count occurrences and we are passing the array so we are having here an array and int target. So at first we take count is equal to at first zero. So now we will move the for loop would be from first to last. Right? So you can use either traditional loop or for each loop as well. Let's loop in this case for each loop. So int num whatever the array. This now check if this num equal to equal to target in that case just do count plus plus. Simple. Right? Otherwise don't we have to do anything and after this for each loop whatever the count just return return that. Simple. Let's run this. For seven it should uh give one okay the occurrence is one itself. Okay, it's fine. It's working. Now let's go for the target is suppose three. Let's run this. It's one two three four five five times. So yeah, five. It's working. Now target is suppose 31. It's not present so count is zero. So it should give zero. Yeah, it's zero. But this is linear search and obviously the time complexity is not that much great. Now go for binary search. Okay. Now let just comment out this thing. Okay. Now Now let's just refactor this. Count occurrence uh using linear. Just refactor. Now, let's create a new class, and there we have count occurrence using binary. Using binary approach. Okay. Uh, let's just copy-paste this thing as it is, and we'll change accordingly. Because, um, this is same. We have array, and the target is this, and we are calling count occurrence and all. Okay. Now, in count occurrence, what do you need to do? First, we'll just, um, find the first occurrence, then the last occurrence, and then just do last minus, uh, first plus one. We know how to find out first and last occurrence. We know the thing. First and last position. We can easily find out with this search position a method. Either separately you can find out first, first occurrence, last occurrence, and then do. Otherwise, this was the approach. We have modified it a little bit by calling, by passing one more, um, argument, that is boolean, find first position or not. So, we can have this thing also. So, let's just copy-paste the same code from this. Using binary. So, we are having here. We are having See, first and last position we want to find out. Okay. Uh, here the result is zero. So, first is equal to the search position in this. Delete this, this line. And now we are having first it's minus one, then result, and last, and last. Okay. Let just come in, uh, sorry, delete this thing also. So, this will give me first and last position. This is calling search position. So, this is the search position method. Okay, fine. Count occurrence. Now, in count occurrence, count is, say, let's say we have zero at first. So, we know now the first and last position from this method. So, we can call this method from count occurrence. Right? Just delete this thing. And now, just write down the code. Now, we are calling this first and last position. We are passing the whatever the array and the target. Yes? This will return an array. Because it is returning result, and result is itself an array. So, to store this, we have an array itself. So, we have an array. End of array, and, uh, the name is I'm taking answer. Is equal to this. Whatever it is returning, I'm just fetching that in this array, answer array. Now, count would be what? Now, suppose if this is, uh, you can say the first it's it is minus one. The first is minus one, then there is no, like, the element is not there. So, we can simply do if answer of the first element is equal to is equal to minus one, then return zero. Or return count, because at first count is also zero. If this is not the case, then we do something like this. What we do is then we update. Now, count becomes answer of the last occurrence is at this index one minus answer of zero. Just put it in the bracket. And, uh, plus one. Simple. That's it. And simply return whatever the count you have. It will return the count here, and we'll print that. Let's run for this for 31. So, it should return zero. Yeah, it's zero. Now, again for three, it should return three and five, five. So, it's five. If I go for one, it should return one, because one is only one time. So, it's one. If there is nothing in the array. Let's run this. Now, it should return zero. Right? Because there's nothing in the array. And if you have zero itself here, then also, obviously, there is no zero here, so it should return zero. Zero. So, like this. This is one more case. But here, same like it should be log n. Because see, here we are calling count occurrence. In count occurrence, this method we are again calling first and last position. Now, go for first and last position. In this, we are calling search position. Right? Two times. One is this, one is this. So, it should be two of log n. In search position, we have a loop, obviously, while loop it is running till low is less than equal to high, but, uh, dividing by two each half. So, it's binary. So, basically, log n. So, log n and log n. It is like two log n, because two times we are calling this. Right? That's it. Complexity would be two log n with some plus some, uh, constant values, maybe three, four, five, or 10, 15. But we ignore these things. We ignore constant. So, complexity would be we take it log n itself, base two. So, that is much better than the previous, that is order of n. Okay, so this is the uh, second approach to find out, to count the occurrences of an element in a sorted array. And if my, if I copy-paste my code here, it's, uh, n, and we're having x. So, we are having rather than target, we are having x here. So, let's call it. We are passing x. Okay? Now, obviously, you have to copy-paste these things also, these methods. So, we just copy-paste these things also. Search position, target, and, uh, this, this, this. Let's run this and see it's working or not. There are 15 test cases. So, yeah, we are done with all the test cases, and, uh, if you want to submit this code, then let's see it's working or not. Okay, like this you can, uh, submit it. Right? So, you are better than 91% of the students. Maybe in space complexity you can do something better in this case. So, I hope you got these type of questions. Uh, we'll see more practice questions as well, but you also try out now. Go for, uh, maybe on LeetCode or on some other coding platform, go for these, uh, sorted arrays questions asked in top tech companies or these things. And just keep in mind one thing, if this is sorted array is given, apply binary search. You'll get optimal solution. Maybe you have to modify that binary search a little bit. And if you know about lower bound, upper bound, you can solve easily many questions if you aware about that technique. Right? So, now that's it for this lecture. Now, I'll see you in the next lecture with some more practice problems. So, till then, bye-bye. Take care.