Maximum and minimum of an array using minimum number of comparisons

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.

[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).

#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; } 

#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; } 

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));  } } 

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])) 

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]}");  } } 

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]}`); 

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).

#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; } 

#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; } 

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));  } } 

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]) 

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]}");  } } 

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); 

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:

#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; } 

#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; } 

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));  } } 

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])) 

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]}");  } } 

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]); 

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:

#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; } 

#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; } 

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));  } } 

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() 

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]}");  } } 

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]); 

1 9