Find the First and Second Smallest Elements

Problem Statement

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.

Implementation

C++ Program 

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N; cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  cin>>arr[i];
  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;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int small,next_small=10000000;
        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 && arr[i] > small)
            next_small = arr[i];
        }
        System.out.println("Smallest and the second smallest numbers are respectively "+small+ " and "+next_small);
    }
}

8
4 1 8 9 11 3 77 2

Smallest and the second smallest numbers are respectively 1 and 2

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.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N; 
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  cin>>arr[i];
  //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;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        Arrays.sort(arr);
        System.out.println("Smallest and the second smallest numbers are respectively "+arr[0]+ " and "+arr[1]);
    }
}

5
1 5 3 2 9

Smallest and the second smallest numbers are respectively 1 and 2