Find Second Smallest and Second Largest Element in an array

When working with an array of integers, the task often arises to identify the second smallest and second largest elements within the array. This article at OpenGenus.org explores both a brute-force approach and an optimized technique to find Second Smallest and Second Largest Element in an array, followed by real-world scenarios where such analysis proves valuable.

Table of Contents:

1. Problem Statement
2. Key takeaways
3. Mininum comparisions required for bruteforce and optimized approach.
4. Brute force approach
5. Optimized approach: Divide and Conquer
6. Real World examples.

Problem Statement

Given an array of integers arr of length n, the goal is to determine the second largest and second smallest elements present in the array. For instance, consider the array arr = [12, 35, 1, 10, 34, 1]. The expected output would be:

Second Smallest: 10
Second Largest: 34

Key takeaways

Brute Force Approach:

• Involves multiple passes through the array.
• Requires n - 1 comparisons for finding the smallest and largest elements.
• For finding the second smallest and second largest elements, it needs 2n comparisons.
• Time Complexity: O(n) for small arrays.
• Space Complexity: O(1).

Optimized Approach:

• Achieves the goal with a single pass through the array.
• Uses only 3n comparisons to find the second smallest and second largest elements.
• Time Complexity: O(n), which is more efficient than the brute force approach for larger arrays.
• Space Complexity: O(1).

Mininum comparisions required for bruteforce and optimized approach.

Second Smallest element

Imagine you have a list of numbers, and you want to find the smallest number.

1. If the list size is a power of 2 (like 2, 4, 8, 16...), finding the smallest number needs half the size in comparisons each time, until only one number remains.
2. The total number of comparisons needed to figure out the smallest number is the size of the list minus 1.
3. Now, to find the second smallest number, you compare it with all the other numbers except the smallest one.
4. The process to find the second smallest number involves a step where we work with a smaller list, which has at most log₂(n) numbers. This step needs log₂(n) - 1 comparisons.

When you add up these steps, the smallest number requires n - 1 comparisons, and finding the second smallest number needs n + log₂(n) - 2 comparisons.

So, in simple words, to find the second smallest number in a list using this method, we need around n + log₂(n) - 2 comparisons.

Second Largest element

Imagine you have a list of numbers, and you want to find the second largest number.

1. If the list size is a power of 2 (like 2, 4, 8, 16...), finding the second largest number needs half the size in comparisons each time, until only one number remains.
2. The total number of comparisons needed to figure out the second largest number is the size of the list minus 1.
3. Now, to find the second largest number, you compare it with all the other numbers except the largest one.
4. The process to find the second largest number involves a step where we work with a smaller list, which has at most log₂(n) numbers. This step needs log₂(n) - 1 comparisons.

When we add up these steps, finding the largest number requires n - 1 comparisons, and finding the second largest number needs n + log₂(n) - 2 comparisons.

So, to find the second largest number in a list using this method, we need around n + log₂(n) - 2 comparisons, similar to finding the second smallest number.

Comparisions when finding both the second smallest and second largest elements together

Finding both the second smallest and second largest elements together can lead to an optimized approach that leverages the comparisons more effectively. To minimize the number of comparisons, we can use a modified version of the divide and conquer strategy.

1. Divide the list into pairs:

Pair up adjacent elements in the list. Compare each element in a pair and keep track of the smaller and larger elements of each pair.

2. Find the smallest and largest of the smaller elements:

Compare the smaller elements from step 1 to find the smallest among them. This requires log₂(n) comparisons.

3. Find the largest of the larger elements:

Compare the larger elements from step 1 to find the largest among them. This requires log₂(n) - 1 comparisons.

4. Compare the smallest from step 2 with the larger from step 3:

Compare the smallest element from step 2 with the larger element from step 3 to determine the second smallest.

5. Compare the largest from step 2 with the larger from step 4:

Compare the largest element from step 2 with the larger element from step 4 to determine the second largest.

