For an array with single peak element, it could be done in o(logn) using binary search, however in case of multiple peak elements in an array what approach should we use ?
---Putting some more information ---- A peak element is something which is greater then it's neighbors for instance, look at the below array,
[1,3,20,4,1,0,7,5,2]
there are 2 peaks in it, 20 and 7.
We need to design an algorithm to find the peak elements in this array.
I might have not understand your question since, finding single peak can be done in O(logn) requires array to be sorted at first place.
I would advise you to store a difference array which will generate an output like: [1,3,20,4,1,0,7,5,2] => [1, 1,-1,-1,-1, 1,-1,-1] which is simply generate an array of size n - 1 and place the direction of increase in the array. This can be done in O(n) single pass.
In the second pass you will look for [1, -1] pairs this is the place where peak occurs.
If you want to find peaks in the start and end you need to check if start is -1, and end is 1.
Hope this helps.
I recently faced the similar problem on a programming website but there was another important constraint other than finding peaks. Firstly, there can be multiple peaks, but there can also be plateaus! A plateau is something that occurs in an arr: [1,2,2,2,1] and in this case we have to return the peak to be 2. In the problem we are also asked to return the first position where the peak occurs, so in this case it will be position = 1. The only case, that we have to remain careful about is that in arr: [1,2,2,2,3,4,5,1], there is peak with 5 in the second last position but there is no plateau even if there is a series of duplicates which look like a plateau in the first glance.
So the basic algorithm that I thought about was using a difference array as already suggested using {1,0,-1} where we use 0 when we get a series of duplicates in a continuous stream. Whenever we get a 0 while checking the difference array, we start looking for the first non zero entry, whether it is 1 or -1 and output accordingly. But again we have to remain careful that may be the Difference array looks like Diff = [-1,1,-1,1,0,0,0], in which case there is no plateau and only one peak. The python code looks like the following, when arr is given as input:
n = len(arr)
if arr == []:
return {"pos":[],"peaks":[]}
Diff = []
for i in range(0,n-1):
if arr[i]< arr[i+1]:
Diff.append(1)
elif arr[i] == arr[i+1]:
Diff.append(0)
if arr[i] > arr[i+1]:
Diff.append(-1)
pos = []
peaks = []
j = 0
for i in range(0,n-2):
if Diff[i] == 1 and Diff[i+1] == -1:
pos.append(i+1)
peaks.append(arr[i+1])
if Diff[i] == 1 and Diff[i+1] == 0:
if Diff[i+1:] == [Diff[i+1]]:
break
j = i+1
while(Diff[j] == 0 and j < n-2):
j = j+1
if Diff[j] == -1:
pos.append(i+1)
peaks.append(arr[i+1])
return {"pos":pos, "peaks":peaks}
For finding all the peak elements when having multiple peaks.
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + right >> 1
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
int arr[] = {50, 12, 13, 20, 16, 19, 11, 7, 24};
int size = sizeof(arr) / sizeof(arr[0]);
int peak_arr[size / 2];
int i, j, k = 0;
int next, previous = 0;
for(i = 0; i < size; i++){
if(i + 1 == size){
next = 0;
}
else{
next = arr[i + 1];
}
if(arr[i] > next && arr[i] >= previous){
peak_arr[k++] = arr[i];
}
previous = arr[i];
}
Finding multiple peak elemets using a recursive approach.
def Div(lst, low, high):
mid = (low + high)//2
if low > high:
return ""
else:
if mid+1 < len(lst) and lst[mid] > lst[mid+1] and lst[mid] > lst[mid -1]:
return str(lst[mid]) + " " + Div(lst, low, mid-1) + Div(lst, mid+1, high)
else:
return Div(lst, low, mid-1) + Div(lst, mid + 1, high)
def peak(lst):
if lst == []:
return "list is empty"
elif len(lst) in [1, 2]:
return "No peak"
else:
return Div(lst, 0, len(lst))
print(peak([0, 5, 2, 9, 1, 10, 1]))
The idea is to use modified binary search.
If arr[mid+1]>arr[mid] then your peak ALWAYS exists on the right half.
If arr[mid-1]>arr[mid] then your peak ALWAYS exists on the left half.
Because arr[i+1] have only two options, either bigger than arr[i] or smaller than arr[i-1]
I don't have java implementation but here is a python implementation.
def FindAPeak(arr, i, j):
mid = (i+j)/2
# if mid element is peak
if (mid == len(arr)-1 or arr[mid] > arr[mid+1]) and (mid == 0 or arr[mid] > arr[mid-1]):
return arr[mid]
# when your peak exists in the right half
if arr[mid] < arr[mid+1] and mid+1 < len(arr):
return FindAPeak(arr, mid+1, j)
# when your peak exists in the left half
else:
return FindAPeak(arr, i, mid-1)
In [31]: arr = [1,2,3,2,1]
...: FindAPeak(arr, 0, len(arr)-1)
...:
Out[31]: 3
In [32]:
...: arr = [1,2,3,4,5,6]
...: FindAPeak(arr, 0, len(arr)-1)
...:
Out[32]: 6
© 2022 - 2024 — McMap. All rights reserved.
0 0 0 42 0 0 0 0 0 0 0your strategy fails and there is no constraint that elements can't be equal (even example in your post has two1s). – Sulfa