Open In App

Maximum and minimum of an array using minimum number of comparisons

Last Updated : 25 Oct, 2025
Comments
Improve
Suggest changes
1.14k Likes
Like
Report
Try it on GfG Practice
redirect icon

Given an array of integers arr[], the task is to find the maximum and minimum elements in the array using the minimum number of comparisons.

Examples:

Input: arr[] = [3, 5, 4, 1, 9]
Output: [1, 9]
Explanation: The minimum element is 1, and the maximum element is 9.

Input: arr[] = [22, 14, 8, 17, 35, 3]
Output: [3, 35]
Explanation: The minimum element is 3, and the maximum element is 35.

Table of Content

[Naive Approach] By Sorting the array - O(n log n) Time and O(1) Space

The idea is to firstly sort the array in ascending order.
Once the array is sorted, the first element of the array will be the minimum element and the last element of the array will be the maximum element.

Number of Comparisons

The number of comparisons is equal to the number of comparisons made during the sorting process. For any comparison-based sorting algorithm, the minimum number of comparisons required in the worst case to sort an array of n elements is O(n log n). Hence, the number of comparisons made in this approach is O(n log n).

C++ 
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> findMinMax(vector<int>& arr) {
    vector<int> sortedArr = arr;
    
    // Sort array
    sort(sortedArr.begin(), sortedArr.end()); 
    return {sortedArr[0], sortedArr[sortedArr.size()-1]};
}

int main() {
    vector<int> arr = {3, 5, 4, 1, 9};
    vector<int> result = findMinMax(arr);
    cout << result[0] << " " << result[1] << endl;
    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    
    // Comparison function
    return (*(int*)a - *(int*)b); 
}

int* findMinMax(int arr[], int n) {
    static int result[2];
    int* sortedArr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) sortedArr[i] = arr[i];
    
     // Sort array
    qsort(sortedArr, n, sizeof(int), cmp);
    result[0] = sortedArr[0]; 
    result[1] = sortedArr[n-1];
    free(sortedArr);
    return result;
}

int main() {
    int arr[] = {3, 5, 4, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* result = findMinMax(arr, n);
    printf("%d %d\n", result[0], result[1]);
    return 0;
}
Java 
import java.util.ArrayList;
import java.util.Collections;

class GfG {
    public static ArrayList<Integer> findMinMax(int[] arr) {
        
        ArrayList<Integer> sortedArr = new ArrayList<>();
        for (int num : arr) {
            sortedArr.add(num);
        }
        
        // Sort ArrayList
        Collections.sort(sortedArr);
        
        ArrayList<Integer> result = new ArrayList<>();
        result.add(sortedArr.get(0));               
        result.add(sortedArr.get(sortedArr.size() - 1)); 
        
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 1, 9};
        ArrayList<Integer> result = findMinMax(arr);
        System.out.println(result.get(0) + " " + result.get(1));
    }
}
Python 
def findMinMax(arr):
    
    # Sort array
    sorted_arr = sorted(arr)
    return [sorted_arr[0], sorted_arr[-1]] 

if __name__ == "__main__":
    arr = [3, 5, 4, 1, 9]
    result = findMinMax(arr)
    print("%d %d" % (result[0], result[1]))
C# 
using System;
using System.Collections.Generic;
using System.Linq;

class GfG {
    public static List<int> FindMinMax(int[] arr) {

        List<int> sortedArr = arr.ToList();
        
        // Sort List
        sortedArr.Sort();
        
        // Create result List with min and max
        List<int> result = new List<int> { sortedArr[0], sortedArr[sortedArr.Count - 1] };
        
        return result;
    }

    public static void Main(string[] args) {
        int[] arr = { 3, 5, 4, 1, 9 };
        List<int> result = FindMinMax(arr);
        Console.WriteLine($"{result[0]} {result[1]}");
    }
}
JavaScript 
function findMinMax(arr) {
    
    //Sort array
    const sortedArr = [...arr].sort((a, b) => a - b);
    return [sortedArr[0], sortedArr[sortedArr.length-1]]; 
}

const arr = [3, 5, 4, 1, 9];
const result = findMinMax(arr);
console.log(`${result[0]} ${result[1]}`);

Output
1 9

[Better Approach I] Iterating the array - O(n) Time and O(1) Space

The idea is to perform a single traversal, firstly initialize two variables - mini as INT_MAX and maxi as INT_MIN, then traverse the array to update mini whenever a smaller element is encountered and to update maxi whenever a larger element is found.

Number of Comparisons:

  • Worst Case: 2 * n comparisons (n for minimum, n for maximum).
  • Best Case: 2 * n comparisons (no optimization possible).
