Problem Statement: Given an array, find the second smallest and second largest element in the array. Print ‘-1’ if either of them doesn’t exist.

Example:

Example 1:
Input: [1,2,4,7,7,5]
Output: Second Smallest : 2
    Second Largest : 5
Explanation: The elements are as follows 1,2,3,5,7,7 and hence second largest of these is 5 and second smallest is 2

Constraints:

• Duplicates are present

• Array size >= 1

• Requires O(N) solution

Brute Force Approach (Sorting)

1. Sort the array

2. Get the element, just less than the last element in the sorted array

3. Take care of edge cases (Not found, duplicates)

public static int findSecondLargest(int n, int[] arr){
    if(n == 1)
        return -1;

    // As negatives are present, use int's min
    int secondLargest = Integer.MIN_VALUE;

    // Sort the array
    Arrays.sort(arr);

    // Get the second minimum
    for(int i = n - 2; i > 0; i--){
        if(arr[i] < arr[n-1]){
            secondLargest = arr[i];
            break;
        }
    }

    return (secondLargest == Integer.MIN_VALUE) ? -1 : secondLargest;
}

Better Approach (Linear Traversal)

1. Find the first largest element

2. Find the largest element which is not equal to the first largest, which is second largest

public static int findSecondLargest(int n, int[] arr){
    if(n == 1)
        return -1;

    // As negatives are present, use int's min
    int firstLargest = Integer.MIN_VALUE;
    int secondLargest = Integer.MIN_VALUE;

    // Find the first maximum
    for(int i = 0; i < n; i++){
        firstLargest = Math.max(firstLargest, arr[i]);
    }

    // Find the second maximum
    for(int i = 0; i < n; i++){
        if(arr[i] != firstLargest)
            secondLargest = Math.max(secondLargest, arr[i]);
    }

    return (secondLargest == Integer.MIN_VALUE) ? -1 : secondLargest;
}

Optimal Approach (Two pointers)

This approach is based on how an element is ranked second. It is advised to dry-run the algorithm to get the intuition of the approach.

1. The first updates for the maximum element

2. The second pointer updates when

   1. The first pointer gets a new maximum

   2. The first pointer is not updated, but a larger element is present

public static int findSecondLargest(int n, int[] arr) {

        int firstLargest = Integer.MIN_VALUE, secondLargest = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++){
            if(firstLargest < arr[i]){
                secondLargest = firstLargest;
                firstLargest = arr[i];
            }
            else if(firstLargest != arr[i]){
                secondLargest = Math.max(secondLargest, arr[i]);
            }
        }

        return (secondLargest == Integer.MIN_VALUE) ? -1: secondLargest;
    }