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
Click here to know about Array in Python here.
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
Frequently Asked Questions
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 Development, Coding Ninjas Studio Problems, Coding Ninjas Studio Interview Bundle, Coding Ninjas Studio Interview Experiences, Coding Ninjas Courses, Coding Ninjas Studio Contests, and Coding Ninjas Studio Test Series.
Recommended problems -
Do upvote our blog to help other ninjas grow. Happy Coding!