Scale Engineer

Find Peak Element

Med
#0162Time: O(n)Space: O(1)18 companies
Algorithms
Binary Search
Data structures
Array
Companies
AccentureFlipkartGoldman SachsNvidia

Prompt

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

 

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a simple linear scan through the array. We iterate over each element and check if it satisfies the condition of being a peak: being strictly greater than its adjacent neighbors. Special care is taken for the first and last elements of the array, as they only have one neighbor to compare against.

Algorithm

  • Handle the edge case where the array has only one element by returning index 0.
  • Check if the first element nums[0] is a peak. This is true if nums[0] > nums[1]. If so, return 0.
  • Check if the last element nums[n-1] is a peak. This is true if nums[n-1] > nums[n-2]. If so, return n-1.
  • Iterate through the rest of the array from index i = 1 to n-2.
  • For each element nums[i], check if it is strictly greater than both its left neighbor nums[i-1] and its right neighbor nums[i+1].
  • If the condition nums[i] > nums[i-1] && nums[i] > nums[i+1] is met, nums[i] is a peak. Return its index i.
  • Since the problem guarantees a peak exists, the function will always return an index from one of these checks.

Walkthrough

The brute-force method is to iterate through the nums array and check each element to see if it's a peak. The problem statement implies that nums[-1] and nums[n] are negative infinity, which simplifies the logic for the boundary elements.

  1. Single Element Array: If the array contains only one element, that element is a peak by definition. We return index 0.
  2. First Element: We check if nums[0] is greater than nums[1]. If it is, nums[0] is a peak.
  3. Last Element: We check if nums[n-1] is greater than nums[n-2]. If it is, nums[n-1] is a peak.
  4. Middle Elements: We loop from the second element to the second-to-last element. For each element nums[i], we check if it's greater than both nums[i-1] and nums[i+1].

Since the problem guarantees that a peak always exists, this scan will find and return the index of one of the peaks.

class Solution {    public int findPeakElement(int[] nums) {        int n = nums.length;        if (n == 1) {            return 0;        }        // Check if the first element is a peak        if (nums[0] > nums[1]) {            return 0;        }        // Check if the last element is a peak        if (nums[n - 1] > nums[n - 2]) {            return n - 1;        }        // Check the elements in the middle        for (int i = 1; i < n - 1; i++) {            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {                return i;            }        }        return -1; // This line is unreachable given the problem constraints    }}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

  • The logic is straightforward and easy to understand.

  • It's simple to implement.

Cons

  • The time complexity of O(n) does not meet the problem's requirement of an O(log n) solution.

  • It is inefficient for large input arrays as it may need to scan the entire array in the worst-case scenario (e.g., a sorted array where the peak is the last element).

Solutions

class Solution { public int findPeakElement ( int [] nums ) { int left = 0 , right = nums . length - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( nums [ mid ] > nums [ mid + 1 ]) { right = mid ; } else { left = mid + 1 ; } } return left ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem