/
Problem4_Find_Peak_Element.py
46 lines (36 loc) · 1.27 KB
/
Problem4_Find_Peak_Element.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""
UCLA ACM ICPC: Interview Track Leetcode Problem Solutions
Disclaimer: This is not the only valid solution and we do not claim our solutions
to be optimal in terms of runtime or memory usage, we are merely giving example
solutions to questions for learning purposes only
Find Peak Element
Leetcode Problem 162
https://leetcode.com/problems/find-peak-element/
"""
"""
Time Complexity: O(NlogN)
Space Complexity: O(1)
"""
class Solution:
def findPeakElement(self,nums):
# Python uses a version of MergeSort to sort, so the sort has O(NlogN)
# this finds the value of the peak value as the end of the sorted array
peakVal = sorted(nums)[len(nums) - 1]
# return the index of this maximum value
for i in range(len(nums)):
if nums[i] == peakVal:
return i
"""
Time Complexity: O(N)
Space Complexity: O(1)
"""
class Solution:
def findPeakElement(self,nums):
peak = -sys.maxsize - 1 # minimum possible integer
# find the index of the maximum value in the array in O(N)
for i in range(len(nums)):
if nums[i] > peak:
peak = nums[i]
index = i
# return the location of this index
return index