Find the smallest and second smallest element in an array
The problem at hand is to find the smallest and second smallest elements in an array of integers. This task involves iterating through the array and identifying the two smallest values present in it. This operation can be useful in various contexts, such as ranking students based on test scores or finding the lowest and second lowest prices in a dataset.
Problem Statement and Description
Given an array of integers, the objective is to determine the smallest and second smallest values present in the
array. For example, consider the array [10, 3, 44, 86, 8, 9, 4, 5, 7]
. The smallest element in this
array is 3, and the second smallest element is 4.
Idea to Solve the Problem
To find the smallest and second smallest elements in the array, we can iterate through the array while keeping track
of the two smallest values encountered so far. We'll initialize two variables, first
and
second
, to store these values. As we traverse the array, we'll compare each element with these
variables and update them accordingly. By the end of the iteration, we will have identified the smallest and second
smallest elements.
Pseudocode
find_smallest(arr, size):
if size < 2:
return
else:
first = INT_MAX
second = INT_MAX
for i from 0 to size-1:
if arr[i] < first:
second = first
first = arr[i]
else if arr[i] < second:
second = arr[i]
print "First smallest: ", first
print "Second smallest: ", second
Algorithm Explanation
- Check if the size of the array is less than 2. If so, there can't be a second smallest element, and we return.
- Initialize two variables,
first
andsecond
, toINT_MAX
. These will be used to store the smallest and second smallest elements. - Iterate through the array. For each element
arr[i]
:- Compare
arr[i]
withfirst
. If it's smaller thanfirst
, updatesecond
with the value offirst
and updatefirst
with the value ofarr[i]
. - If
arr[i]
is not smaller thanfirst
but is smaller thansecond
, updatesecond
with the value ofarr[i]
.
- Compare
- After the iteration, the
first
variable will contain the smallest element, and thesecond
variable will contain the second smallest element. - Print the values of
first
andsecond
.
Program
//C Program
//Find the smallest and second smallest element in an array
#include <stdio.h>
#include <limits.h>
void find_smallest(int arr[], int size)
{
if (size < 2)
{
return;
}
else
{
//Variable which is used to store the result
int first = INT_MAX;
int second = INT_MAX;
for (int i = 0; i < size; i++)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
}
//Display result
printf("First smallest : %d\n", first);
printf("Second smallest : %d\n", second);
}
}
int main()
{
//Define collection of array elements
int arr[] = {
10 , 3 , 44 , 86 , 8 , 9 , 4 , 5 , 7
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
find_smallest(arr, size);
return 0;
}
Output
First smallest : 3
Second smallest : 4
/*
Java Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
public void find_smallest(int[] arr, int size)
{
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int i = 0; i < size; i++)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
}
//Display result
System.out.print("First smallest : " + first + "\n");
System.out.print("Second smallest : " + second + "\n");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define collection of array elements
int[] arr = {
10,
3,
44,
86,
8,
9,
4,
5,
7
};
//Get the size of array
int size = arr.length;
obj.find_smallest(arr, size);
}
}
Output
First smallest : 3
Second smallest : 4
//Include header file
#include <iostream>
#include<limits.h>
using namespace std;
/*
C++ Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
public: void find_smallest(int arr[], int size)
{
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
int first = INT_MAX;
int second = INT_MAX;
for (int i = 0; i < size; i++)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
}
//Display result
cout << "First smallest : " << first << "\n";
cout << "Second smallest : " << second << "\n";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr[] = {
10 , 3 , 44 , 86 , 8 , 9 , 4 , 5 , 7
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.find_smallest(arr, size);
return 0;
}
Output
First smallest : 3
Second smallest : 4
//Include namespace system
using System;
/*
C# Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
public void find_smallest(int[] arr, int size)
{
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
int first = int.MaxValue;
int second = int.MaxValue;
for (int i = 0; i < size; i++)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
}
//Display result
Console.Write("First smallest : " + first + "\n");
Console.Write("Second smallest : " + second + "\n");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr = {
10 , 3 , 44 , 86 , 8 , 9 , 4 , 5 , 7
};
//Get the size of array
int size = arr.Length;
obj.find_smallest(arr, size);
}
}
Output
First smallest : 3
Second smallest : 4
<?php
/*
Php Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
public function find_smallest( $arr, $size)
{
if ($size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
$first = PHP_INT_MAX;
$second = PHP_INT_MAX;
for ($i = 0; $i < $size; $i++)
{
//compare the array element values
if ($first > $arr[$i])
{
if ($second > $first)
{
$second = $first;
}
$first = $arr[$i];
}
else if ($second > $arr[$i])
{
$second = $arr[$i];
}
}
echo "First smallest : ". $first ."\n";
echo "Second smallest : ". $second ."\n";
}
}
}
function main()
{
$obj = new MyArray();
//Define collection of array elements
$arr = array(10, 3, 44, 86, 8, 9, 4, 5, 7);
//Get the size of array
$size = count($arr);
$obj->find_smallest($arr, $size);
}
main();
Output
First smallest : 3
Second smallest : 4
/*
Node Js Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
find_smallest(arr, size)
{
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
var first = Number.MAX_VALUE;
var second = Number.MAX_VALUE;
for (var i = 0; i < size; i++)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
}
process.stdout.write("First smallest : " + first + "\n");
process.stdout.write("Second smallest : " + second + "\n");
}
}
}
function main()
{
var obj = new MyArray();
//Define collection of array elements
var arr = [10, 3, 44, 86, 8, 9, 4, 5, 7];
//Get the size of array
var size = arr.length;
obj.find_smallest(arr, size);
}
main();
Output
First smallest : 3
Second smallest : 4
import sys
#
# Python 3 Program
# Find the smallest and second smallest element in an array
class MyArray :
def find_smallest(self, arr, size) :
if (size <= 1) :
return
else :
# Variable which is used to store the result
first = sys.maxsize
second = sys.maxsize
i = 0
while (i < size) :
# compare the array element values
if (first > arr[i]) :
if (second > first) :
second = first
first = arr[i]
elif(second > arr[i]) :
second = arr[i]
i += 1
print("First smallest : ", first )
print("Second smallest : ", second )
def main() :
obj = MyArray()
# Define collection of array elements
arr = [10, 3, 44, 86, 8, 9, 4, 5, 7]
# Get the size of array
size = len(arr)
obj.find_smallest(arr, size)
if __name__ == "__main__": main()
Output
First smallest : 3
Second smallest : 4
# Ruby Program
# Find the smallest and second smallest element in an array
class MyArray
def find_smallest(arr, size)
if (size <= 1)
return
else
# Variable which is used to store the result
first = (2 ** (0. size * 8 - 2))
second = (2 ** (0. size * 8 - 2))
i = 0
while (i < size)
# compare the array element values
if (first > arr[i])
if (second > first)
second = first
end
first = arr[i]
elsif(second > arr[i])
second = arr[i]
end
i += 1
end
# Display result
print("First smallest : ", first ,"\n")
print("Second smallest : ", second ,"\n")
end
end
end
def main()
obj = MyArray.new()
# Define collection of array elements
arr = [10, 3, 44, 86, 8, 9, 4, 5, 7]
# Get the size of array
size = arr.length
obj.find_smallest(arr, size)
end
main()
Output
First smallest : 3
Second smallest : 4
/*
Scala Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
def find_smallest(arr: Array[Int], size: Int): Unit = {
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
var first: Int = Int.MaxValue;
var second: Int = Int.MaxValue;
var i: Int = 0;
while (i < size)
{
//compare the array element values
if (first > arr(i))
{
if (second > first)
{
second = first;
}
first = arr(i);
}
else if (second > arr(i))
{
second = arr(i);
}
i += 1;
}
//Display result
print("First smallest : " + first + "\n");
print("Second smallest : " + second + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define collection of array elements
var arr: Array[Int] = Array(10, 3, 44, 86, 8, 9, 4, 5, 7);
//Get the size of array
var size: Int = arr.length;
obj.find_smallest(arr, size);
}
}
Output
First smallest : 3
Second smallest : 4
/*
Swift Program
Find the smallest and second smallest element in an array
*/
class MyArray
{
func find_smallest(_ arr: [Int], _ size: Int)
{
if (size <= 1)
{
return;
}
else
{
//Variable which is used to store the result
var first: Int = Int.max;
var second: Int = Int.max;
var i: Int = 0;
while (i < size)
{
//compare the array element values
if (first > arr[i])
{
if (second > first)
{
second = first;
}
first = arr[i];
}
else if (second > arr[i])
{
second = arr[i];
}
i += 1;
}
print("First smallest : ", first );
print("Second smallest : ", second );
}
}
}
func main()
{
let obj: MyArray = MyArray();
//Define collection of array elements
let arr: [Int] = [10, 3, 44, 86, 8, 9, 4, 5, 7];
//Get the size of array
let size: Int = arr.count;
obj.find_smallest(arr, size);
}
main();
Output
First smallest : 3
Second smallest : 4
Time Complexity Analysis
The algorithm iterates through the array once, performing constant-time comparisons and updates for each element. Therefore, the time complexity of the algorithm is O(n), where n is the size of the input array. This linear time complexity ensures that the algorithm performs well even for larger input arrays.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment