4
\$\begingroup\$

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

```
\$\endgroup\$
1
  • 3
    \$\begingroup\$ That definition looks wrong. Is the original online somewhere? \$\endgroup\$ Aug 27 '20 at 18:46
9
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ I'd be interested in how you'd avoid the still remaining quadratic runtime. \$\endgroup\$ Aug 27 '20 at 21:32
  • \$\begingroup\$ @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? \$\endgroup\$
    – vnp
    Aug 27 '20 at 21:44
  • 1
    \$\begingroup\$ Yes, the removal time is what I meant. Linked list sounds good. \$\endgroup\$ Aug 27 '20 at 21:48
  • \$\begingroup\$ Just saw your edit. Nice observation. So except for sorting initial peaks, this could be done in linear time, I guess? \$\endgroup\$ Aug 27 '20 at 22:10
  • \$\begingroup\$ @superbrain Correct. \$\endgroup\$
    – vnp
    Aug 27 '20 at 22:12
4
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.