How to get largest and smallest number in an Array?

Given an array arr[] of length N, The task is to find the maximum and the minimum number in the array.

Examples:

Input: arr[] = {1, 2, 3, 4, 5}
Output: Maximum is: 5
Minimum is: 1
Explanation: The maximum of the array is 5 
and the minimum of the array is 1.

Input: arr[] = {5, 3, 7, 4, 2}
Output: Maximum is: 7
Minimum is: 2

Approach 1(Greedy): The problem can be solved using the greedy approach:

The solution is to compare each array element for minimum and maximum elements by considering a single item at a time.

Follow the steps to solve the problem:

  • Create a variable mini/maxi and initialize it with the value at index zero of the array.
  • Iterate over the array and compare if the current element is greater than the maxi or less than the mini.
  • Update the mini/maxi element with the current element so that the minimum/maximum element is stored in the mini/maxi variable.
  • Return the mini/maxi variable.

Below is the implementation of the above idea:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

pair<int, int> findMinMax(int arr[], int n)

{

    int mini = arr[0];

    int maxi = arr[0];

  

    for (int i = 0; i < n; i++) {

        if (arr[i] < mini) {

            mini = arr[i];

        }

        else if (arr[i] > maxi) {

            maxi = arr[i];

        }

    }

    return { mini, maxi };

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    pair<int, int> ans = findMinMax(arr, N);

    cout << "Maximum is: " << ans.second << endl;

    cout << "Minimum is: " << ans.first;

    return 0;

}
Output

Maximum is: 5
Minimum is: 1

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach 2(Library Function): The problem can be solved using the library functions provided in different programming languages.

We can use min_element() and max_element() to find the minimum and maximum elements of the array in C++.

Below is the implementation of the above idea:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int findMin(int arr[], int n)

{

    return *min_element(arr, arr + n);

}

  

int findMax(int arr[], int n)

{

    return *max_element(arr, arr + n);

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << "Maximum is: " << findMax(arr, N) << endl;

    cout << "Minimum is: " << findMin(arr, N);

    return 0;

}
Output

Maximum is: 5
Minimum is: 1

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach 3(Minimum comparisons): To solve the problem with minimum number of comparisons, follow the below steps:

  • If N is odd then initialize mini and maxi as the first element. 
  • If N is even then initialize mini and maxi as minimum and maximum of the first two elements respectively. 
  • For the rest of the elements, pick them in pairs and compare
    • Maximum and minimum with maxi and mini respectively. 

The total number of comparisons will be:

If N is odd: 3*(N – 1)/2  
If N is even: 1 Initial comparison for initializing min and max, and 3(N – 2)/2 comparisons for rest of the elements 
=  1 + 3*(N – 2) / 2 = 3N / 2 – 2

Below is the implementation of the above idea:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

struct Pair {

    int min;

    int max;

};

  

struct Pair getMinAndMax(int arr[], int n)

{

    struct Pair minmax;

    int i;

  

    

    

    

    if (n % 2 == 0) {

        if (arr[0] > arr[1]) {

            minmax.max = arr[0];

            minmax.min = arr[1];

        }

        else {

            minmax.min = arr[0];

            minmax.max = arr[1];

        }

  

        

        i = 2;

    }

  

    

    

    

    else {

        minmax.min = arr[0];

        minmax.max = arr[0];

  

        

        i = 1;

    }

  

    

    

    

    while (i < n - 1) {

        if (arr[i] > arr[i + 1]) {

            if (arr[i] > minmax.max)

                minmax.max = arr[i];

  

            if (arr[i + 1] < minmax.min)

                minmax.min = arr[i + 1];

        }

        else {

            if (arr[i + 1] > minmax.max)

                minmax.max = arr[i + 1];

  

            if (arr[i] < minmax.min)

                minmax.min = arr[i];

        }

  

        

        

        i += 2;

    }

    return minmax;

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

    

    Pair minmax = getMinAndMax(arr, N);

  

    cout << "Maximum is: " << minmax.max << endl;

    cout << "Minimum is: " << minmax.min;

    return 0;

}
Output

Maximum is: 5
Minimum is: 1

Time Complexity: O(N)
Auxiliary Space: O(1)

By Julio MarchiPosted on