Find the first, second and third minimum elements in an array
Find the first, second and third minimum elements in an array in O(n).
Examples:
Input : 9 4 12 6 Output : First min = 4 Second min = 6 Third min = 9 Input : 4 9 1 32 12 Output : First min = 1 Second min = 4 Third min = 9
First approach : First we can use normal method that is sort the array and then print first, second and third element of the array. Time complexity of this solution is O(n Log n).
C++
// CPP program to find the first, second // and third minimum element in an array #include<bits/stdc++.h> using namespace std; int Print3Smallest( int array[], int n) { // Sorting the array sort(array,array+n); cout << "First min = " << array[0] << "\n" ; cout << "Second min = " << array[1] << "\n" ; cout << "Third min = " << array[2] << "\n" ; } // Driver code int main() { int array[] = {4, 9, 1, 32, 12}; int n = sizeof (array) / sizeof (array[0]); Print3Smallest(array, n); return 0; } // Code submitted by Pushpesh Raj |
Java
// Java program to find the first, second // and third minimum element in an array import java.util.Arrays; public class Main { static void Print3Smallest( int array[], int n) { // Sorting the array Arrays.sort(array); System.out.println( "First min = " + array[ 0 ]); System.out.println( "Second min = " + array[ 1 ]); System.out.println( "Third min = " + array[ 2 ]); } // Driver code public static void main(String[] args) { int array[] = { 4 , 9 , 1 , 32 , 12 }; int n = array.length; Print3Smallest(array, n); } } // this code is contributed by bhardwajji |
Python3
# Python program to find the first, second # and third minimum element in an array def print_3_smallest(array): # Sorting the array array.sort() print ( "First min =" , array[ 0 ]) print ( "Second min =" , array[ 1 ]) print ( "Third min =" , array[ 2 ]) # Driver code if __name__ = = '__main__' : array = [ 4 , 9 , 1 , 32 , 12 ] n = len (array) print_3_smallest(array) |
C#
// C# program to find the first, second // and third minimum element in an array using System; using System.Linq; class Program { static void Print3Smallest( int [] array, int n) { // Sorting the array Array.Sort(array); Console.WriteLine( "First min = " + array[0]); Console.WriteLine( "Second min = " + array[1]); Console.WriteLine( "Third min = " + array[2]); } // Driver code static void Main() { int [] array = {4, 9, 1, 32, 12}; int n = array.Length; Print3Smallest(array, n); } } |
Javascript
// JavaScript program to find the first, // second and third minimum element in an // array. function Print3Smallest(array,n){ // Sorting the array array.sort((a, b) => a - b); console.log( 'First min = ' + array[0]); console.log( 'Second min = ' + array[1]); console.log( 'Third min = ' + array[2]); } // Driver code let array = [4, 9, 1, 32, 12]; Print3Smallest(array,array.length); |
Output
First min = 1 Second min = 4 Third min = 9
Second approach : Time complexity of this solution is O(n).
Algorithm:
- First take an element
- then if array[index] < Firstelement
- Thirdelement = Secondelement
- Secondelement = Firstelement
- Firstelement = array[index]
- else if array[index] < Secondelement
- Thirdelement = Secondelement
- Secondelement = array[index]
- else if array[index] < Thirdelement
- Thirdelement = array[index]
- then print all the element
Implementation:
C++
// CPP program to find the first, second // and third minimum element in an array #include<bits/stdc++.h> #define MAX 100000 using namespace std; int Print3Smallest( int array[], int n) { int firstmin = MAX, secmin = MAX, thirdmin = MAX; for ( int i = 0; i < n; i++) { /* Check if current element is less than firstmin, then update first, second and third */ if (array[i] < firstmin) { thirdmin = secmin; secmin = firstmin; firstmin = array[i]; } /* Check if current element is less than secmin then update second and third */ else if (array[i] < secmin) { thirdmin = secmin; secmin = array[i]; } /* Check if current element is less than then update third */ else if (array[i] < thirdmin) thirdmin = array[i]; } cout << "First min = " << firstmin << "\n" ; cout << "Second min = " << secmin << "\n" ; cout << "Third min = " << thirdmin << "\n" ; } // Driver code int main() { int array[] = {4, 9, 1, 32, 12}; int n = sizeof (array) / sizeof (array[0]); Print3Smallest(array, n); return 0; } |
Java
// Java program to find the first, second // and third minimum element in an array import java.util.*; public class GFG { static void Print3Smallest( int array[], int n) { int firstmin = Integer.MAX_VALUE; int secmin = Integer.MAX_VALUE; int thirdmin = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++) { /* Check if current element is less than firstmin, then update first, second and third */ if (array[i] < firstmin) { thirdmin = secmin; secmin = firstmin; firstmin = array[i]; } /* Check if current element is less than secmin then update second and third */ else if (array[i] < secmin) { thirdmin = secmin; secmin = array[i]; } /* Check if current element is less than then update third */ else if (array[i] < thirdmin) thirdmin = array[i]; } System.out.println( "First min = " + firstmin ); System.out.println( "Second min = " + secmin ); System.out.println( "Third min = " + thirdmin ); } // Driver code public static void main(String[] args) { int array[] = { 4 , 9 , 1 , 32 , 12 }; int n = array.length; Print3Smallest(array, n); } } // This code is contributed by // Sam007 |
Python3
# A Python program to find the first, # second and third minimum element # in an array MAX = 100000 def Print3Smallest(arr, n): firstmin = MAX secmin = MAX thirdmin = MAX for i in range ( 0 , n): # Check if current element # is less than firstmin, # then update first,second # and third if arr[i] < firstmin: thirdmin = secmin secmin = firstmin firstmin = arr[i] # Check if current element is # less than secmin then update # second and third elif arr[i] < secmin: thirdmin = secmin secmin = arr[i] # Check if current element is # less than,then update third elif arr[i] < thirdmin: thirdmin = arr[i] print ( "First min = " , firstmin) print ( "Second min = " , secmin) print ( "Third min = " , thirdmin) # driver program arr = [ 4 , 9 , 1 , 32 , 12 ] n = len (arr) Print3Smallest(arr, n) # This code is contributed by Shrikant13. |
C#
// C# program to find the first, second // and third minimum element in an array using System; class GFG { static void Print3Smallest( int []array, int n) { int firstmin = int .MaxValue; int secmin = int .MaxValue; int thirdmin = int .MaxValue; for ( int i = 0; i < n; i++) { /* Check if current element is less than firstmin, then update first, second and third */ if (array[i] < firstmin) { thirdmin = secmin; secmin = firstmin; firstmin = array[i]; } /* Check if current element is less than secmin then update second and third */ else if (array[i] < secmin) { thirdmin = secmin; secmin = array[i]; } /* Check if current element is less than then update third */ else if (array[i] < thirdmin) thirdmin = array[i]; } Console.WriteLine( "First min = " + firstmin ); Console.WriteLine( "Second min = " + secmin ); Console.WriteLine( "Third min = " + thirdmin ); } // Driver code static void Main() { int []array = new int []{4, 9, 1, 32, 12}; int n = array.Length; Print3Smallest(array, n); } } // This code is contributed by Sam007 |
PHP
<?php // php program to find the first, second // and third minimum element in an array function Print3Smallest( $array , $n ) { $MAX = 100000; $firstmin = $MAX ; $secmin = $MAX ; $thirdmin = $MAX ; for ( $i = 0; $i < $n ; $i ++) { /* Check if current element is less than firstmin, then update first, second and third */ if ( $array [ $i ] < $firstmin ) { $thirdmin = $secmin ; $secmin = $firstmin ; $firstmin = $array [ $i ]; } /* Check if current element is less than secmin then update second and third */ else if ( $array [ $i ] < $secmin ) { $thirdmin = $secmin ; $secmin = $array [ $i ]; } /* Check if current element is less than then update third */ else if ( $array [ $i ] < $thirdmin ) $thirdmin = $array [ $i ]; } echo "First min = " . $firstmin . "\n" ; echo "Second min = " . $secmin . "\n" ; echo "Third min = " . $thirdmin . "\n" ; } // Driver code $array = array (4, 9, 1, 32, 12); $n = sizeof( $array ) / sizeof( $array [0]); Print3Smallest( $array , $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find the first, second // and third minimum element in an array let MAX = 100000 function Print3Smallest( array, n) { let firstmin = MAX, secmin = MAX, thirdmin = MAX; for (let i = 0; i < n; i++) { /* Check if current element is less than firstmin, then update first, second and third */ if (array[i] < firstmin) { thirdmin = secmin; secmin = firstmin; firstmin = array[i]; } /* Check if current element is less than secmin then update second and third */ else if (array[i] < secmin) { thirdmin = secmin; secmin = array[i]; } /* Check if current element is less than then update third */ else if (array[i] < thirdmin) thirdmin = array[i]; } document.write( "First min = " + firstmin + "</br>" ); document.write( "Second min = " + secmin + "</br>" ); document.write( "Third min = " + thirdmin + "</br>" ); } // Driver program let array = [4, 9, 1, 32, 12]; let n = array.length; Print3Smallest(array, n); </script> |
Output
First min = 1 Second min = 4 Third min = 9
Time Complexity: O(n)
Auxiliary Space: O(1)