Finding the minimum and maximum element in an array

Problem Statement :-

Finding the minimum and maximum element in a given array

Example 1: We will be given an array and we need to output two space separated integers. First integer should be the minimum number in the array and the second interger should be the maximum number in the array.

Input: {15, 1, -9, 76, 28, 1}
Output: -9 76
Explanation: -9 is the smallest integer and 76 is the largest
integer in the given array.

Solution:-
The above problem can be solved in multiple ways, but I will be discussing two basic approaches to solve the problem.

Using Sorting:-

In this method, we need to sort the array first. Let’s say we have sorted the array in ascending order. This means that the first element of the array will now be the minimum element and the last element in the array would be maximum element.

The solution is easy to implement and really easy to understand as well, but the only issue that we might face during the interview will be its execution time. Techniques like merge sort, and quick sort take O(NlogN) time , where N is the number of elements in the array. We don’t need to use any extra space, so the space complexity will be constant O(1) .

Here is the solution to find the maximum and minimum element using sorting

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

int main(){
	int N;
	cin>>N; //taking the size of array
	vector<int> V(N); //declaring an array of size N
	//taking array as input
	for(int i=0; i<N; ++i){
		cin>>V[i];
	}	
	//sorting the array
	//for now I will be using sort() method of C++ STL
	sort(V.begin(), V.end());
	
	//displaying the output
	cout<<V[0]<<" "<<V[V.size()-1]<<"\n";
	return 0;
}

Optimal Approach

This method will help us solve the problem in O(N) time and using constant space, i.e space complexity will be O(1).

To do so, I will first take two variables and store the first value of the given array in both of them. Now we will traverse the array from second element till the last. In each iteration we will compare and store the minimum element in first variable and store the maximum element in the second variable.

Here is the solution to do so,

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

int main(){
	int N;
	cin>>N; //taking the size of array
	vector<int> V(N); //declaring an array of size N
	//taking array as input
	for(int i=0; i<N; ++i){
		cin>>V[i];
	}	
	
	int minElement = V[0];
	int maxElement = V[0];
	
	//traversing the array
	for(int i=1; i<N; ++i){
		//comparison to store the maximum element
		if(V[i] > maxElement) {
			maxElement = V[i];
		}
		//comparison to store the minimum element
		if(V[i] < minElement){
			minElement = V[i];
		}
	}
	// we now have the values of minimum and maximum element stored in the two variables
	cout<<minElement<<" "<<maxElement<<"\n";
	return 0;
}

So these were the two solutions to find minimum and maximum element in an non-sorted array.

You can follow me on Github to find solutions to many more DSA problems.

Thank you,
Gaurav Goyal

Github
LinkedIn