Find minimum peak elements in an array

Question

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

\begin{gather} \text{If }a[i] > a[i-1]\text{ or if first element }a[i] > a[i+1] \end{gather}

\begin{gather} \text{If }a[i] > a[i+1]\text{ or if last element }a[LastIndex] > a[LastIndex - 1] \end{gather}

• 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;
 }
```

• superb rain: That definition looks wrong. Is the original online somewhere?

Answer 1

Thou shalt not bruteforce.

Your algorithm exhibits a quadratic time complexity, and cannot be salvaged. You need a better one.

First observation you should make is that when you remove the peak, other peaks stay put. That alone is enough to see that rescanning the entire array is a waste of time.

More important observation is that once you remove the peak, the new peak may appear only in the position immediately adjacent to the peak being removed. Please prove this fact (or at least convince yourself that it is so). Also notice that the newborn peak would in general be smaller than the existing peaks, if any.

I hope it is enough to get you going.

---

As for the proper review:

• Flat is better than nested. The condition list1.size() >= 2 better be reversed:

   if (list1.size() < 2) {
   // The list consists of a single element, which is a peak,
   // and it resides at index 0
   return 0;
   }
   // Proceed with a general case here
   ....
  

• list1 looks like a strange name. There are no other lists, are there?

• superb rain: I'd be interested in how you'd avoid the still remaining quadratic runtime.
• vnp: @superbrain Why quadratic? I do not take the array as a requirement. If it is initially in the array, copy it (in linear time) into the linked list. Or am I not seeing something important?
• superb rain: Yes, the removal time is what I meant. Linked list sounds good.
• superb rain: Just saw your edit. Nice observation. So except for sorting initial peaks, this could be done in linear time, I guess?
• vnp: @superbrain Correct.

Answer 2

I have some suggestions for your code.

Always add curly braces to loop & if

In my opinion, it's a bad practice to have a block of code not surrounded by curly braces; I saw so many bugs in my career related to that, if you forget to add the braces when adding code, you break the logic / semantic of the code.

Extract the expression to variables when used multiple times.

In your code, you can extract the similar expressions into variables; this will make the code shorter and easier to read. (java.util.List#size, java.util.List#get, ect)