find_peak_element
1# @leet start 2class Solution: 3 def findPeakElement(self, nums: list[int]) -> int: 4 """ 5 This question asks us to find an element that is strictly greater than 6 its neighbors, so `nums[i - 1] < nums[i] > nums[i + 1]`. 7 8 There are three possible cases, where nums is sorted in ascending order, 9 descending order, or the peak is somewhere in the middle. 10 11 In the ascending case, we want to return the last element. 12 In the descending case, we want to return the first element. 13 In the case where the peak is in the middle, we want to return the case 14 where nums[i] > nums[i + 1], for all the items in the array. We know 15 this works, because if the previous item fit this criteria, it would be 16 greater than its previous number (through induction) and also greater 17 than its next number, so it fits the criteria. 18 19 We can do a linear scan where we zip through the numbers and do this. 20 21 However, we can do this in $O(log\{n})$ time as well. We can apply the 22 same rule to find the peak element. We do binary search as usual, but 23 the criteria becomes checking if the current mid is greater than the 24 next item. If this is the case, we set the right pointer to mid, since 25 it is the last possible peak element, and we don't need to look at all 26 items after mid. 27 28 In the other case, we set l to mid + 1, because this item isn't a peak 29 element, and all items to the left are discarded. 30 """ 31 l, r = 0, len(nums) - 1 32 while l < r: 33 mid = (l + r) // 2 34 if nums[mid] > nums[mid + 1]: 35 r = mid 36 else: 37 l = mid + 1 38 return l 39 40 41# @leet end 42 43 44def test(): 45 assert 2 + 2 == 4
3class Solution: 4 def findPeakElement(self, nums: list[int]) -> int: 5 """ 6 This question asks us to find an element that is strictly greater than 7 its neighbors, so `nums[i - 1] < nums[i] > nums[i + 1]`. 8 9 There are three possible cases, where nums is sorted in ascending order, 10 descending order, or the peak is somewhere in the middle. 11 12 In the ascending case, we want to return the last element. 13 In the descending case, we want to return the first element. 14 In the case where the peak is in the middle, we want to return the case 15 where nums[i] > nums[i + 1], for all the items in the array. We know 16 this works, because if the previous item fit this criteria, it would be 17 greater than its previous number (through induction) and also greater 18 than its next number, so it fits the criteria. 19 20 We can do a linear scan where we zip through the numbers and do this. 21 22 However, we can do this in $O(log\{n})$ time as well. We can apply the 23 same rule to find the peak element. We do binary search as usual, but 24 the criteria becomes checking if the current mid is greater than the 25 next item. If this is the case, we set the right pointer to mid, since 26 it is the last possible peak element, and we don't need to look at all 27 items after mid. 28 29 In the other case, we set l to mid + 1, because this item isn't a peak 30 element, and all items to the left are discarded. 31 """ 32 l, r = 0, len(nums) - 1 33 while l < r: 34 mid = (l + r) // 2 35 if nums[mid] > nums[mid + 1]: 36 r = mid 37 else: 38 l = mid + 1 39 return l
4 def findPeakElement(self, nums: list[int]) -> int: 5 """ 6 This question asks us to find an element that is strictly greater than 7 its neighbors, so `nums[i - 1] < nums[i] > nums[i + 1]`. 8 9 There are three possible cases, where nums is sorted in ascending order, 10 descending order, or the peak is somewhere in the middle. 11 12 In the ascending case, we want to return the last element. 13 In the descending case, we want to return the first element. 14 In the case where the peak is in the middle, we want to return the case 15 where nums[i] > nums[i + 1], for all the items in the array. We know 16 this works, because if the previous item fit this criteria, it would be 17 greater than its previous number (through induction) and also greater 18 than its next number, so it fits the criteria. 19 20 We can do a linear scan where we zip through the numbers and do this. 21 22 However, we can do this in $O(log\{n})$ time as well. We can apply the 23 same rule to find the peak element. We do binary search as usual, but 24 the criteria becomes checking if the current mid is greater than the 25 next item. If this is the case, we set the right pointer to mid, since 26 it is the last possible peak element, and we don't need to look at all 27 items after mid. 28 29 In the other case, we set l to mid + 1, because this item isn't a peak 30 element, and all items to the left are discarded. 31 """ 32 l, r = 0, len(nums) - 1 33 while l < r: 34 mid = (l + r) // 2 35 if nums[mid] > nums[mid + 1]: 36 r = mid 37 else: 38 l = mid + 1 39 return l
This question asks us to find an element that is strictly greater than
its neighbors, so nums[i - 1] < nums[i] > nums[i + 1].
There are three possible cases, where nums is sorted in ascending order, descending order, or the peak is somewhere in the middle.
In the ascending case, we want to return the last element. In the descending case, we want to return the first element. In the case where the peak is in the middle, we want to return the case where nums[i] > nums[i + 1], for all the items in the array. We know this works, because if the previous item fit this criteria, it would be greater than its previous number (through induction) and also greater than its next number, so it fits the criteria.
We can do a linear scan where we zip through the numbers and do this.
However, we can do this in $O(log{n})$ time as well. We can apply the same rule to find the peak element. We do binary search as usual, but the criteria becomes checking if the current mid is greater than the next item. If this is the case, we set the right pointer to mid, since it is the last possible peak element, and we don't need to look at all items after mid.
In the other case, we set l to mid + 1, because this item isn't a peak element, and all items to the left are discarded.