How to find peak elements in an array when there are multiple peaks?

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