Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author Pradeep Kumar
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.

Learn more about Array in Java here.

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


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

Previous article
Minimum Number of Subsets with Distinct Elements
Next article
Find an array element such that all elements are divisible by it
Live masterclass