How do you find second highest number in an integer array? [duplicate]

Question

This question already has answers here:

Finding the second highest number in array (43 answers)

Closed 8 years ago.

How do you find second highest number in an integer array?

Is this a good implementation?

Is there a better way to do this?

public class Find2ndHighest {
    public static void main(String[] args) {
        int b[] = {2,3,1,0,5};

        TreeMap<Integer,Integer> tree = new TreeMap<Integer,Integer>();
        for(int i = 0; i<b.length;i++){
            tree.put(b[i], 0);
        }
        System.out.println(tree.floorKey(tree.lastKey()-1));
    }
}

Answer 1

You can sort the array and fetch second last element which executes in O(nlogn), but this works only if you are sure that there are no duplicates in the array else this method is unreliable.

You can iterate through the array maintain counters for highest and second highest and return 2nd highest. This executes in O(n)

Example:

 int highest = Integer.MIN_VALUE+1; 
 int sec_highest = Integer.MIN_VALUE;
 for(int i : b) //b is array of integers
 {
     if(i>highest)
     {
        sec_highest = highest; //make current highest to second highest
        highest = i; //make current value to highest
     }
     else if(i>sec_highest && i != highest) 
     {
        sec_highest = i;
     }
 }

---

Another solution is:

int b[] = {1, 2, 31,22,12,12};
Arrays.sort(b);
System.out.println(b[b.length-2]);

Answer 2

The easiest solution would be:

public static void main(String[] args) {
    int b[] = {2,3,1,0,5};
    int highest = Integer.MIN_VALUE;
    int highest2nd = Integer.MIN_VALUE;
    for(int i :b ) 
        if (i>=highest) { 
            highest2nd = highest;
            highest = i;
        } else if (i>= highest2nd)
            highest2nd = i;
    System.out.println(highest2nd);
}

Then you walk through the list only once, which is the best you can do from a 'Big O' standpoint.

PS: depending on whether you want the second highest unique value, or the value that is stricly lower than the highest value, you could choose to put i>highest in the if-statement, instead of i>=highest.

Answer 3

There are multiple ways to find the second highest element in an unsorted array:

1. You can sort the array and take the second last element - runs in O(n log n).

2. You can store the elements in a TreeSet instead of an array, which is what you are doing - runs in O(n log n) as well.

3. Suppose for a while you want to get the highest element - all you have to do is to iterate over the whole aray once, while keeping the maximum in a variable. This way you can achieve O(n) performance.

   You can do the same thing for the second highest element, but instead of keeping the highest element, you will keep the two highest elements. This way you can easily achieve O(n) performance.

4. The only problem with the last solution is that it does not scale well with the increasng k. There is however a linear time algorithm to find the k-th highest element in an unsorted array - runs in O(n) for any k (http://en.wikipedia.org/wiki/Selection_algorithm)