Find minimum peak elements in an array

Question: Given an array numbers = {2, 7, 8, 5, 1, 6, 3, 9, 4}. Check the below conditions, both the conditions should be satisfied.

1. a[i] > a[i-1] or if first element a[i] > a[i+1]
2. a[i] > a[i+1] or if last element a[lastelement] > a[lastelement - 1]

Therefore:

• 1st Iteration - 8, 6, 9 are peak values. Remove the smallest ele. Remove 6. New arr {2, 7, 8, 5, 1, 3, 9, 4}. Output Arr - {6}

• 2nd Iteration - 8, 9 are peak values. Remove the smallest ele. Remove 8. New arr {2, 7, 5, 1, 3, 9, 4}. Output Arr - {6, 8}

• 3rd Iteration - 7, 9 are peak values. Remove the smallest ele. Remove 7. New arr {2, 5, 1, 3, 9, 4}. Output Arr - {6, 7, 8}

• 4th Iteration - 5, 9 are peak values. Remove the smallest ele. Remove 5. New arr {2, 1, 3, 9, 4}. Output Arr - {6, 7, 8, 5}

• 5th Iteration - 2, 9 are peak values. Remove the smallest ele. Remove 2. New arr {1, 3, 9, 4}. Output Arr - {6, 7, 8, 5, 2}

• 6th Iteration - 9 are peak values. Remove the smallest ele. Remove 9. New arr {1, 3, 4}. Output Arr - {6, 7, 8, 5, 2, 9}

• 7th Iteration - 4 are peak values. Remove the smallest ele. Remove 4. New arr {1, 3}. Output Arr - {6, 7, 8, 5, 2, 9, 4}

• 8th Iteration - 3 are peak values. Remove the smallest ele. Remove 3. New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3}

• 9th Iteration - 1 are peak values. Remove the smallest ele. Remove 1. New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}

Output: {6, 8, 7, 5, 2, 9, 4, 3, 1}

My solution is working but I am looking for optimized solution. Please let me know.

Here is my code:

public int[] findMinimumPeaks(int[] arr){
List<Integer> list1 = new ArrayList<Integer>(arr.length);
int[] output = new int[arr.length];
for(int i: arr)
list1.add(i);
for(int i =0; i<arr.length; i++){
int minIndex = minimumPeakElement(list1);
output[i] = list1.get(minIndex);
list1.remove(minIndex);
}
return output;
}
public int minimumPeakElement(List<Integer> list1){
int minIndex = 0, peakStart = Integer.MAX_VALUE, peakEnd = Integer.MAX_VALUE;
int peak = Integer.MAX_VALUE, minPeak = Integer.MAX_VALUE;
if(list1.size() >= 2){
if(list1.get(0) > list1.get(1)) peakStart = list1.get(0);
if(list1.get(list1.size() - 1) > list1.get(list1.size() - 2)) peakEnd = list1.get(list1.size() - 1);
if(peakStart < peakEnd){
minPeak = peakStart;
minIndex = 0;
}
else if(peakEnd < peakStart){
minPeak = peakEnd;
minIndex = list1.size() - 1;
}
}
for(int i=1; i<list1.size() - 1; i++){
if(list1.get(i) > list1.get(i + 1) && list1.get(i) > list1.get(i-1)) peak = list1.get(i);
if(peak < minPeak){
minPeak = peak;
minIndex = i;
} 
}
return minIndex;
}

Here is an idea how to optimize asymptotic complexity.

Use single pass over elements of your initial array to split it into "up-down" "slopes" or "hills", i.e. subsequence of elements in ascending order, followed by subsequence in descending order.

Store these slopes in the following datastructure:

val slopes = MinPriorityQueue<Slope>()
class Slope(
var first: Int, // first element of the slope
var last: Int,   // last element of the slope
var peak: Int,   // max or peak element
var els: MaxPriorityQueue<Int>(),  // all elements of the slope
var prev: Slope?,    // link to the previous slope in the list or null if first
var next: Slope?     // link to the next slope in the list or null if last
)

Slopes should be comparable by their peak value.

Now, having this data structure, you can poll the slope that has minimal peak value in O(log(N)). After you polled the slope, you should update the slope by removing it's peak element (i.e. poll els, then update first, last, peak), also, slope might become eligible to be merged with the previous or next slope:

Admittedly, this solution is not an easy one, having a lot of things to maintain and large number of corner cases. However, it's much better in terms of asymptotic complexity.

• Initial data structure build: O(n log(n))
• Polling elements while maintaining slopes: O(n log (n))
• Overall complexity: O(n log(n))

Notes:

1. One of the corner cases, if array can have duplicate elements, then inner priority queue (els) becomes MaxPriorityQueue<Pair<Int,Int>>, i.e. you need to store the number of potentially duplicate elements along with the element value.

2. MinPriorityQueue and MaxPriorityQueue is an abstract heap-based data structure with min and max element at the head respectively. Can be implemented with PriorityQueue in java