C++ 
#include <vector>
#include <climits>
#include <iostream>
using namespace std;

vector<int> findMinMax(vector<int>& arr) {
    int n = arr.size();
    int mini = INT_MAX, maxi = INT_MIN;
    
    // Find minimum and maximum
    for (int i = 0; i < n; i++) { 
        if (arr[i] < mini) mini = arr[i];
        if (arr[i] > maxi) maxi = arr[i];
    }
    
    return {mini, maxi};
}

int main() {
    vector<int> arr = {3, 5, 4, 1, 9};
    vector<int> result = findMinMax(arr);
    cout << result[0] << " " << result[1] << endl;
    return 0;
}
C 
#include <stdio.h>
#include <limits.h>

int* findMinMax(int arr[], int n) {
    static int result[2];
    int mini = INT_MAX, maxi = INT_MIN;
    
    // Find minimum and maximum
    for (int i = 0; i < n; i++) { 
        if (arr[i] < mini) mini = arr[i];
        if (arr[i] > maxi) maxi = arr[i];
    }
    
    result[0] = mini; 
    result[1] = maxi; 
    return result;
}

int main() {
    int arr[] = {3, 5, 4, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* result = findMinMax(arr, n);
    printf("%d %d\n", result[0], result[1]);
    return 0;
}
Java 
import java.util.ArrayList;

class GfG {
    public static ArrayList<Integer> findMinMax(int[] arr) {
        int mini = Integer.MAX_VALUE;
        int maxi = Integer.MIN_VALUE;
        
        // Find minimum and maximum
        for (int num : arr) {
            if (num < mini) mini = num;
            if (num > maxi) maxi = num;
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        result.add(mini);
        result.add(maxi);
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 1, 9};
        ArrayList<Integer> result = findMinMax(arr);
        System.out.println(result.get(0) + " " + result.get(1));
    }
}
Python 
def findMinMax(arr):
    mini = float('inf') 
    maxi = float('-inf')
    
    # Find minimum and maximum
    for num in arr: 
        if num < mini:
            mini = num
        if num > maxi:
            maxi = num
    
    return [mini, maxi]

if __name__ == "__main__":
    arr = [3, 5, 4, 1, 9]
    result = findMinMax(arr)
    print(result[0], result[1])
C# 
using System;
using System.Collections.Generic;

class GfG {
    public static List<int> FindMinMax(int[] arr) {
        int mini = int.MaxValue;
        int maxi = int.MinValue;
        
        // Find minimum and maximum
        foreach (int num in arr) {
            if (num < mini) mini = num;
            if (num > maxi) maxi = num;
        }
        
        List<int> result = new List<int> { mini, maxi };
        return result;
    }

    public static void Main(string[] args) {
        int[] arr = { 3, 5, 4, 1, 9 };
        List<int> result = FindMinMax(arr);
        Console.WriteLine($"{result[0]} {result[1]}");
    }
}
JavaScript 
function findMinMax(arr) {
    let mini = Number.MAX_SAFE_INTEGER;
    let maxi = Number.MIN_SAFE_INTEGER;
    
    // Find minimum and maximum
    for (let num of arr) { 
        if (num < mini) mini = num;
        if (num > maxi) maxi = num;
    }
    
    console.log(`${mini} ${maxi}`);
}

const arr = [3, 5, 4, 1, 9];
findMinMax(arr);

Output
1 9

[Better Approach II] Dividing array in two parts - O(n) Time and O(log n) Space

This method recursively divides the array until it can no longer be split. If a segment contains only one element, that element is both the minimum and maximum. If it contains two elements, they are compared directly. For larger segments, the method finds the min and max in each half, then combines the results by taking the smaller of the two minimums and the larger of the two maximums.

Number of Comparisons (Simplified)

Let T(n) be the number of comparisons needed for an array of size n.

  • If there's 1 element: T(1) = 0 (no comparison needed).
  • If there are 2 elements: T(2) = 1 (just 1 comparison).
  • For larger arrays: the method splits the array, recursively compares each half, and adds 2 comparisons to combine results:
    T(n) = T(floor(n / 2)) + T(ceil(n / 2)) + 2

When n is a power of 2, solving this gives:
T(n) = (3 * n) / 2 - 2

Below is the implementation of the above approach:

C++ 
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> getMinMax(vector<int>& arr, int low, int high) {
    vector<int> result(2);
    
    // Base case: single element
    if (low == high) { 
        result[0] = arr[low];
        result[1] = arr[low];
        return result;
    }
    
    // Base case: two elements
    if (high == low + 1) { 
        if (arr[low] < arr[high]) {
            result[0] = arr[low];
            result[1] = arr[high];
        } else {
            result[0] = arr[high];
            result[1] = arr[low];
        }
        return result;
    }
    
    int mid = (low + high) / 2;
    
    // Recurse on left half
    vector<int> left = getMinMax(arr, low, mid); 
    
    // Recurse on right half
    vector<int> right = getMinMax(arr, mid + 1, high); 
    
    // Combine min
    result[0] = min(left[0], right[0]); 
    
    // Combine max
    result[1] = max(left[1], right[1]); 
    
    return result;
}

vector<int> findMinMax(vector<int>& arr) {
    return getMinMax(arr, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {3, 5, 4, 1, 9};
    vector<int> result = findMinMax(arr);
    cout << result[0] << " " << result[1] << endl;
    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

int* getMinMax(int arr[], int low, int high) {
    static int result[2];
    
    // Base case: single element
    if (low == high) {
        result[0] = arr[low];
        result[1] = arr[low];
        return result;
    }
    
    // Base case: two elements
    if (high == low + 1) {
        if (arr[low] < arr[high]) {
            result[0] = arr[low];
            result[1] = arr[high];
        } else {
            result[0] = arr[high];
            result[1] = arr[low];
        }
        return result;
    }
    
    int mid = (low + high) / 2;
    
    // Recurse on left half
    int* left = getMinMax(arr, low, mid);   
    
    // Recurse on right half
    int* right = getMinMax(arr, mid + 1, high);
    
    // Combine min
    result[0] = left[0] < right[0] ? left[0] : right[0]; 
    
    // Combine max
    result[1] = left[1] > right[1] ? left[1] : right[1]; 
    
    return result;
}

int* findMinMax(int arr[], int n) {
    return getMinMax(arr, 0, n - 1);
}

int main() {
    int arr[] = {3, 5, 4, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* result = findMinMax(arr, n);
    printf("%d %d\n", result[0], result[1]);
    return 0;
}
Java 
import java.util.ArrayList;
import java.util.Arrays;

public class MinMaxDivideConquer {
    
    public static ArrayList<Integer> getMinMax(ArrayList<Integer> arr, int low, int high) {
        ArrayList<Integer> result = new ArrayList<>(Arrays.asList(0, 0));

        // Base case: one element
        if (low == high) {
            result.set(0, arr.get(low));  
            result.set(1, arr.get(low)); 
            return result;
        }

        // Base case: two elements
        if (high == low + 1) {
            if (arr.get(low) < arr.get(high)) {
                result.set(0, arr.get(low));   
                result.set(1, arr.get(high));  
            } else {
                result.set(0, arr.get(high));
                result.set(1, arr.get(low));
            }
            return result;
        }

        // Recursive case: divide array into two halves
        int mid = (low + high) / 2;
        ArrayList<Integer> left = getMinMax(arr, low, mid);
        ArrayList<Integer> right = getMinMax(arr, mid + 1, high);

        // Combine results
        int min = Math.min(left.get(0), right.get(0));
        int max = Math.max(left.get(1), right.get(1));
        result.set(0, min);
        result.set(1, max);

        return result;
    }

    public static ArrayList<Integer> findMinMax(ArrayList<Integer> arr) {
        return getMinMax(arr, 0, arr.size() - 1);
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(3, 5, 4, 1, 9));
        ArrayList<Integer> result = findMinMax(arr);
        System.out.println(result.get(0) + " " + result.get(1));
    }
}
Python3 
def get_min_max(arr, low, high):
    result = [0, 0]
    
    # Base case: single element
    if low == high:
        result[0] = arr[low]
        result[1] = arr[low]
        return result
    
    # Base case: two elements
    if high == low + 1:
        if arr[low] < arr[high]:
            result[0] = arr[low]
            result[1] = arr[high]
        else:
            result[0] = arr[high]
            result[1] = arr[low]
        return result
    
    mid = (low + high) // 2
    
    # Recurse on left half
    left = get_min_max(arr, low, mid) 
    
    # Recurse on right half
    right = get_min_max(arr, mid + 1, high)  
    
    # Combine min
    result[0] = min(left[0], right[0])  
    
    # Combine max
    result[1] = max(left[1], right[1])  
    
    return result

def find_min_max(arr):
    return get_min_max(arr, 0, len(arr) - 1)

if __name__ == "__main__":
    arr = [3, 5, 4, 1, 9]
    result = find_min_max(arr)
    print("%d %d" % (result[0], result[1]))
C# 
using System;
using System.Collections.Generic;

class Program{
    static List<int> GetMinMax(List<int> arr, int low, int high)
    {
        //Base case: Single Element
        if (low == high)
            return new List<int> { arr[low], arr[low] };
            
        //Base case: Two Elements
        if (high == low + 1)
        {
            if (arr[low] < arr[high])
                return new List<int> { arr[low], arr[high] };
            else
                return new List<int> { arr[high], arr[low] };
        }

        int mid = (low + high) / 2;
        var left = GetMinMax(arr, low, mid);
        var right = GetMinMax(arr, mid + 1, high);

        return new List<int> {
            Math.Min(left[0], right[0]),
            Math.Max(left[1], right[1])
        };
    }

    static List<int> FindMinMax(List<int> arr) => GetMinMax(arr, 0, arr.Count - 1);

    static void Main()
    {
        var arr = new List<int> { 3, 5, 4, 1, 9 };
        var result = FindMinMax(arr);
        Console.WriteLine($"{result[0]} {result[1]}");
    }
}
JavaScript 
function getMinMax(arr, low, high) {
    
    //Base Case: Single Element
    if (low === high) 
        return [arr[low], arr[low]];
        
    //Base Case: Two Elements
    if (high === low + 1) {
        return arr[low] < arr[high] 
            ? [arr[low], arr[high]] 
            : [arr[high], arr[low]];
    }

    const mid = Math.floor((low + high) / 2);
    const left = getMinMax(arr, low, mid);
    const right = getMinMax(arr, mid + 1, high);

    return [
        Math.min(left[0], right[0]),
        Math.max(left[1], right[1])
    ];
}

function findMinMax(arr) {
    return getMinMax(arr, 0, arr.length - 1);
}

const arr = [3, 5, 4, 1, 9];
const result = findMinMax(arr);
console.log(result[0], result[1]);

Output
1 9

[Optimal Approach] Comparing in pairs - O(n) Time and O(1) Space

This approach finds the smallest and largest numbers in a list by reducing the number of comparisons. If the list has an odd number of elements, it initializes both the minimum and maximum with the first element. If it has an even number, it compares the first two elements to set the initial min and max.

It then processes the remaining elements in pairs. For each pair, it identifies the smaller and larger number, then updates the current minimum and maximum accordingly. After all pairs are checked, the final minimum and maximum values are returned.

Number of Comparisons:

If n is odd:

  • First element sets both min and max (no comparison).
  • Remaining n - 1 elements are processed in pairs.
  • Each pair takes 3 comparisons (between elements, and with min and max).
  • Total comparisons: 3 * (n - 1) / 2.

If n is even:

  • First two elements compared once to set min and max.
  • Remaining n - 2 elements processed in pairs (3 comparisons per pair).
  • Total comparisons: 1 + 3 * (n - 2) / 2 = (3 * n) / 2 - 2.

Below is the implementation of the above approach:

C++ 
#include <vector>
#include <climits>
#include <iostream>
using namespace std;

vector<int> findMinMax(const vector<int>& arr) {
    int n = arr.size();
    int mini, maxi, i;

    // Initialize min and max
    if (n % 2 == 1) {
        mini = maxi = arr[0];
        i = 1;
    } else {
        if (arr[0] < arr[1]) {
            mini = arr[0];
            maxi = arr[1];
        } else {
            mini = arr[1];
            maxi = arr[0];
        }
        i = 2;
    }

    // Process elements in pairs
    while (i < n - 1) {
        if (arr[i] < arr[i + 1]) {
            mini = min(mini, arr[i]);
            maxi = max(maxi, arr[i + 1]);
        } else {
            mini = min(mini, arr[i + 1]);
            maxi = max(maxi, arr[i]);
        }
        i += 2;
    }

    return {mini, maxi};
}

int main() {
    vector<int> arr = {3, 5, 4, 1, 9};
    vector<int> result = findMinMax(arr);
    if (!result.empty()) {
        cout << result[0] << " " << result[1] << endl;
    }
    return 0;
}
C 
#include <stdio.h>

int* findMinMax(int arr[], int n) {
    static int result[2];
    int mini, maxi, i;

    // Initialize min and max
    if (n % 2 == 1) {
        mini = maxi = arr[0];
        i = 1;
    } else {
        if (arr[0] < arr[1]) {
            mini = arr[0];
            maxi = arr[1];
        } else {
            mini = arr[1];
            maxi = arr[0];
        }
        i = 2;
    }

    // Process elements in pairs
    while (i < n - 1) {
        if (arr[i] < arr[i + 1]) {
            if (arr[i] < mini) mini = arr[i];
            if (arr[i + 1] > maxi) maxi = arr[i + 1];
        } else {
            if (arr[i + 1] < mini) mini = arr[i + 1];
            if (arr[i] > maxi) maxi = arr[i];
        }
        i += 2;
    }

    result[0] = mini;
    result[1] = maxi;
    return result;
}

int main() {
    int arr[] = {3, 5, 4, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* result = findMinMax(arr, n);
    printf("%d %d\n", result[0], result[1]);
    return 0;
}
Java 
import java.util.ArrayList;
import java.util.Arrays;

public class MinMaxFinder {
    public static void findMinMax(ArrayList<Integer> arr, ArrayList<Integer> result) {
        int n = arr.size();
        int mini, maxi, i;

        // Initialize min and max
        if (n % 2 == 1) {
            mini = maxi = arr.get(0);
            i = 1;
        } else {
            if (arr.get(0) < arr.get(1)) {
                mini = arr.get(0);
                maxi = arr.get(1);
            } else {
                mini = arr.get(1);
                maxi = arr.get(0);
            }
            i = 2;
        }

        // Process elements in pairs
        while (i < n - 1) {
            if (arr.get(i) < arr.get(i + 1)) {
                mini = Math.min(mini, arr.get(i));
                maxi = Math.max(maxi, arr.get(i + 1));
            } else {
                mini = Math.min(mini, arr.get(i + 1));
                maxi = Math.max(maxi, arr.get(i));
            }
            i += 2;
        }

        result.add(mini);
        result.add(maxi);
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(3, 5, 4, 1, 9));
        ArrayList<Integer> result = new ArrayList<>();
        findMinMax(arr, result);
        System.out.println(result.get(0) + " " + result.get(1));
    }
}
Python 
def find_min_max(arr):
    n = len(arr)

    # Initialize min and max
    if n % 2 == 1:
        mini = maxi = arr[0]
        i = 1
    else:
        if arr[0] < arr[1]:
            mini = arr[0]
            maxi = arr[1]
        else:
            mini = arr[1]
            maxi = arr[0]
        i = 2

    # Process elements in pairs
    while i < n - 1:
        if arr[i] < arr[i + 1]:
            mini = min(mini, arr[i])
            maxi = max(maxi, arr[i + 1])
        else:
            mini = min(mini, arr[i + 1])
            maxi = max(maxi, arr[i])
        i += 2

    return [mini, maxi]

def main():
    arr = [3, 5, 4, 1, 9]
    result = find_min_max(arr)
    print(result[0], result[1])

if __name__ == "__main__":
    main()
C# 
using System;
using System.Collections.Generic;

class GfG {
    static List<int> FindMinMax(List<int> arr) {
        int n = arr.Count;
        int mini, maxi, i;

        // Initialize min and max
        if (n % 2 == 1) {
            mini = maxi = arr[0];
            i = 1;
        } else {
            if (arr[0] < arr[1]) {
                mini = arr[0];
                maxi = arr[1];
            } else {
                mini = arr[1];
                maxi = arr[0];
            }
            i = 2;
        }

        // Process elements in pairs
        while (i < n - 1) {
            if (arr[i] < arr[i + 1]) {
                mini = Math.Min(mini, arr[i]);
                maxi = Math.Max(maxi, arr[i + 1]);
            } else {
                mini = Math.Min(mini, arr[i + 1]);
                maxi = Math.Max(maxi, arr[i]);
            }
            i += 2;
        }

        return new List<int> { mini, maxi };
    }

    static void Main() {
        List<int> arr = new List<int> { 3, 5, 4, 1, 9 };
        var result = FindMinMax(arr);
        Console.WriteLine($"{result[0]} {result[1]}");
    }
}
JavaScript 
function findMinMax(arr) {
    const n = arr.length;
    let mini, maxi, i;

    // Initialize min and max
    if (n % 2 === 1) {
        mini = maxi = arr[0];
        i = 1;
    } else {
        if (arr[0] < arr[1]) {
            mini = arr[0];
            maxi = arr[1];
        } else {
            mini = arr[1];
            maxi = arr[0];
        }
        i = 2;
    }

    // Process elements in pairs
    while (i < n - 1) {
        if (arr[i] < arr[i + 1]) {
            mini = Math.min(mini, arr[i]);
            maxi = Math.max(maxi, arr[i + 1]);
        } else {
            mini = Math.min(mini, arr[i + 1]);
            maxi = Math.max(maxi, arr[i]);
        }
        i += 2;
    }

    return [mini, maxi];
}

const arr = [3, 5, 4, 1, 9];
const result = findMinMax(arr);
console.log(result[0], result[1]);

Output
1 9

K

kartik
Improve
Article Tags :

Explore

Lightbox