Find the second-largest number in an array of elements

I have written this code to find second largest element in an array of random integers. If it needs to be optimized, then do comment on it. First of all I'm populating all the elements into the list which does not have any repeating value, then sorting, then in list.size()-2 I have second largest element.

This is one way of doing this:

int[] randomIntegers = {1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9};
int max = Integer.MIN_VALUE;
int secMax = Integer.MIN_VALUE;
List list = new ArrayList<>();
for(int i:randomIntegers) {
    if(!(list.contains(i))){
        list.add(i);
    }
}
Collections.sort(list);
System.out.println(list.get(list.size()-2));

If you are not allowed to sort that list then you can do the following to find the second-largest element:

int[] randomIntegers = {1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9};
int max = Integer.MIN_VALUE;
int secMax = Integer.MIN_VALUE;
List list = new ArrayList<>();
for(int i:randomIntegers) {
    if(!(list.contains(i))){
        list.add(i);
    }
}
for(int i:list) {
    if(max < i) {
        secMax = max;
        max = i;
    }
    else if(secMax < i){
        secMax = i;
    }
}
System.out.println("Second Largest Number is :" + secMax);

ArrayList is not the right tool. Since ArrayList makes no attempt to arrange its elements, ArrayList.contains(...) is inefficient — it has to examine every previously added element to see whether it is present. Then, at the end, you still have to sort the entire list. If you're adding n numbers, and adding each number takes O(n) time, then your entire solution is O(n2), which is horrible for such a simple problem.

If you want to use a Java Collections data structure, why not use SortedSet instead? The advantages of SortedSet are:

• It maintains the order of elements as it adds them

• It automatically deduplicates (TreeSet does it in O(log n) time)

• You don't have to sort the elements again at the end

Here's a solution (that works in O(n log n) time):

int[] randomIntegers = { 1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9 };
SortedSet set = new TreeSet();
for (int i: randomIntegers) {
    set.add(i);
}
// Remove the maximum value; print the largest remaining item
set.remove(set.last());
System.out.println(set.last());

A more efficient and minimalist solution wouldn't use any data structure. You just keep track of the two largest numbers you have encountered as you walk along the input array. See this related question. That approach hardly uses any space and works in O(n) time, which is as good as it gets.

StackExchange Code Review Q#31470, answer score: 7