2

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));
    }
}
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
user3246790
  • 31
  • 1
  • 1
  • 3
  • You could simply use `Arrays.sort` and get the last element in the list – MadProgrammer Jan 29 '14 at 00:04
  • How do you find the highest number? – Hot Licks Jan 29 '14 at 00:04
  • @MadProgrammer - That would be the highest number. And it's unnecessary work, from a "Big O" standpoint. – Hot Licks Jan 29 '14 at 00:05
  • @HotLicks True (about the highest), but from a pure lines-of-code, it's a relatively simply start point... – MadProgrammer Jan 29 '14 at 00:07
  • 2
    Can "the second highest" be equal the highest, if integers aren't unique? Both problems are completely different. – Happy Jan 29 '14 at 00:09
  • 1
    Please check this link for better algorithm: http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array?rq=1 – vishal_aim Jan 29 '14 at 00:12
  • Thanks guys for the responses, Arrays.sort would have been more efficient solution, trying to study up for job interviews and test different data structures – user3246790 Jan 29 '14 at 00:15
  • If you're studying up for job interviews you should find out how to do it right. (Though I question whether such job interview tests are worth anything.) – Hot Licks Jan 29 '14 at 01:02

3 Answers3

7

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]);
Surender Dalal
  • 3
  • 3
hemanth
  • 1,033
  • 8
  • 12
  • This is a perfect solution actually, thanks hemanth for helping me out and those whom suggested similar solutions. – user3246790 Jan 29 '14 at 00:25
  • 2
    Doesn't work on `{3,1}`... – Bernhard Barker Jan 29 '14 at 00:54
  • Note that the question is ambiguous as to whether we want the second highest token (which amounts to using `>=` instead of '>') or the second highest type, which has to be strictly lower than the highest number. – Tim Kuipers Jan 29 '14 at 10:10
  • it will also not work for negative number array. e.g: {-5, -3, -8} To make it work for negative number as well, you need to initialize "highest" and "sec_highest" like this: int highest, sec_highest; if(b[0] > b [1]) { highest = b[0]; sec_highest = b[1]; }else{ highest = b[1]; sec_highest = b[0]; } then start loop from 2 index of the array. – Afzal Masood Dec 10 '14 at 19:39
  • if you enter {2,2,1} it is giving 2 as second highest number. – subhashis Feb 03 '15 at 06:40
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.

Tim Kuipers
  • 1,705
  • 2
  • 16
  • 26
1

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)

pepo
  • 669
  • 4
  • 7
  • You miss the right way to do it: Iterate over the list once and keep the TWO highest numbers, rather than just the highest. (And this scheme extends pretty well out to 10, 20 or more "highest".) – Hot Licks Jan 29 '14 at 01:04
  • It's right there, under 3. And although it might scale fairly well for any constant `k`, it is not particularly useful for `k` being a non-constant function of `n` (think of median for example). – pepo Jan 29 '14 at 01:29
  • Perhaps you're right -- the wording was a bit unclear. But the scheme scales quite well, though probably not out to median. I would say it'll probably beat sorting, in "real life" time, out to N/10 or better. – Hot Licks Jan 29 '14 at 01:39