Peak Index in Mountain Array ｜ Binary Search ｜ Lee..
Peak Index in Mountain Array ｜ Binary Search ｜ Lee..
Category
📚
LearningTranscript
00:00Hi everyone and welcome to the complete DSA series in which we are going to do an important
00:08question which is called Peak Index in Mountain Area.
00:11Now if we want to read any other concept of DSA then it will be available in this playlist
00:16on this channel.
00:17Let's talk about the question Peak Index in Mountain Area.
00:20Now if we generally find the solution of this question on tutorials or on any online platform
00:26then the solution that we generally get may look a little unintuitive.
00:29So in today's lecture, the solution that I am going to discuss is slightly different
00:33from what is discussed on other platforms and that solution may look more intuitive
00:38as a student.
00:39That means the solution that we will discuss today, we will not feel that we have to remember
00:44it or we have to keep it.
00:46We will discuss it in a very practical, very intuitive manner.
00:50We will try to fit the logic of the entire binary search in this question practically.
00:55So our approach is going to be slightly more intuitive and more understandable.
01:25And they form something which we are calling a mountain area because our area is of a mountain
01:53shape.
01:54Another example of a mountain area can be, let's suppose we have written 1, 2, and 1.
01:59We started from 1 in this area, we went to 2, and then we came back to 1.
02:04So this is also a valid example of a mountain area.
02:07There will always be a peak in every mountain area and we have to return the index of this
02:12peak in the question.
02:13So this problem is also problem no. 852 on lead code in which we have to return the index
02:18of the peak element.
02:19So in this question, we are already given that the area is guaranteed to be a mountain
02:23area.
02:24That is, there will always be a peak in our mountain.
02:28Now before the solution, let's look at some of the characteristics of a mountain area.
02:32If the elements of our area can be arranged in a mountain form in this way, then can we
02:37say that in the beginning, our elements will be arranged in an increasing fashion.
02:42So we can say that whatever index we are talking about, if we are talking about the array of
02:47i index, then its value will always be greater than the array of i minus 1.
02:53That is, the next value will always be greater than the previous index.
02:56Like 3 is greater than its previous index, 8 is greater than its previous index, 9 is
03:01greater than its previous index.
03:02When we are talking about the opposite side of the mountain, then our elements are in
03:06a decreasing fashion.
03:07That is, if we talk about any index i, then it is greater than its array of i plus 1,
03:13that is, from the next index.
03:15For example, 9 is greater than 5 or if we talk about 5, then this is greater than 2.
03:19So in the beginning, our elements are in increasing order, and later our elements are in decreasing
03:23order.
03:24And the special thing about the peak element is that the peak element is greater than the
03:27left one and greater than the right one.
03:29That is, if our i is the peak element, then what will be its condition?
03:34If in the array, this i-th index is the peak element, or let's represent it with p, then
03:41this is going to be greater than the array of p minus 1 and this is going to be greater
03:45than the array of p plus 1.
03:48So this is an element that is greater than the left one and greater than the right one.
03:52So in our mountain array, there are some properties that follow each index.
03:58And this is very intuitive.
03:59We did not have to use much IQ to understand this.
04:01All this information can be understood by just reading the question.
04:04Now to solve this question, our brute force approach will be there.
04:08Brute force approach, which is probably very, very easy, is linear search.
04:15In linear search, we know that we can go to a single index and check whether our element
04:19is a peak element.
04:20Whichever peak element it is, it will satisfy these conditions.
04:23That is, for the peak element, we can see whether it is greater than the previous and
04:27the next one.
04:28First, we will check for this, we will check for this, we will check for this.
04:31Finally, when we check for 9, we will find that 9 is greater than 8 and greater than
04:355.
04:36So this is our peak element.
04:37It will take us a lot of time to perform linear search.
04:40And it is going to be a very easy approach.
04:42So we are not going to discuss this.
04:44Because most probably everyone of us can write its code.
04:47The approach we will discuss is going to be a binary search approach.
04:52Now how can binary search be applied here?
04:55How did it come to our mind?
04:56First of all, the array given to us in the question has some sort of data in it.
05:01In the beginning, there is sorted data in increasing order.
05:04Then there is sorted data in decreasing order.
05:06And in this, we have to find out a peak element, that is, some value.
05:10So in the last lecture, we have discussed that whenever there is a question like this
05:14where there is some sort of sorted data in the array, plus we have to find some value
05:19in that sorted data, some index, some particular condition.
05:22So we should definitely hit binary search in our mind.
05:25First of all, this is the reason.
05:27And the second reason is directly mentioned in the question that we have to solve this
05:31question in log n time complexity.
05:33So log n time complexity is generally seen in binary search.
05:37So we are going to use some or the other approach in the same way.
05:40And in the question, this condition is given to us.
05:43That is, there is a situation like this, which exists for our peak array,
05:46or for the elements before the peak or after the peak.
05:49Which is pretty straightforward.
05:51Apart from that, the second piece of information given to us in the question
05:55which is that our array will always be a mountain array.
06:00Our array will always be a mountain array.
06:03If an array is always a mountain array,
06:06then can we say that when we plot its elements, we will get such a shape?
06:10So from here, we can draw one more important conclusion before solving the question.
06:14That is, because the array will always be a mountain array,
06:18then the first or last element of the array can never be our peak element.
06:22Because if the first element becomes the peak element,
06:24then after that, the elements will be in a decreasing fashion.
06:27Or if the last element becomes the peak element,
06:29then all the previous elements will be in an increasing fashion.
06:31So the mountain can never be formed.
06:33So from here, we can draw one more conclusion that
06:35whether our index becomes 0 or our index becomes n-1,
06:39it can never become our answer, that is, our peak element.
06:44Because that will not align with the condition of the array being a mountain array always.
06:48So these are some things that we understood after reading the question.
06:50Now we know that if we want to find the solution of log n time complexity,
06:53then we will have to think in the direction of binary search.
06:56So to perform binary search, first we visualize our array in this way.
07:00We have 0, 3, 8, 9, 5 and 2.
07:04The first step of binary search is that first we take out our start and then we take out our end.
07:09So we took out our start and we took out our end.
07:12After that, based upon start and end, we take out our mid.
07:15We already know the formula for mid.
07:17Mid is always equal to start plus end minus start divided by 2.
07:21This is an optimized formula.
07:22Generally, it is the logic of S plus E divided by 2.
07:25But we have converted the same logic into this for better optimizations.
07:28So here when we take out our mid element,
07:30then according to our calculation, this is going to be the mid element.
07:34Then binary search says straight forward.
07:36After taking out the mid, the second step is to compare
07:39that the thing we wanted to find out, does it exist on mid?
07:43Now what do we have to find out?
07:45We have to find out the peak element.
07:46We already know the condition of the peak element.
07:49We already know its logic.
07:51So we can simply check that whatever mid we have,
07:54is it our peak element?
07:55And the condition to check it will also be very straight forward.
07:58If whatever mid we have in our array,
08:01its value becomes greater than our mid minus 1.
08:05If this is greater than our mid minus 1
08:08and if this is also greater than mid plus 1.
08:12So can we say that this is the condition of our peak element?
08:16So in this case, we have got our answer
08:18and from here we can return our mid value.
08:21So these two steps are very straight forward.
08:23But here when we check for 8,
08:258 will be greater than 3 but not greater than 9.
08:27So this means that 8 is not our peak element.
08:30So how do we find out the peak element?
08:32For that, we have to figure out the logic of how binary search will be applied here.
08:36Now the main logic of binary search,
08:38this was also discussed in the last lecture.
08:40The main logic of binary search says
08:43that how do we halve our search space on each level.
08:48That means how do we decide
08:50that next time our answer will be on the left side or right side.
08:53This is the main logic of binary search.
08:55That what is the condition on which
08:58we completely discard the left half of our mid
09:01or completely discard the right half of our mid.
09:04Because the step of discarding,
09:06due to which the time complexity login comes out.
09:09So this is what we have to figure out
09:11that now by identifying the mid here,
09:13how do we find out
09:15that our peak element should be on the left or right.
09:18So to identify it, let us see a diagram.
09:21Let's suppose our mountain area looks like this.
09:23Its elements are basically plotted in the form of lines
09:27and our peak element exists above.
09:29The first case can be this.
09:31This is case 1.
09:33In case 1, it is possible that our mid is our peak.
09:35In the case in which mid is peak,
09:37where will the mid lie in that case?
09:39In that case, our mid will lie here.
09:42And we already know its conditions
09:44that mid should be bigger than its previous element
09:46and bigger than its next element.
09:48So that is our peak element.
09:50Case 1 can be this.
09:52Can we say that in case 2,
09:54our mid will lie somewhere here.
09:56This is our mid and it is going to lie on this line.
09:59Our mid lies somewhere above our increasing slope.
10:03If we find out that our mid lies in the increasing part,
10:07can we say that the peak will always exist in the right side of the mid?
10:12The peak can never exist in the left side.
10:15I will repeat this.
10:17Let's suppose our mid is 8.
10:19We know that 8 lies in the increasing slope.
10:220, 3, 8.
10:24And the peak above is 9.
10:26So if we find out that 8 lies in the increasing slope,
10:29we will know that the peak will not lie in the left side of 8.
10:32We have to find our peak in the right part after the mid
10:37and reject the left part completely.
10:39And vice versa.
10:41If our mid lies in the decreasing part after the peak,
10:45can we say that we will never find the peak after the mid?
10:48We have to try to search our peak in this area before the mid.
10:52Let's suppose this is my mid.
10:55I know that values will decrease after 5.
10:58So we will not find the peak in the values after the decrease.
11:01We will find the peak in the left part.
11:04If we figure out that our mid lies in the left or right,
11:09then we will know where our peak element lies.
11:13Logically, if our mid lies in the left side,
11:17i.e. when the values are increasing,
11:20our mid lies here.
11:22So for our peak, we will always have to search in the right.
11:25We know that we will always have to search in the right for the peak.
11:29And logically, if our mid lies in the right side,
11:33i.e. in the decreasing values,
11:36then our peak will always exist in the left side.
11:40So we can also write that when our mid lies in the right,
11:44i.e. in the decreasing values,
11:46then we have to search in the left for our peak.
11:50So the main logic of applying binary search here is
11:54that we have to figure out whether our mid lies in the left or right.
11:58We already know that our mid lies in the peak.
12:01If we figure out the logic of left and right,
12:04then we will know how to apply binary search.
12:08So how do we know whether any index i lies in the increasing or decreasing side?
12:15It is a simple way.
12:17Compare it with the values in the front or back.
12:20Can we say that if our mid lies on this line?
12:24Let's suppose that our mid is equal to 8 in this case.
12:27So 3 must have come before 8.
12:290 must have come before 3.
12:31If these values increase, then we will reach the peak.
12:34Now if I simply compare my mid with the value before it
12:38and I get to know that my mid is increasing here,
12:41can I say that it lies on the increasing side?
12:44Let us resize this a little.
12:49So when will our mid lie on the left side?
12:51When the value of our array of mid minus 1
12:54will be less than the value of the array of mid.
12:57If the value of 3 is less than the value of 8,
13:00it means that the order is increasing.
13:03If the order is increasing,
13:05then we know that our peak element
13:07will never exist in the left side of the array.
13:10Where do we have to search?
13:11We have to search in the right side.
13:13So next time we will call to search in the right side.
13:16And in binary search, the call to search in the right side,
13:19what is that call?
13:20In that, we update our start to mid plus 1.
13:23So this is the logic of searching in the left side.
13:26Similarly, if this does not happen,
13:28that is, instead of increasing, we are getting a decreasing value,
13:31then it will be our decreasing order case.
13:33So the else case of this will be our decreasing order case
13:37in which our mid exists in the decreasing slope on the right.
13:40So this is the else case of the other
13:42in which we have to search in the left half.
13:44Searching in the left half means
13:46that we will update our end in binary search,
13:48which is going to be equal to mid minus 1.
13:51So this is our overall logic
13:53on which we will apply binary search in this question
13:56because of which time complexity will come.
13:58Because at every step, we are taking a decision
14:00whether we have to search in the left or right.
14:03And because of this decision, our login time complexity comes.
14:06So let's summarize the logic we have seen once.
14:09We started with some start value and some end value.
14:13Then we will run a loop similar to binary search
14:16till the time start is less than end.
14:18For start and end, we always have to find out their mid.
14:21We already know the formula for mid.
14:23It is start plus end minus start divided by 2.
14:26After that, first of all, we will check
14:28whether our mid is the peak element.
14:30When will the mid peak element occur?
14:32Mid peak element will occur when
14:34the value of our array of mid minus 1
14:36will be smaller than the array of mid
14:38and the array of mid will be bigger than the next value.
14:41That is, it is bigger than the left value
14:43and bigger than the right value.
14:45In that case, we will return mid as our answer.
14:49If this does not happen,
14:51if mid does not lie here,
14:53then we have to check whether
14:55mid lies in the left or right.
14:57Whenever mid lies in the left,
14:59its condition is that
15:01the value of our array of mid minus 1
15:03is less than the array of mid.
15:05This is the condition in which
15:07our mid lies in the left.
15:09We are not comparing equal to
15:11because it is already given in the question
15:13If the value of our array of mid
15:15is less than the array of mid
15:17then we do not need to check equal to.
15:19We can check only less than, less than, greater than.
15:21Whenever the old value is smaller than the new value,
15:23that is, which order is running,
15:25the increasing order is running here.
15:27That is, our mid lies somewhere in the mountain.
15:29If mid lies here,
15:31then the peak element will exist after mid.
15:33That is, we have to go right.
15:35In this case, we have to search to the right
15:37and searching to the right means
15:39that our start is going to be mid plus 1
15:41and if it is not the case,
15:43then it is the opposite.
15:45Opposite means that
15:47this time our mid lies on the decreasing slope.
15:49And lying here means that
15:51this time
15:53this is decreasing,
15:55this time we have to search to the left
15:57and searching to the left means
15:59that our end is going to be equal to
16:01mid minus 1.
16:03This is the logic of our overall binary search
16:05or modified binary search
16:07with which we can find out our answer.
16:09We will find out our answer and write its code practically.
16:11This is a corner case, an edge case
16:13which we have to see.
16:15And that edge case is that
16:17whenever we apply binary search,
16:19then mid value can be any value in it.
16:21It means that
16:23if we apply binary search on this array,
16:25then it is also possible that
16:27let's suppose we have to discard the left,
16:29we will find our answer on the right side.
16:31In that case, it is possible that
16:33we have to discard this and we will find our answer here.
16:35So, in the entire binary search,
16:37mid value can be anything
16:39because our answer can be anything.
16:41When we read a normal binary search,
16:43then the answer can be any value in it.
16:45Our target can exist anywhere.
16:47So, our mid value can exist anywhere.
16:49This means that
16:51mid value can also be the starting value
16:53after some levels or
16:55after some iterations or
16:57mid value can also be the last value.
16:59Now, the comparisons that we have done
17:01are logically correct.
17:03But from the code point of view,
17:05if our mid value is 0,
17:07then can we say that
17:090-1 index will never exist for 0?
17:11Or if our mid value is n-1,
17:13then array of n will never exist
17:15because it will overflow.
17:17So, here when we are taking
17:19mid-1 or mid-1 situation,
17:21then we have to apply many checks.
17:23We have to apply checks in the form that
17:25if mid value is 0,
17:27then we will not compare with mid-1
17:29or if mid value is n-1,
17:31then we will not compare with mid-1
17:33But one single optimization
17:35that we can do here is that
17:37we don't have to apply checks.
17:39That is, we already know that
17:41our peak element will never be the starting or ending value.
17:43This is already given in the question.
17:45So, we don't have to include
17:47this starting and ending value
17:49in the answer
17:51because in these values,
17:53in these indexes,
17:55our answer can never be 0 or 2.
17:57So, we will start our start from 1
17:59and end from n-2.
18:01Because in the question,
18:03we are already given that
18:05minimum length of our array will be 3
18:07so we will not face any issue.
18:09Binary search will apply anyway.
18:11So, in binary search,
18:13the values that we take for start and end
18:15are the range of our search space.
18:17But in the question,
18:19we are already given that
18:21these two values will never come in the search space.
18:23So, we have not taken them.
18:25So, the initialization of start and end
18:27that we have changed,
18:29our search space
18:31where our answer can lie
18:33will never have 0 or n-1.
18:35We can understand this by reading the question
18:37because our array is a mountain array
18:39in which starting and ending values
18:41can never be the answer.
18:43Second reason is that
18:45we don't have to do unnecessary checks
18:47for mid-1, mid-1.
18:49If we say that
18:51we will start our start
18:53and end from here
18:55and end from here.
18:57So, now our mid can be any of these values.
18:59And in worst case,
19:01in edge case scenario,
19:03if mid comes here,
19:05then also m-1 will exist.
19:07And if mid comes here,
19:09then m-1 will exist.
19:11So, we don't have to do any checks.
19:13All these conditions will always be valid.
19:15So, because of these two reasons,
19:17our initialization
19:19can be initialized from start and end.
19:21So, let's dry run this approach
19:23on the given code.
19:25We are going to start with some starting value
19:27and some ending value.
19:29So, we know that our start will start from here,
19:31from index 1.
19:33And our end will start from here,
19:35from index n-2.
19:37Our elements are already forming a mountain.
19:39This is 0.
19:41Here, 3 will come.
19:43Here, 8 will come.
19:45Here, 9 will come.
19:47This is going to be equal to 5 and 2.
19:49Our elements are forming a mountain-like structure
19:51where this is our peak.
19:54For these, our mid value
19:56will be this index.
19:58So, if mid is this index,
20:00first of all, we will check whether
20:02this is our peak element.
20:04It is bigger than left but not bigger than right.
20:06This is not the peak element.
20:08Then, we have to check whether we have to go
20:10to left or right.
20:12So, we will check whether we are in increasing slope
20:14or decreasing slope.
20:16How do we check increasing slope?
20:18Is our value bigger than previous value?
20:20So, yes, our value is bigger than previous value.
20:22Our mid value lies on the left slope
20:24and it lies here.
20:26So, the answer will always exist
20:28after mid.
20:30So, this time, we will search on the right side.
20:32Searching on the right side means
20:34that this time,
20:36our starting value will be mid plus 1
20:38and our search space
20:40will be reduced to this space.
20:42In this space,
20:44we will take out mid again.
20:46This time, our mid value will be this value.
20:48When we check for this,
20:50it is bigger than left but not bigger than right.
20:52So, this value is going to be the peak value.
20:54When we return this value,
20:56we find out our peak value.
20:58So, in this way,
21:00our modified binary search strategy will work
21:02for this particular question.
21:04Let's convert this question into code.
21:06Here, we can rename our arr array to a.
21:08First of all,
21:10we will take our starting value
21:12which is equal to 0.
21:14After that, we will take ending value
21:16which is going to be equal to a.size-1.
21:18Now, we have to run a loop
21:20till the time our starting value
21:22is less than or equal to end.
21:24First of all, we will take out our mid.
21:26Mid is going to be equal to start plus
21:28end minus start
21:30divided by 2.
21:32After that, we will check
21:34whether our mid is the answer.
21:36When will our mid be the answer?
21:38When array of mid minus 1
21:40will be less than array of mid
21:42and array of mid will be bigger
21:44than array of mid plus 1.
21:46In this case, value bigger than left
21:48and value bigger than right.
21:50So, here we will get our answer
21:52which is going to be equal to mid.
21:54Else if case will be
21:56in which we know that
21:58value of array of mid minus 1
22:00will be less than array of mid.
22:02In this case, we are on increasing slope.
22:04So, where do we have to go?
22:06Our answer will be in right.
22:08In right, we will redefine our start
22:10to mid plus 1.
22:12Else if case will be
22:14on right slope
22:16means we have to go to left.
22:18Going to left means
22:20our end will be
22:22going to be mid
22:24minus 1.
22:26And as soon as
22:28while loop will end,
22:30we can return minus 1.
22:32But this statement will never be executed
22:34because if any peak element exists
22:36then we will always find out
22:38that mid.
22:40In initialization, we will initialize
22:42end from minus 2.
22:44This is the optimization
22:46which we discussed.
22:48Because of this, we don't have to handle
22:50extra edge cases here.
22:52Let's run this code once.
22:54And let us submit it.
22:56Our code has been successfully submitted.
22:58And this is how we perform modified binary search
23:00to solve our question.
23:02In this whole code,
23:04in this whole approach,
23:06the time complexity that we find
23:08that is big of log n.
23:10Because in every iteration,
23:12we are taking decision
23:14whether to go right or left.
23:16So whenever the search space is half,
23:18our time complexity log n comes out.
23:20I hope we have understood
23:22this question well.
23:24If you have successfully completed today's lecture,
23:26then you can comment done or completed
23:28in the comment section.
23:30You can also let me know about your progress on Twitter.
23:32That's all for today. See you in the next video.
23:34Till then keep learning and keep exploring.