By using this approach, you can find both the second smallest and second largest elements in a list of numbers with a total of 3 * log₂(n) - 5 comparisons. This is more efficient than the individual calculations.

BruteForce Approach

In brute force approach we find the second largest and second smallest element by iterating through the array multiple times. Here's an intuitive breakdown of the process:

1. Finding Smallest Element:

We will start by looking at each element in the array to determine the smallest element. This involves comparing each element with the current smallest element found so far. By the end of this step, we have identified the smallest element in the array.

2. Finding Largest Element:

Similar to finding smallest element, we will examine each element again to find the largest element in the array. This step involves comparing each element with the current largest element found so far.

3. Finding Second Smallest and Second Largest:

Finally, we will go through the array one more time to identify the second smallest and second largest elements. For each element, we compare it with the current second smallest and second largest elements, updating them if necessary.

C++ Implementation:

#include <iostream>
#include <limits>
using namespace std;

pair<int, int> findSecondSmallestLargestBruteforce(int arr[], int n) {
    if (n < 2) {
        return {-1,-1};  // Not enough elements to find second smallest and second largest
    }

    int secondSmallest = INT_MAX;
    int smallest = INT_MAX;
    int secondLargest = INT_MIN;
    int largest = INT_MIN;

    for (int i = 0; i < n; ++i) {
        smallest = min(smallest, arr[i]);
    }

    for (int i = 0; i < n; ++i) {
        largest = max(largest, arr[i]);
    }

    for (int i = 0; i < n; ++i) {
        if (arr[i] > smallest && arr[i] < secondSmallest) {
            secondSmallest = arr[i];
        }

        if (arr[i] < largest && arr[i] > secondLargest) {
            secondLargest = arr[i];
        }
    }

    return make_pair(secondSmallest, secondLargest);
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    pair<int, int> result = findSecondSmallestLargestBruteforce(arr, n);
    
    cout << "Second Smallest: " << result.first << endl;
    cout << "Second Largest: " << result.second << endl;
    
    return 0;
}

Explanation with example:

1. Initially Smallest=secondSmallest=INT_MAX and largest=secondLargest=INT_MIN.
2. Iterate through the array: [12, 35, 1, 10, 34, 1].From this we can find that smallest is 1 and largest is 35.
3. Finding Second Smallest and Second Largest:

• Iterate through the array once more: [12, 35, 1, 10, 34, 1].
• For each element num in the array:
  Examine whether num falls within the range of smallest and the current value of secondSmallest.

num = 12, NO

num = 35 NO

num = 1, YES the condition holds trueand we update the secondSmallest to 1.

num = 10, YES, the condition holds trueand we update the secondSmallest to 10.

num = 34, NO

num = 1, No

num = 12, NO

num = 35, YES the condition holds trueand we update the secondSmallest to 35.

num = 10, YES the condition holds trueand we update the secondSmallest to 10.

num = 34, NO
num = 1, NO

Here the NO is indicating that the condition is not met
Final Result:
secondSmallest = 10 (second smallest element).
secondLargest = 35 (second largest element).

Number of caluclations:

• Finding Smallest Element: n - 1 comparisons (in the worst case).
• Finding Largest Element: n - 1 comparisons (in the worst case).
• Finding Second Smallest and Second Largest: 2n comparisons (2 comparisons for each of the n elements).
• Total Comparisons: (n - 1) + (n - 1) + 2n = 4n - 2 comparisons.

Time Complexity:

1. For Finding Smallest Element: O(n)
2. For Finding Largest Element: O(n)
3. For Finding Second Smallest and Second Largest: O(n)

The total time complexity simplifies to O(n).

The brute force approach's time complexity is reasonable for small arrays, it's less efficient compared to more optimized algorithms for larger arrays.

Space Complexity:

O(1)
The space complexity is constant because you're using a few extra variables (secondSmallest, secondLargest, smallest, largest) that do not depend on the size of the input array.

