Home » Technical Interview Questions » Array Interview Questions » Find the First and Second Smallest Elements

Find the First and Second Smallest Elements


Reading Time - 2 mins

In find the first and second smallest elements problem we have given an array of integers. Find the first and second smallest integers from an array or find two smallest numbers from an array.

Example

Input

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

Output

First Smallest is 5 and Second Smallest is 6

Here we have so many approaches to solving this problem but we discuss only two of them. We use iteration and store the first and second minimum values and sorting for find the desired result.

Approach 1 for Find the First and Second Smallest Elements

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.

C++ Program 

#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;
}
Smallest and the second smallest numbers are respectively 1 and 2

Complexity Analysis for Find the First and Second Smallest Elements

Time Complexity: O(N) where N is the number of elements present in the array. Here we just store the 1st min and second min element while iterating over the whole array.

READ  Rearrange array such that even positioned are greater than odd

Space Complexity: O(1) because we just use some variables which lead us to O(1) space complexity.

Approach 2 for Find the First and Second Smallest Elements

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.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int arr[] = {56,21,8,91,311,3,7,0};
  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;
}
Smallest and the second smallest numbers are respectively 0 and  3

Complexity Analysis for Find the First and Second Smallest Elements

Time Complexity: O(NlogN) where N is the number of elements in the array. Here we use inbuild sort function which has O(n*logn) time complexity.
Space Complexity: O(1) because we don’t use any auxiliary space here. We just swap the number of the given array.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions