Searching and Sorting: Find the smallest and second smallest elements in an array

Problem Statement:

You are given an unsorted array.

You need to find the first and second smallest element in that unsorted array.

You need to do it with minimum comparisons.

Example

Input: {5, 3, 1, 6, 7, 9, 10}

Output: The smallest element is 1 and
second Smallest element is 10

Solution

There are number of solutions:

1. Naive approach:

Here you will sort the array in increasing order then get the first 2 elements of the array.

The time complexity is (nlogn)

2. O(n) solution:

In this solution we traverse the array twice.
First time we get the smallest element.
Second time we get the second smallest element.

3. Efficient solution:

In this solution we can can find the min two elements in one traversal only.

Take 2 variables initialize to INT_MAX. Then start looping through the elements in the array,
-> check if the element is smaller than first, then update first and second.

->else if the current element is smaller than second, then update only second.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

void get_two_smallest_elements(int arr[], int arr_size)  
{  
    int i, first, second;  
  
    first = second = INT_MAX; 

    for (i = 0; i < arr_size ; i ++)  
    {  

        if (arr[i] < first)  
        {  
            second = first;  
            first = arr[i];  
        }  

        else if (arr[i] < second && arr[i] != first)  
            second = arr[i];  
    } 
 
        cout << "The first smallest element is " << first << " and second "
            "Smallest element is " << second << endl;  
}  
  
int main()  
{  
    int arr[] = {5, 3, 1, 6, 7, 9, 10};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    get_two_smallest_elements(arr, n);  
    return 0;  
}  

Output:

The first smallest element is 1 and second Smallest element is 3