Link: Geeks for Geeks

Given an array of integers, our task is to write a program that efficiently finds the second largest element present in the array.

Example:

Input : arr[] = {12, 35, 1, 10, 34, 1}
Output : The second largest element is 34.

Input : arr[] = {10, 5, 10}
Output : The second largest element is 5.

Input : arr[] = {10, 10, 10}
Output : The second largest does not exist.

Questions

1. Can we consider the array to be an array of integers?
2. What will be the minimum number of elements in the array? (Hint - If array can contain only 2 elements, we can simply compare the 2 elements and return the second bigger number.)
3. What will be the range of elements in array - Positives, Negatives? (Hint - If array contains negative values as well, then we have to initialize first & second variables to INTEGER MINIMUM values, else we can assign them to -1)
4. Is the array sorted? (Hint - If sorted in ascending order, then simply return last but one element.)

A simple solution will be first sort the array in descending order and then return the second element from the sorted array. The time complexity of this solution is O(n logn).

A Better Solution is to traverse the array twice. In the first traversal find the maximum element. In the second traversal find the greatest element less than the element obtained in first traversal. The time complexity of this solution is O(n).

A more Efficient Solution can be to find the second largest element in a single traversal.
Below is the complete algorithm for doing this:

1) Initialize two variables first and second to INT_MIN as,
   first = second = INT_MIN
2) Start traversing the array,
   a) If the current element in array say arr[i] is greater
      than first. Then update first and second as,
      second = first
      first = arr[i]
   b) If the current element is in between first and second (this is important, as it takes care of duplicate values),
      then update second to store the value of current variable as
      second = arr[i]
3) Return the value stored in second.

Example:

Given Array = {12, 35, 1, 10, 34, 1}

Initialize the variables: first = second = -1

Loop finish. Return the _second _value.

Time Complexity: O(n) - Linear time, as we have to iterate the array once when it is unsorted.

Space Complexity: O(1) - Constant space, as we need only 2 spaces to hold the intermediate values.

public class SecondLargest {

    public int perform(int[] array) {

        int first = -1;
        int second = -1;

        for(int i = 0; i < array.length; i++) {
            if (array[i] > first) {
                second = first;
                first = array[i];
            } else if (first > array[i] && array[i] > second) {
                second = array[i];
            }
        }
        return second;
    }

    public static void main(String[] args) {
        SecondLargest secondLargest = new SecondLargest();
        int arr[] = {12, 35, 1, 10, 34, 1};
        int secondLarge = secondLargest.perform(arr);
        System.out.println("Second Largest Number is: " + secondLarge);
    }
}