Find second highest number in an array

Nowadays technical interview involves writing small small code to judge whether candidate is aware of java APIs or not and how he/she using APIs in different scenarios.

For any such scenario, there can be 10 ways in which you can code a given problem but among those only 2-3 ways will solve the problem efficiently.

Take an example to "find out second highest number in a given array."

My version of solving this problem statement would be using stack with size 2. It will hold highest and second highest number by traversing on given array.

Pseudo Code:
1. Create a stack with size limit 2.
2. Start traversing on given array arr[n] from i=0 to n-1, step 1.
3. If arr[i] is greater than HEAD element of stack then push arr[i] into stack, so that HEAD element       will go one level down and arr[i] will become HEAD.
    Else if arr[i] is greater than TAIL element of stack then replace TAIL element with arr[i].

This diagram will be helpful to understand stack push operation:

As we know that Stack class of Java has no size limitation so somehow we have to limit the size to 2. Therefore I created customized stack to store elements. As you can see I overridden push method and if stack size becomes equal to max size(in our case its 2), then I am removing bottom element before doing any push operation to stack.

 import java.util.Stack;  
 @SuppressWarnings("serial")  
 public class SizedStack<E> extends Stack<E> {  
      private int maxSize;  
      public SizedStack(int maxSize){  
           super();  
           this.maxSize = maxSize;  
      }  
      @Override  
      public E push(E item){  
           if(this.size() == maxSize){  
                this.remove(0);  
           }  
           return super.push(item);  
      }  
 } 

Class which is implementing discussed pseudo code:

 public class FindSecondLargest {  
      public static void main(String[] args) {  
           int[] arr = {4,3,2,9,4,5,3,7};  
           System.out.println(getSecondLargest(arr));  
      }  
      public static int getSecondLargest(int[] arr){  
           SizedStack<Integer> stack = new SizedStack<Integer>(2);  
           int head = stack.push(0);  
           int tail = stack.get(0);  
           for(int i=0; i<arr.length; i++){  
                if(arr[i] > head){  
                     head = stack.push(arr[i]);  
                }else if(arr[i] > tail){  
                     tail = stack.set(0, arr[i]);  
                }  
           }  
           return stack.get(0);  
      }  
 }  

As you can see that each element in the array will be compared against 2 elements at most which resides in stack.

Since this operation is repeated exactly n times(size of array), hence we can say that time complexity of this algorithm will be O(n).

At the same time I cannot say that my version is best approach for given problem statement, but one of efficient way to solve the problem.

If you can give some solution and time complexity in terms of some logarithmic function then definitely your solution would be more efficient that mine version.