Find the First and Second Smallest Elements

Difficulty Level Easy
Frequently asked in Amazon MAQ o9 solutions TCS
Array SearchingViews 2853

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;
}

Java Program

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

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 elements while iterating over the whole array.

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.

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;
}

Java Program

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

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 the 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

Translate »