Optimised Approach:

An optimized approach for finding the second smallest and second largest elements in an array involves iterating through the array just once.

Intutive Steps:

1. First Pass:

We go through the array elements just once. During this pass, we keep track of important information about the smallest, second smallest, largest, and second largest elements seen so far.

2. Identify Smallest and Second Smallest:

As you iterate, we update the values of the smallest and second smallest elements. If we find a new smallest element, we move the current smallest to the second smallest, and update the smallest with the new element.

3. Identify Largest and Second Largest:

Similarly, we update the values of the largest and second largest elements. If we find a new largest element, we move the current largest to the second largest, and update the largest with the new element.

4. Result:

By the end of the single pass, we've efficiently identified the second smallest and second largest elements without the need for multiple iterations.

#include <iostream>
#include <limits>
using namespace std;

pair<int, int> findSecondSmallestLargestOptimized(int arr[], int n) {
    if (n < 2) {
        return make_pair(-1, -1);  
    }

    int smallest = INT_MAX
    int secondSmallest = INT_MAX
    int largest = INT_MIN
    int secondLargest = INT_MIN

    for (int i = 0; i < n; ++i) {
        if (arr[i] < smallest) {
            secondSmallest = smallest;
            smallest = arr[i];
        } else if (arr[i] < secondSmallest && arr[i] != smallest) {
            secondSmallest = arr[i];
        }

        if (arr[i] > largest) {
            secondLargest = largest;
            largest = arr[i];
        } else if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }

    return({secondSmallest, secondLargest});
}

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

    pair<int, int> result = findSecondSmallestLargestOptimized(arr, n);

    cout << "Second Smallest: " << result.first << endl;
    cout << "Second Largest: " << result.second << endl;

    return 0;
}

Explanation:

example:[12, 35, 1, 10, 34, 1]

1. Initialization:
   smallest = INT_MAX
   secondSmallest = INT_MAX
   largest = INT_MIN
   secondLargest = INT_MIN

2. Iterating Through the Array Once:

For num = 12:
smallest and secondSmallest are updated.
largest and secondLargest are not updated.

For num = 35:
smallest, secondSmallest, largest, and secondLargest sare same

For num = 1:
smallest and secondSmallest are updated.
largest and secondLargest are not updated.

For num = 10:
smallest, secondSmallest, largest, and secondLargest are updated.

For num = 34:
smallest, secondSmallest, largest, and secondLargest are updated.

For num = 1:
smallest, secondSmallest, largest, and secondLargest remain unchanged.

3. Final Result:
   secondSmallest is 10.
   secondLargest is 34.

Number of Caluclations:

• Finding Second Smallest and Second Largest: 3n comparisons (3 comparisons for each of the n elements).

Time Complexity:

Iterating Through the Array: O(n)
In this step, you iterate through the array once to find the second smallest and second largest elements.The time complexity is linear, proportional to the number of elements in the array (n).

This optimized approach maintains the same time complexity as the original brute force approach (O(n)) but achieves the goal with just one iteration, which makes it more efficient for larger arrays.

Space Complexity:

Additional Variables: O(1)
The space complexity is constant because you're using a few extra variables (smallest, secondSmallest, largest, secondLargest) that do not depend on the size of the input array. These variables require constant space, irrespective of the size of the array.

Real World Examples:

1. Exam Grades Ranking:In an educational context, you could use this to identify the second highest and second lowest scores in a class. This might help in determining grading curves or understanding the performance distribution.

2. Population Statistics:You might want to find the second highest and second lowest populations in certain regions. This could be important for urban planning and resource allocation.

3. Stock Prices Analysis:In financial analysis, you might want to find the second highest and second lowest stock prices for a particular period. This can provide insights into stock volatility and potential investment opportunities.

With this article at OpenGenus, you must have the complete idea of how to find Second Smallest and Second Largest Element in an array.