1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Approach 1 (Naive Approach)
3.1.1.
C++ Code
3.2.
Approach 2 (Efficient Method)
3.2.1.
C++ Code
3.2.2.
Python Code
4.
4.1.
What is the space complexity of the above approach?
4.2.
What sorting algorithm does python use?
4.3.
Can the above problem be solved with a time complexity less than O(n)?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Find the first, second, and third minimum elements in an array

1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

In this article, we will look at the problem of finding the first three minimum elements in an array. We will look at two different approaches to solve this problem and compare their time complexities to find out the efficient method.

## Problem Statement

Given an array of n elements, we are to find the first, second, and third minimum elements in the array. The first minimum is the array's minimum, the second is a minimum but larger than the first, and the third is a minimum but larger than the second.

Examples:

Input:

``24 15 7 6 9 10 12``

Output:

``````First Min Element: 6
Second Min Element: 7
Third Min Element: 9``````

Input:

``14 3 79 6 5``

Output:

``````First Min Element: 3
Second Min Element: 5
Third Min Element: 6``````

Must Recommended topic, kth largest element in an array and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Solution Approach

This problem can be solved in a number of ways. In this article, we will discuss two approaches: a naive method and an efficient method.

### Approach 1 (Naive Approach)

In this approach, we will sort the array and pick the first three elements as the output. The algorithm is as follows:

Step 1: Sort the array

Step 2: Print the first three elements

The Time complexity of this algorithm is O(n*logn), as the first step (i.e., sorting) is O(n*logn), and the second step is O(1). Therefore, the overall time complexity is O(n*logn). The implementation code for the above approach is as follows:

#### C++ Code

``````#include<bits/stdc++.h>
using namespace std;

// Function to find first three minimum elements in a given array
void findFirstThreeMin(int arr[],int n){
// Sort the Array
sort(arr,arr+n);

// Now print the first three elements
cout<<"First Min Element: "<<arr[0]<<endl; // First Min Element
cout<<"Second Min Element: "<<arr[1]<<endl; // Second Min Element
cout<<"Third Min Element: "<<arr[2]<<endl; // Third Min Element

}

int main(){
// Input array
const int n = 7; // number of elements in array
int arr [n] = {15, 66, 75, 42, 47, 9, 6};

findFirstThreeMin(arr,n); // Invoking the function to find first three minimum elements

return 0;
}
Python Code
# Function to find first three minimum elements in a given array
def findFirstThreeMin(arr,n):
# Sort the Array
arr.sort()
# now print the first three elements
print("First Min Element: " + str(arr[0])) # first min element
print("Second Min Element: " + str(arr[1])) # second min element
print("Third Min Element: " + str(arr[2])) # third min element

if __name__=="__main__":
# Input array
n= 7 # length of the array
arr = [15, 66, 75, 42, 47, 9, 6]
findFirstThreeMin(arr,n) # invoking the function to find first three minimum elements``````

Output:

``````First Min Element: 6
Second Min Element: 9
Third Min Element: 15``````

### Approach 2 (Efficient Method)

In this approach, we will iterate over the array and compare the elements to get the three minimum elements.

Algorithm:

``````Initialize firstElement, secondElement, thirdElement to INT_MAX
// now iterate over the array to find all the elements
for i in 0...n-1:
if arr[i] < firstELement:
thirdElement = secondElement
secondElement = firstElement
firstElement = arr[i]
else if arr[i] < secondElement:
thirdElement = secondElement
secondElement = arr[i]
else if arr[i] < thirdElement:
thirdElement = arr[i]

Print the three elements.``````

As we are iterating over the array once, the time complexity of this approach is O(n). The implementation code for the above approach is as follows:

#### C++ Code

``````#include<bits/stdc++.h>
using namespace std;

// Function to find first three minimum elements in a given array
void findFirstThreeMin(int arr[],int n){
int first_min = INT_MAX, second_min = INT_MAX, third_min = INT_MAX;

for(int i=0;i<n;i++){
int curr_element = arr[i];
if(curr_element<first_min){
third_min=second_min;
second_min=first_min;
first_min=curr_element;
}
else if(curr_element < second_min){
third_min=second_min;
second_min = curr_element;
}
else if(curr_element< third_min){
third_min = curr_element;
}
}

// Now print the three minimum elements
cout<<"First Min Element: "<<first_min<<endl; // First Min Element
cout<<"Second Min Element: "<<second_min<<endl; // Second Min Element
cout<<"Third Min Element: "<<third_min<<endl;

}

int main(){
// Input array
const int n = 7; // number of elements in array
int arr [n] = {15, 66, 75, 42, 47, 9, 6};

findFirstThreeMin(arr,n); // Invoking the function to find first three minimum elements

return 0;
}``````

#### Python Code

``````# Function to find first three minimum elements in a given array
def findFirstThreeMin(arr,n):
first_min = 1e9
second_min = 1e9
third_min = 1e9

for i in range(n):
curr_element = arr[i]
if(curr_element<first_min):
third_min=second_min
second_min=first_min
first_min=curr_element
elif(curr_element < second_min):
third_min=second_min
second_min = curr_element

elif(curr_element< third_min):
third_min = curr_element

#  Now print the three minimum elements
print("First Min Element: " + str(first_min)) # first min element
print("Second Min Element: " + str(second_min)) # second min element
print("Third Min Element: " + str(third_min)) # third min element

if __name__=="__main__":
# Input array
n= 7 # length of the array
arr = [15, 66, 75, 42, 47, 9, 6]
findFirstThreeMin(arr,n) # invoking the function to find first three minimum elements``````

Output:

``````First Min Element: 6
Second Min Element: 9
Third Min Element: 15``````

Check out this problem - Maximum Product Subarray

#### What is the space complexity of the above approach?

The space complexity of the above approach is O(1), as we are only using the unit amount of extra space. This unit space is being used to store the values of the variables firstElement, secondElement, and thirdElement.

#### What sorting algorithm does python use?

The default list.sort() of python uses the Tim Sort Algorithm. It is a sorting algorithm based on the Insertion Sort and the Merge Sort. The time complexity of this algorithm is O(nlogn).

#### Can the above problem be solved with a time complexity less than O(n)?

As the array is not sorted, we need to iterate over the array at least once before deciding upon the output. Iterating over the array takes O(n) time. Therefore it's not possible to solve the problem in time less than O(n).

## Conclusion

In this article, we have extensively discussed the problem of finding the first three minimum elements in an array. We hope that this blog has helped you enhance your knowledge regarding finding minimum elements in an array, to learn more, check out the awesome content on the Coding Ninjas Website,
Android DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test Series

Recommended problems -

Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass