Find Maximum and minimum in an array

Find the Maximum and minimum of an array using a minimum number of comparisons.

For every problem we will have multiple solutions, everyone can have their own solution.

For this problem here we have three approaches to solve this problem - 

  1. First Approach "Simple Linear Search"
  2. Second Approach "Tournament Method (Divide and Conquer)"
  3. The third Approach "Compare in Pairs"

  1. First Approach "Simple Linear Search" 
Description - 
First, initialize values of minValue and maxValue as minimum and maximum of the first two elements respectively. Now Starting from 3rd, compare each element with maxValue and minValue, and change maxValue and minValue accordingly (i.e., if the element is smaller than minValue then change minValue, else if the element is greater than maxValue then change maxValue, else ignore the element) 

package javaoneworld.learndsa.problems;

public class JavaOneWorldDSA {
    /* Class Pair is used to return two values from getMinMax() */
    static class Pair {

        int minValue;
        int maxValue;

    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new  Pair();
        int i;

        /*If there is only one element then return it as min and max both*/
        if (n == 1) {
            minmax.maxValue = arr[0];
            minmax.minValue = arr[0];
            return minmax;

        /* If there are more than one elements, then initialize min
    and max*/
        if (arr[0] > arr[1]) {
            minmax.maxValue = arr[0];
            minmax.minValue = arr[1];
        } else {
            minmax.maxValue = arr[1];
            minmax.minValue = arr[0];

        for (i = 2; i < n; i++) {
            if (arr[i] > minmax.maxValue) {
                minmax.maxValue = arr[i];
            } else if (arr[i] < minmax.minValue) {
                minmax.minValue = arr[i];

        return minmax;

    /* Testing the implemented program  */
    public static void main(String args[]) {
        int arr[] = {999, 98, 986, 56, 550, 7986};
        int arr_size = 6;
        Pair minMax = getMinMax(arr, arr_size);
        System.out.println("Minimum element is :"+ minMax.minValue);
        System.out.println("Maximum element is :"+ minMax.maxValue);


Time Complexity - O(n)

No comments:

Post a Comment