aboutsummaryrefslogtreecommitdiff
path: root/find_peak_element.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_peak_element.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_peak_element.py')
-rw-r--r--find_peak_element.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/find_peak_element.py b/find_peak_element.py
new file mode 100644
index 0000000..18ef2f9
--- /dev/null
+++ b/find_peak_element.py
@@ -0,0 +1,34 @@
+# 162. Find Peak Element
+
+"""
+a peak element is an element that is strictly greater than its neighbours.
+given a 0 indexed 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] = -inf' in other words, an element is
+always considered to be strictly greater than a neighbour that is outside the
+array. you must write an algorithm that runs in 'O(log n)' time.
+"""
+
+
+class Solution(object):
+ def findPeakElement(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ left, right = 0, len(nums) - 1
+ while left < right - 1:
+ mid = (left + right) / 2
+ if nums[mid] > nums[mid + 1] and nums[mid] > nums[mid - 1]:
+ return mid
+ if nums[mid] < nums[mid + 1]:
+ left = mid + 1
+ else:
+ right = mid - 1
+ return left if nums[left] >= nums[right] else right
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findPeakElement(nums=[1, 2, 3, 1]))
+ print(obj.findPeakElement(nums=[1, 2, 1, 3, 5, 6, 4]))