← Meta Interview InsightsSoftware Engineer
I started with the linear scan and they let me finish before asking if I could do better.
Use a binary search approach by examining the middle element and comparing it to its neighbors to determine which half of the array is guaranteed to contain a peak. Since no two adjacent elements are equal, you can always eliminate half the search space by moving toward the side with the larger neighbor. This guarantees O(log n) time complexity while leveraging the mathematical guarantee that a peak must exist in the chosen half.
Pro tip: Explicitly state the key invariant that makes binary search valid here: if nums[mid] < nums[mid+1], the right half must contain a peak because the sequence must eventually turn downward before the boundary (treated as -infinity). Articulating this invariant shows deep understanding beyond just memorizing the algorithm.
Confirm that 'any' peak is acceptable (not necessarily the global maximum) and that boundaries are treated as negative infinity. Ask about edge cases like a single-element array, which is trivially a peak.
Articulate the core invariant: if the middle element is smaller than its right neighbor, a peak must exist in the right half because the values must eventually decrease before hitting the -infinity boundary. This logical guarantee is what makes binary search applicable to a non-sorted array.
Set lo=0 and hi=n-1, then in each iteration check if nums[mid] > nums[mid+1]; if so, search left (hi=mid), otherwise search right (lo=mid+1). Continue until lo==hi, which is the peak index.
Verify your solution handles single-element arrays, peaks at the first or last index, and strictly monotonic arrays (where the peak is at one of the ends). Trace through at least one example to validate correctness.
Confirm O(log n) time and O(1) space complexity. Optionally mention the follow-up variant (LC 1901) for finding a peak in a 2D matrix, which demonstrates awareness of how the concept scales.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.