← Create New Paste

Find Peak Element (LeetCode 162): Binary Search Without a Sorted Array

7 views
A peak element is strictly greater than its neighbors. Given an array where nums[i] != nums[i + 1], return the index of any peak in O(log n) time. Treat positions outside the array as negative infinity. For [1, 2, 3, 1] the answer is 2; for [1, 2, 1, 3, 5, 6, 4] either 1 or 5 is correct. Why it is a good interview question Most candidates learn binary search on sorted arrays. This problem asks you to see that binary search really needs only a rule that tells you which half still contains an answer. Explaining that rule clearly matters more than the code. The linear baseline Scan once and return the first i where nums[i] > nums[i + 1]. It is O(n) and correct, and it is worth mentioning first so the interviewer knows you have a working answer before you optimize. The key insight Look at the middle element and its right neighbor. - If nums[mid] < nums[mid + 1], you are on an upward slope. Moving right, the values either keep rising until the end (and the last element is a peak, because the outside value is negative infinity) or they drop at some point (and that turning point is a peak). Either way, a peak exists to the right. - Otherwise nums[mid] > nums[mid + 1], so a peak exists at mid or to its left by the same argument. def find_peak_element(nums): lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] < nums[mid + 1]: lo = mid + 1 else: hi = mid return lo The loop runs while lo < hi, so mid + 1 is always in range. When the loop ends, lo == hi points at a peak. Time O(log n), space O(1). Edge cases worth saying - A single element is a peak. - A strictly increasing array returns the last index; a strictly decreasing one returns 0. - If equal neighbors were allowed, the slope argument breaks and the worst case becomes O(n). Mentioning this shows you understand why the constraint exists. Follow-ups - Find a peak in a 2D grid (LeetCode 1901): binary search over columns, taking the maximum of each column, for O(m log n). - Peak index in a mountain array (LeetCode 852): the same code works, with a guaranteed single peak. - Minimum in a rotated sorted array uses a similar "which half is safe" argument. How to present it Give the linear solution, state the slope argument in one or two sentences, write the loop, and trace [1, 2, 1, 3, 5, 6, 4]. If nerves make you mix up lo < hi and lo <= hi, Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly reminding you of details like loop bounds while you explain the idea in your own words.
Created Nov 17, 2026 20:35 Expires Nov 17, 2027 20:35