Tag
: Binary Search
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 validi
.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
peak = ans = -math.inf
for idx, num in enumerate(nums):
if peak < num:
peak = num
ans = idx
return ans
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return nums.index(max(nums))
- Time complexity: O(log(n))
- Space complexity: O(1)
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mi = lo + (hi - lo) // 2
if nums[mi] > nums[mi + 1]:
hi = mi
else:
lo = mi + 1
return lo
- Time complexity: O(log(n))
- Space complexity: O(log(n))
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
def binary_search(lo, hi):
# Base case
if lo == hi:
return lo
mi = lo + (hi - lo) // 2
if nums[mi] < nums[mi + 1]:
return binary_search(mi + 1, hi)
else:
return binary_search(lo, mi)
return binary_search(0, len(nums) - 1)
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
lo, hi = 0, n - 1
while lo + 1 < hi:
mi = lo + (hi - lo) // 2
# Found a peak
if nums[mi] > nums[mi + 1] and nums[mi] > nums[mi - 1]:
return mi
# Otherwise, if not a peak, climb up to the higher side
elif nums[mi] < nums[mi + 1]:
lo = mi
else:
hi = mi
return hi if nums[hi] > nums[lo] else lo