Find the first and second smallest elements

OR

Find two smallest numbers from an array

INPUT: 7, 6, 8, 10, 11, 5, 13, 99

OUTPUT: First Smallest is 5 and Second Smallest is 6

Method 1

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

Algorithm

1. Take two variables smallest and nextSmallest.
2. Let say smallest is initialized with first element of array.
3. Keep on comparing the array values as:
a. If the array element is smaller than smallest then

• Compare the value of smallest with value of  nextSmallest and update accordingly.
• Update the smallest value.

b. Else compare if the array element is larger than smallest but smaller than nextSmallest then change the value of nextSmallest variable.

Program for Method 1

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {4,1,8,9,11,3,77,2};
int N = sizeof(arr)/sizeof(arr[0]);

int small,next_small=INT_MAX;
small = arr[0];

for(int i=1;i<N;i++)
{
if(arr[i] < small)
{
next_small = small;
small = arr[i];
}
else if(arr[i] < next_small and arr[i] > small)
next_small = arr[i];
}

cout << "Smallest and the second smallest numbers are respectively "<< small << " and " << next_small <<endl;

return 0;
}``````

Method 2

TIME COMPLEXITY: O(NlogN)
SPACE COMPLEXITY: O(N)

Algorithm

1. Simply Sort the array using Merge or Heap sort. We can also use sort() STL.
2. The first and the second element will be the smallest and next smallest respectively as it is in ascending order.

Program for Method 2

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {4,1,8,9,11,3,77,2};
int N = sizeof(arr)/sizeof(arr[0]);

//sort the array and the first two elements are the desired values
sort(arr,arr+N);

cout << "Smallest and the second smallest numbers are respectively "<< arr[0] << " and  " << arr[1] <<endl;

return 0;
}``````

Scroll to Top