Find the Second Smallest Element in an Array Efficiently

Finding the second smallest element in an array is a common programming task. This article covers three different approaches to solve this problem, each with varying levels of efficiency and simplicity.

Methods to Find the Second Smallest Element

Method 1: Sorting the Array

This is the simplest approach. By sorting the array in ascending order, the second smallest element can be found directly at the second position.

Algorithm

1. Declare an array and input the array elements.
2. Sort the array using a sorting function (e.g., sort(arr, arr + n) in C++).
3. Display the second element from the sorted array.

Code Example

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

void findSecondSmallestBySorting(int arr[], int n) {
    sort(arr, arr + n);
    cout << "The second smallest element is: " << arr[1] << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);

    findSecondSmallestBySorting(arr, n);
    return 0;
}

Output

Input: [12, 3, 5, 7, 19]
Output: The second smallest element is: 5

Method 2: Two Traversals of the Array

In this method, the array is traversed twice:

1. The first traversal finds the smallest element (first_smallest).
2. The second traversal finds the smallest element greater than first_smallest (second_smallest).

Algorithm

1. Declare an array and input the array elements.
2. Traverse the array to find the smallest element (first_smallest).
3. Traverse the array again, skipping first_smallest, to find the second smallest element (second_smallest).
4. Display second_smallest.

Code Example

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

void findSecondSmallestTwoPass(int arr[], int n) {
    int first_smallest = INT_MAX, second_smallest = INT_MAX;

    // First traversal to find the smallest element
    for (int i = 0; i < n; i++) {
        if (arr[i] < first_smallest) {
            first_smallest = arr[i];
        }
    }

    // Second traversal to find the second smallest element
    for (int i = 0; i < n; i++) {
        if (arr[i] > first_smallest && arr[i] < second_smallest) {
            second_smallest = arr[i];
        }
    }

    cout << "The second smallest element is: " << second_smallest << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);

    findSecondSmallestTwoPass(arr, n);
    return 0;
}

Output

Input: [12, 3, 5, 7, 19]
Output: The second smallest element is: 5

Method 3: Single Traversal of the Array

This is the most efficient method, where the array is traversed once. The smallest and second smallest elements are updated dynamically as the array is traversed.

Algorithm

1. Declare an array and input the array elements.
2. Initialize first_smallest and second_smallest to a very large value (e.g., INT_MAX).
3. Traverse the array:
   • If the current element is smaller than first_smallest, update second_smallest to first_smallest and first_smallest to the current element.
   • Otherwise, if the current element is greater than first_smallest but smaller than second_smallest, update second_smallest.
4. Display second_smallest.

Code Example

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

void findSecondSmallestSinglePass(int arr[], int n) {
    int first_smallest = INT_MAX, second_smallest = INT_MAX;

    for (int i = 0; i < n; i++) {
        if (arr[i] < first_smallest) {
            second_smallest = first_smallest;
            first_smallest = arr[i];
        } else if (arr[i] > first_smallest && arr[i] < second_smallest) {
            second_smallest = arr[i];
        }
    }

    cout << "The second smallest element is: " << second_smallest << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);

    findSecondSmallestSinglePass(arr, n);
    return 0;
}

Output

Input: [12, 3, 5, 7, 19]
Output: The second smallest element is: 5

Related Programs

1. Basic Array Operations: Insert, delete, and search an element.
2. Find the Smallest and Largest Elements in an Array.
3. Sum of Elements in an Array.
4. Sort the Elements of an Array.
5. Find Non-Repeating Elements in an Array.
6. Identify Repeating Elements in an Array.

By understanding these three methods, you can choose the best approach based on the constraints and size of your dataset. Experiment with the provided code examples to solidify your grasp of the concepts.