Problem Statement

Given an array of integers, the task is to find the second smallest and second largest elements present in the array.

Examples

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

Example 2:

Input: [1]
Output: Second Smallest : -1
        Second Largest : -1

Explanation: Since there is only one element in the array, it is the largest and smallest element present in the array. There is no second largest or second smallest element present.

Example 3:

Input: [5, 5, 5, 5, 5]
Output: Second Smallest :  -1
        Second Largest : -1

Explanation: Since all the elements in the array are same, so there is no second smallest or second largest element.

Different Approaches

1️⃣ Brute Force Approach: (this approach only works if there are no duplicates)

Sorting the array in increasing order allows us to easily identify the second smallest and second largest elements. Once the array is sorted, the second smallest element will be at index 1, and the second largest element will be at index n - 2, where n is the size of the array.

Algorithm:

1. Sort the array in non-decreasing order.
2. The second smallest element will be at index1 (arr[1]), and the second largest element will be at index n - 2 (arr[n - 2]), where n is the size of the array.

Code:

#include<bits/stdc++.h>
using namespace std;
void getElements(int arr[],int n)
{
    if(n==0 || n==1)
        cout<<-1<<" "<<-1<<endl;  // edge case when only one element is present in array
    sort(arr,arr+n);
    int small=arr[1];
    int large=arr[n-2];
    cout<<"Second smallest is "<<small<<endl;
    cout<<"Second largest is "<<large<<endl;
}
int main()
{
    int arr[]={1,2,4,6,7,5};
    int n=sizeof(arr)/sizeof(arr[0]);
    getElements(arr,n);
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n log n) due to sorting.
• Space Complexity:O(1) if sorting is done in place.

2️⃣ Better Solution

Algorithm:

1. Find the smallest and largest element in the array in a single traversal.
2. After this, we once again find the largest element however which is smaller than the largest element which we found in first traversal.
3. Similarly, we would find the second smallest element which is just larger than the smallest element from the first traversal.

Code:

#include<bits/stdc++.h>
using namespace std;
void getElements(int arr[],int n)
{
    if(n==0 || n==1)
        cout<<-1<<" "<<-1<<endl;  // edge case when only one element is present in array
    int small=INT_MAX,second_small=INT_MAX;
    int large=INT_MIN,second_large=INT_MIN;
    int i;
    for(i=0;i<n;i++)
    {
        small=min(small,arr[i]);
        large=max(large,arr[i]);
    }
    for(i=0;i<n;i++)
    {
        if(arr[i]<second_small && arr[i]!=small)
            second_small=arr[i];
        if(arr[i]>second_large && arr[i]!=large)
            second_large=arr[i];
    }

    cout<<"Second smallest is "<<second_small<<endl;
    cout<<"Second largest is "<<second_large<<endl;
}
int main()
{
    int arr[]={1,2,4,6,7,5};
    int n=sizeof(arr)/sizeof(arr[0]);
    getElements(arr,n);
    return 0;
}

// Output
Second smallest is 2
Second largest is 6

Complexity Analysis

Time Complexity:

• The first loop iterates through the array once to find the smallest and largest elements. This requires O(n) time.
• The second loop also iterates through the array once to find the second smallest and second largest elements. This also requires O(n) time.
• Therefore, the overall time complexity of this approach is O(n + n), which is simplifies to O(2n), or O(n) when considering the dominant term.

Space Complexity:

• The space complexity of this approach remains O(1)as it only uses a constant amount of extra space to store variables.

3️⃣ Optimal Approach

The time complexity was reduced to O(n) in the previous approach, but still involved two separate traversal of the array, which may not be the most efficient solution, especially for large arrays.

To optimize the solution further and reduce it to single traversal, we can use a slightly different strategy. We can maintain four variables to keep track of the smallest, second smallest, largest, and second largest elements as we traverse the array one.

Algorithm:

• Initialize four variables: smallest, second_smallest, largest, and second_largest, with initial values set to the maximum and minimum possible integer values, respectively.
• Iterate through the array:
  • For each element arr[i]:
    • If arr[i] is smaller than smallest, update both second_smallest and smallest.
    • Otherwise, if arr[i] is smaller than second_smallest and arr[i]is not equal to smallest, update second_smallest only.
    • If arr[i] is larger than largest, update both second_largest and largest.
    • Otherwise, if arr[i] is larger than second_largest and arr[i] is not equal to largest, update second_largest only.
• After iterating through the entire array, the variables second_smallest and second_largest will contain the second smallest and second largest elements, respectively.
• Output the values of second_smallest and second_largest.

Code:

#include <iostream>
#include <climits> // For INT_MAX and INT_MIN

using namespace std;

void findSecondLargestAndSmallest(int arr[], int n) {
    // Initializing the variables
    int smallest = INT_MAX, second_smallest = INT_MAX;
    int largest = INT_MIN, second_largest = INT_MIN;

    if (n < 2) {
        cout << "Array needs to have at least two elements." << endl;
        return;
    }

    for (int i = 0; i < n; ++i) {
        // Finding smallest and second smallest
        if (arr[i] < smallest) {
            second_smallest = smallest;
            smallest = arr[i];
        } else if (arr[i] < second_smallest && arr[i] != smallest) {
            second_smallest = arr[i];
        }

        // Finding largest and second largest
        if (arr[i] > largest) {
            second_largest = largest;
            largest = arr[i];
        } else if (arr[i] > second_largest && arr[i] != largest) {
            second_largest = arr[i];
        }
    }

    // Checking if we found valid second smallest and second largest
    if (second_smallest == INT_MAX) {
        cout << "There is no second smallest element." << endl;
    } else {
        cout << "The second smallest element is: " << second_smallest << endl;
    }

    if (second_largest == INT_MIN) {
        cout << "There is no second largest element." << endl;
    } else {
        cout << "The second largest element is: " << second_largest << endl;
    }
}

int main() {
    int arr[] = {12, 35, 1, 10, 35, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    findSecondLargestAndSmallest(arr, n);

    return 0;
}

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is O(n), where n is the number of elements in the array. This is because we only traverse the array once.
• Space Complexity: The space complexity of this algorithm is O(1), as we only use a constant amount of extra space to store the variables smallest, second_smallest, largest, and second_largest.