Coding Interview Question - Find Peak (LeetCode), two solutions

Let's solve a coding interview question "Find Peak Element" from LeetCode. Given an array of numbers, find an element greater than its both neighbours, in logarithmic time complexity. I will show you two solutions.

Subscribe for more videos and streams on algorithms and coding interviews!

I'm known as Errichto. I compete in and organize programming competitions. I'm a finalist of ACM-ICPC, Topcoder Open, Facebook Hacker Cup and Google Code Jam. I got a second place in Google Code Jam 2018. Watch me if you want to practice Competitive Programming, algorithms or you want to learn for a coding interview. I share my thought process, explain everything, and mention similar problems that I know or techniques/algorithms that could be used too. Learn from me and grow your rating on Codeforces!

[Errichto]

I've added the subtitles in this video! Turn them on in the bottom-right corner, or just hit 'C'. Enjoy! I'm slowly learning to edit stuff. I hope you liked the new format :)
If you want to skip some part:
9:39 Solution summary
11:32 Implementation
13:47 Alternative solution

[kaushalkumar-obmw]

Dude!! you are the awesome and best teacher I have got a chance to learn from. Thanks for ur keep up the good work

[purple_rabbit]

This question looks way too simple but the optimal answer is quite clever and tricky to understand good job young man for explaining the solution.

[william]

Thank you for this! I solved this one on myself but not quite sure about how to prove it, this explanation nailed it.

[muskansinghal]

Thanks for the graphical explanation, I was looking for proof why binary search works here, found this video at last . :)

[vivekpal]

R - (R - L) / 2 can also be used to round up the mid value.

[sangramjitchakraborty]

I came up with an almost similar solution myself. Instead of looking at the single left element like he did, I looked at both the left and the right elements and just returned the middle element as peak if I got both less than it. The edges of the array were handled by a couple special cases where if middle equaled end index then that's the peak, and same for the beginning.

[drishtdyumnshrivastava]

such a sweet guy....especially that latter part of channel KAWAIII

[AM-ivbp]

That was an amazing explanation, and an amazing solution. Thank you!

[anirudhthatipelli]

Thank you so much for explaining the problem!

[davithov]

You're awesome Errichto. How did you manage to be so strong by algorithms
? I can't even solve all medium problems in LeetCode, and when I see your 'Google code jam' videos I start to think to retire from programming. Can you give some advices how to improve algorithmic thinking?

[anirbanchakraborty]

Hi! this explanation is wonderful, can you just tell me, if in while loop, we used while(L<=R) instead of while(L<R), then can it be done ? if so then how? how do we know which one to choose?

[algorithmimplementer]

Wow - such a super hard problem with easy coding.

[MinhTran-wnri]

@11:26 What of the case where you subdivide the interval and the middle element is less than both left and right neighbor?

[cp-kbbo]

Thank you very much for the videos. They are very helpful!

[hangyin]

great explanation, thanks for the effort!

[zhenwang]

Can you please explain why left = right at the end, and we return left/right instead of the middle?

[varunnarayanan]

Well explained those dots are enough they leak the entire solution

[DiapaYY]

This problem as an interactive problem where have to find peak with fewer queries than the solution in this video :) There are also test groups for this problem with 2 and 3 dimensions.

[MrCrYMusic]

Can you suggest how to start to learn algorithms from a newbie, who was not so good in math?