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