162. Find Peak Element - Explanation

Problem Link

Description

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

You are 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,4,5,0]

Output: 5

Explanation: 5 is a peak element and your function should return the index number 5.

Constraints:

  • 1 <= nums.length <= 1000.
  • -(2^31) <= nums[i] <= ((2^31)-1)
  • nums[i] != nums[i + 1] for all valid i.

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i

        return len(nums) - 1

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + (r - l) // 2
            if m > 0 and nums[m] < nums[m - 1]:
                r = m - 1
            elif m < len(nums) - 1 and nums[m] < nums[m + 1]:
                l = m + 1
            else:
                return m

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1)
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        def binary_search(l, r):
            if l == r:
                return l
            m = l + (r - l) // 2
            if nums[m] > nums[m + 1]:
                return binary_search(l, m)
            return binary_search(m + 1, r)

        return binary_search(0, len(nums) - 1)

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(log⁡n)O(\log n) for recursion stack.

4. Binary Search (Optimal)

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) >> 1
            if nums[m] > nums[m + 1]:
                r = m
            else:
                l = m + 1

        return l

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n)
  • Space complexity: O(1)O(1)