Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Meta SWE coding round, one problem the whole time. A binary search variant that looks deceptively familiar if you've done LC 162, but flipped to find a valley instead of a peak. Felt okay about it but I'm never fully sure with Meta.

Questions Asked (1)

Given an integer array, find any index where the element is strictly less than both its neighbors (a local minimum / valley). Treat out-of-bounds neighbors as positive infinity. Solve it in O(log n) using binary search.

Algorithms & Data Structures

Author's notes

I recognized the peak-finding pattern pretty fast, which was both helpful and a little dangerous.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search to find a local minimum by comparing the middle element with its neighbors. If the middle is greater than its left neighbor, a local minimum must exist on the left; otherwise, it exists on the right. This works because the array boundaries are treated as positive infinity, guaranteeing at least one local minimum.

Pro tip: Explicitly state that the algorithm relies on the fact that a local minimum is guaranteed to exist due to the infinite boundaries, and that the binary search effectively follows the 'downhill' direction. This shows deep understanding of the invariant and avoids off-by-one errors.

1. Clarify problem and constraints

Confirm that the array is non-empty, elements are integers, and out-of-bounds neighbors are positive infinity. Restate that we need any local minimum index in O(log n) time.

2. Define binary search invariant

Maintain that a local minimum exists within the current search range [low, high]. Initially, the whole array is the range, and the invariant holds because the boundaries are positive infinity.

3. Compare mid with neighbors

Compute mid = (low + high) // 2. Compare nums[mid] with nums[mid-1] (or +inf if mid=0) and nums[mid+1] (or +inf if mid=n-1). If nums[mid] is smaller than both, return mid.

4. Move towards the smaller neighbor

If nums[mid] > nums[mid-1], then a local minimum must exist in the left half, so set high = mid - 1. Otherwise, nums[mid] > nums[mid+1], so set low = mid + 1. This maintains the invariant.

5. Conclude and analyze complexity

When low > high, the search ends, but the invariant guarantees we would have found a local minimum before that. The algorithm runs in O(log n) time and O(1) space.

Key Points to Mention

Binary search is applicable because the problem has a monotonic property: if a position is not a local minimum, at least one side must contain a local minimum.
Handling boundaries: treat out-of-bounds as positive infinity, which ensures the array always has at least one local minimum.
The comparison logic: if nums[mid] > nums[mid-1], go left; else if nums[mid] > nums[mid+1], go right; else return mid.
Time complexity O(log n) and space complexity O(1).
Edge cases: array of size 1 (return 0), size 2 (return index of smaller element), and arrays with multiple local minima (any is acceptable).
Proof of correctness: by induction, the search range always contains a local minimum, and the range halves each step.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.