Second highest element

Question

To find the second highest element of an array, is it better to sort the entire array (bubble sort) and then print the second highest element of sorted array, or should we find highest element of array, delete it and again find highest element (which will be the second highest element)?

First option is better. Use `Array.sort` and print second element. Also please provide necessary details. — Rajesh, Jun 26 '16 at 04:38
It's better finding the highest, then the second highest. Because it's only `O(n)` compared to a merge sort (or generally used quick sort ) of `nlog(n)`. — Spencer Wieczorek, Jun 26 '16 at 04:39
You can refer following post http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array — Rajesh, Jun 26 '16 at 04:42
Just a note, bubble sorts are one of the slowest sorts. As they are `O(n^2)` in the average case. — Spencer Wieczorek, Jun 26 '16 at 04:44

score 3 · Answer 1 · answered Jun 26 '16 at 04:38

3

You should make a single pass through the array, tracking the two highest elements as you go.

answered Jun 26 '16 at 04:38

rob mayoff

375,296
67
796
848

2

It would be a good idea to state why that's better, other then just stating it is. – Spencer Wieczorek Jun 26 '16 at 04:42
1

I assumed a newbie isn't famiiar with big-O or memory bandwidth, but okay: sorting is generally O(N log N), bubble sorting is O(N^2), and running through the array once lowers the constant factor over running through it twice and is more cache-friendly. – rob mayoff Jun 26 '16 at 04:56
If they don't you can simply state this way is more efficient because it only iterates though the array once/(twice) while sorting will iterate through the array several more times. I was thinking since they know what a bubble sort is they might have seen big-O before. – Spencer Wieczorek Jun 26 '16 at 05:02

Mureinik · Accepted Answer · 2016-06-28T04:19:22.817

Neither, frankly. Sorting an array would, at best, be a O(nlog(n)) operation (don't use bubble sort, BTW!). Going over the array twice is still an O(n) operation, but you could save roughly half the runtime - You could just go over the array in a single pass and store the second highest as you go.

Consider the following (example given in Java for an int array, but should easily be translatable to any other language or datatype):

int secondHighest(int[] arr) {
     // Assumption: There are at least two elements in the array
     int highest;
     int secondHighest;
     if (arr[0] > arr[1]) {
         highest = arr[0];
         secondHighest = arr[1];
     } else {
         highest = arr[1];
         secondHighest = arr[0];
     }

     for (int i = 2; i < arr.length; ++i) {
         if (arr[i] >= highest) {
              secondHighest = highest;
              highest = arr[i];
          } else if (arr[i] > secondHighest) {
               secondHighest = arr[i];
          }
     }

     return secondHighest;
}

score 0 · Answer 3 · answered Jun 26 '16 at 07:33

It is totally possible in one pass and more efficient by the way. You look up for the two highest values and pick the second one.

PSEUDO-CODE

INTEGER FINDSECONDHIGHEST (ARRAY A)
    INTEGER FIRST = MINIMUM_INTEGER_VALUE_POSSIBLE
    INTEGER SECOND = MINIMUM_INTEGER_VALUE_POSSIBLE

    FOREACH INTEGER I IN A

        IF I > FIRST THEN

            SECOND = FIRST
            FIRST = I

        ELSE IF I > SECOND THEN

            SECOND = I

        END IF

    END FOREACH

RETURN SECOND

Second highest element

3 Answers3