How to Solve: Peak Element in an Array

How to Solve: Peak Element in an Array

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll prove you can optimize brute-force solutions into logarithmic time while handling edge cases like a pro."

? WHAT YOU NEED TO KNOW FIRST

Before tackling peak elements, ensure you understand: 1. Binary Search – How to modify it for non-sorted arrays. 2. Array Traversal – Linear vs. logarithmic time complexity. 3. Edge Cases – Handling single-element arrays, plateaus, and boundaries.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every peak element problem.)

1. Clarify the Problem
2. Ask: "Is the array guaranteed to have at least one peak?"
3. Ask: "Can the peak be at the boundaries (first/last element)?"

4. Ask: "Are duplicates allowed?"

5. Choose the Right Approach

6. If O(n) is acceptable → Linear Scan (simple, but not optimal).

7. If O(log n) is required → Modified Binary Search (interviewers expect this).

8. Implement Binary Search (Modified)

9. Initialize left = 0, right = len(nums) - 1.
10. While left < right:
    • Compute mid = left + (right - left) // 2.
    • If nums[mid] < nums[mid + 1] → Peak must be on the right (left = mid + 1).
    • Else → Peak is on the left (or at mid) (right = mid).

11. Return left (or right, since they converge).

12. Handle Edge Cases

13. Single-element array? → Return 0.
14. All elements equal? → Any index is a peak.

15. Plateaus? → Move right until a higher neighbor is found.

16. Verify with Examples

17. Test with [1, 2, 3, 1] → Peak at 2.
18. Test with [1, 2, 1, 2, 1] → Peak at 1 or 3.

19. Test with [1] → Peak at 0.

20. Analyze Time & Space Complexity

21. Binary Search: O(log n) time, O(1) space.
22. Linear Scan: O(n) time, O(1) space.

? WORKED EXAMPLES

Example 1 – Basic (Single Peak)

Problem: Find a peak element in an array where nums[i] ≠ nums[i+1] for all i. Input: [1, 2, 3, 1] Output: 2 (index of 3)

Thought Process

1. Clarify: Only one peak exists, no duplicates.
2. Approach: Binary search (O(log n)).
3. Implementation:
   python
def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
4. Why This Works:
5. If nums[mid] < nums[mid+1], the peak must be on the right (since the array increases).
6. Otherwise, the peak is on the left (or at mid).

Time Complexity: O(log n) Space Complexity: O(1)

Example 2 – Medium (Plateaus & Duplicates)

Problem: Find any peak element (array may have duplicates). Input: [1, 2, 2, 3, 1] Output: 3 (index of 3)

Thought Process

1. Clarify: Duplicates allowed, multiple peaks possible.
2. Approach: Modified binary search (handle plateaus).
3. Implementation:
   python
def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
elif nums[mid] > nums[mid + 1]:
right = mid
else: # nums[mid] == nums[mid + 1] (plateau)
# Move right until a higher neighbor is found
temp = mid + 1
while temp < right and nums[temp] == nums[mid]:
temp += 1
if nums[temp] > nums[mid]:
left = temp
else:
right = mid
return left
4. Why This Works:
5. If nums[mid] == nums[mid+1], we skip duplicates until we find a higher neighbor.
6. Ensures we don’t get stuck in a plateau.

Time Complexity: O(log n) (worst case O(n) if all elements are equal). Space Complexity: O(1)

Example 3 – Hard (Follow-Up: 2D Peak)

Problem: Find a peak in a 2D matrix (a cell greater than its 4 neighbors). Input:

[
  [10, 20, 15],
  [21, 30, 14],
  [ 7, 16, 32]
]

Output: 30 (or 32)

Thought Process

1. Clarify: Must be strictly greater than all 4 neighbors.
2. Approach: Binary search on columns, then linear search in the row.
3. Implementation:
   python
def findPeakGrid(mat):
rows, cols = len(mat), len(mat[0])
left, right = 0, cols - 1
while left <= right:
mid_col = left + (right - left) // 2
max_row = 0
# Find the max element in the current column
for i in range(rows):
if mat[i][mid_col] > mat[max_row][mid_col]:
max_row = i
# Check left and right neighbors
left_neighbor = mat[max_row][mid_col - 1] if mid_col > 0 else -1
right_neighbor = mat[max_row][mid_col + 1] if mid_col < cols - 1 else -1
if mat[max_row][mid_col] > left_neighbor and mat[max_row][mid_col] > right_neighbor:
return [max_row, mid_col]
elif left_neighbor > mat[max_row][mid_col]:
right = mid_col - 1
else:
left = mid_col + 1
return [-1, -1]
4. Why This Works:
5. Binary search on columns reduces the problem to O(log cols).
6. For each column, we find the max row (O(rows)).
7. Total complexity: O(rows log cols).

Time Complexity: O(rows log cols) Space Complexity: O(1)

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Here’s your 30-second peak-finding checklist before walking into that interview:

1. Clarify: Is the array guaranteed to have a peak? Can it be at the boundaries?
2. Choose: Binary search (O(log n)) or linear scan (O(n))? Always pick binary search unless the array is tiny.
3. Implement:
4. Set left = 0, right = len(nums) - 1.
5. While left < right, compute mid.
6. If nums[mid] < nums[mid+1], move left = mid + 1.
7. Else, move right = mid.
8. Edge Cases: Single element? Duplicates? Plateaus? Handle them explicitly.
9. Test: Run through [1, 2, 3, 1] and [1, 2, 2, 1] to confirm.

Remember: Binary search isn’t just for sorted arrays. It works here because the peak creates a monotonic property—use it to your advantage. Now go crush that interview!

? Final Notes

• Practice Variations:
• LeetCode 162 (Find Peak Element)
• LeetCode 1901 (Find a Peak Element II)
• Follow-Up Questions to Expect:
• "What if the array is circular?" → Use binary search with wrap-around checks.
• "Can you do it in O(1) space?" → Yes, iterative binary search.
• "What if the array is infinite?" → Use exponential search to find bounds first.

You’ve got this. Now go solve it like a FAANG engineer. ?