Problem of The Day: Find Peak Element
Problem Statement
Intuition
The problem at hand is to find a peak element in an array. A peak element is an element that is strictly greater than its neighbors. The intuition behind solving this problem is to use a modified binary search, as this will allow us to find the peak element efficiently without needing to check every element in the array.
Approach
The approach used here is a recursive binary search. We define a helper function dfs
(depth-first search) that takes in the array and two pointers, l
and r
, representing the current search range. The middle element of the range is calculated and compared with its neighboring elements to check if it is a peak element.
- Middle Element Check: If the middle element is greater than both of its neighbors, it is a peak element, and we return its index.
- Divide and Conquer: If the middle element is not a peak, we recursively search both the left and right halves of the array to find the peak element, and then return the maximum result of these two searches.
- Base Case: If
l
exceedsr
, it means there are no peak elements in the current range, and we return-1
.
This recursive strategy helps reduce the problem size by half in each step, leading to an efficient solution.
Complexity
-
Time complexity:
- The time complexity of this approach is \(O(\log n)\). This is because in each recursive call, we are halving the search space, similar to binary search.
-
Space complexity:
- The space complexity is \(O(\log n)\) due to the recursive function calls stacking up in the call stack for each half of the array.
Code
class Solution:
def dfs(self, nums, l, r):
while l <= r:
m = l + (r - l) // 2
left_val = nums[m - 1] if m - 1 >= 0 else float('-inf')
right_val = nums[m + 1] if m + 1 < len(nums) else float('-inf')
if nums[m] > left_val and nums[m] > right_val:
return m
else:
L = self.dfs(nums, l, m - 1)
R = self.dfs(nums, m + 1, r)
return max(L, R)
return -1
def findPeakElement(self, nums: List[int]) -> int:
return self.dfs(nums, 0, len(nums) - 1)
Editorial
Approach 2: Recursive Binary Search
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return self.search(nums, 0, len(nums) - 1)
def search(self, nums: List[int], l: int, r: int) -> int:
if l == r:
return l
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
return self.search(nums, l, mid)
return self.search(nums, mid + 1, r)
- time: O(log n)
- space: O(log n)
Approach 3: Iterative Binary Search
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
r = mid
else:
l = mid + 1
return l
- time: O(log n)
- space: O(1)