Find Maximum and minimum of an array using minimum number of comparisons

by

Introduction for Find Maximum and minimum of an array

Finding the maximum and minimum values in an array is a common problem in computer science. While it seems straightforward, optimizing the process to use the least number of comparisons is crucial in scenarios where computational efficiency matters. In this blog, we’ll explore an efficient algorithm to Find Maximum and minimum of an array and compare it with other approaches.

Problem Statement for Find Maximum and minimum of an array

Given an array of size N. The task is to Find Maximum and minimum of an array using the minimum number of comparisons.

Examples:

Input: arr[] = {15, 10, 3, 5, 4, 7, 9}
Output: Minimum element is: 3
        Maximum element is: 15


Input: arr[] = {45, 22, 14, 8, 17, 35, 2, 69}
Output: Minimum element is: 2
        Maximum element is: 69

Naive Approach: Linear Search Approach for Find Maximum and minimum of an array

The simplest way to find maximum and minimum of an array is by iterating through each element. Here’s the basic algorithm:

  1. Initialize two variables, max and min, with the first element of the array.
  2. Traverse the array:
    • Update max if the current element is greater than max.
    • Update min if the current element is smaller than min.

Code Example (Java):

public class MinMax {
    public static void findMinMax(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        
        System.out.println("Maximum: " + max);
        System.out.println("Minimum: " + min);
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 2, 9};
        findMinMax(arr);
    }
}

Comparison Count:
This method requires 2n - 2 comparisons, where n is the size of the array.

Approach 2: Using INT_MAX and INT_MIN to Find Maximum and minimum of an array

Steps:

  1. Use INT_MAX (maximum possible integer value) to initialize the minimum value (min), so that any number in the array will naturally be smaller.
  2. Use INT_MIN (minimum possible integer value) to initialize the maximum value (max), so that any number in the array will naturally be larger.
  3. Iterate through the array to update min and max values based on comparisons.
public class MinMaxArray {
    
    // Function to find the minimum value in the array
    public static int setmin(int[] arr) {
        int min = Integer.MAX_VALUE; // Initialize minimum with the largest possible integer
        for (int num : arr) {
            if (num < min) {
                min = num; // Update mini if a smaller value is found
            }
        }
        return min; // Return the smallest value
    }

    // Function to find the maximum value in the array
    public static int setmax(int[] arr) {
        int max = Integer.MIN_VALUE; // Initialize maximum with the smallest possible integer
        for (int num : arr) {
            if (num > max) {
                maxi = num; // Update maxi if a larger value is found
            }
        }
        return max; // Return the largest value
    }

    // Main method
    public static void main(String[] args) {
        // Declare and initialize the array
        int[] arr = {12, 3, 45, 7, -5, 19, 23};

        // Call functions to find minimum and maximum
        int minimum = setmin(arr);
        int maximum = setmax(arr);

        // Print the results
        System.out.println("Minimum value in the array: " + minimum);
        System.out.println("Maximum value in the array: " + maximum);
    }
}

How It Works

  1. Initialization:
    • min is initialized to Integer.MAX_VALUE, ensuring that any number in the array will be smaller initially.
    • max is initialized to Integer.MIN_VALUE, ensuring that any number in the array will be larger initially.
  2. Iteration:
    • Use a for-each loop to traverse through each element of the array.
    • Compare and update mini for the smallest value and maxi for the largest value.
  3. Output:
    • The results are displayed after calling both functions.

Complexity

  • Time Complexity: O(n)
    • Each function (setmin and setmax) iterates through the array once.
  • Space Complexity: O(1)
    • Only a few integer variables are used.

Approach 3: Using Sorting to Find Maximum and minimum of an array

Description:
Sorting the array is another way to determine the maximum and minimum values. After sorting:

  • Sort array in ascending order.
  • The minimum value will be the first element in the sorted array.
  • The maximum value will be the last element in the sorted array.

Although sorting simplifies the process, it is less efficient than other methods for this specific task because sorting has a higher time complexity compared to direct comparison methods.

Steps:

  1. Sort the array using a sorting algorithm.
  2. Retrieve the first element as the minimum and the last element as the maximum.
import java.util.Arrays;

public class MinMax {
    public static void findMinMax(int[] arr) {
        // Sort the array
        Arrays.sort(arr);

        // Minimum is the first element
        int min = arr[0];
        // Maximum is the last element
        int max = arr[arr.length - 1];

        System.out.println("Maximum: " + max);
        System.out.println("Minimum: " + min);
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 2, 9};
        findMinMax(arr);
    }
}

Time Complexity:

  • Sorting: O(nlog⁡n) (depending on the sorting algorithm).
  • Finding Min/Max: O(1)

While sorting is straightforward, it is not optimal for finding only the maximum and minimum values, as direct comparison methods perform this task in O(n) time.

Approach 4: Pair Comparison Method to Find Maximum and minimum of an array

Description:
This approach reduces comparisons by comparing array elements in pairs. For each pair, one comparison determines the local minimum and maximum, followed by updating the global max and min.

Steps:

  1. Traverse the array in pairs.
  2. For each pair:
    • Compare the two elements to determine the local min and max.
    • Compare the local values with the global max and min.

Code Example (Java):

public class MinMax {
    static class Pair {
        int min;
        int max;
    }

    public static Pair getMinMax(int[] arr) {
        Pair result = new Pair();
        int n = arr.length;

        if (n == 1) {
            result.min = result.max = arr[0];
            return result;
        }

        // Initialize first pair
        if (arr[0] > arr[1]) {
            result.max = arr[0];
            result.min = arr[1];
        } else {
            result.max = arr[1];
            result.min = arr[0];
        }

        // Process remaining pairs
        for (int i = 2; i < n - 1; i += 2) {
            int localMax, localMin;
            if (arr[i] > arr[i + 1]) {
                localMax = arr[i];
                localMin = arr[i + 1];
            } else {
                localMax = arr[i + 1];
                localMin = arr[i];
            }

            if (localMax > result.max) {
                result.max = localMax;
            }
            if (localMin < result.min) {
                result.min = localMin;
            }
        }

        // Handle last element if array size is odd
        if (n % 2 != 0) {
            if (arr[n - 1] > result.max) {
                result.max = arr[n - 1];
            }
            if (arr[n - 1] < result.min) {
                result.min = arr[n - 1];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 2, 9, 6};
        Pair result = getMinMax(arr);
        System.out.println("Maximum: " + result.max);
        System.out.println("Minimum: " + result.min);
    }
}

Number of Comparisons:

  • Approximately 3n/2−2.

Approach 5: Divide and Conquer to Find Maximum and minimum of an array

Description:
Using the Divide and Conquer strategy, the array is recursively divided into halves. The maximum and minimum values are determined for each half and merged.

Steps:

  1. Divide the array into two halves.
  2. Recursively find the maximum and minimum in each half.
  3. Merge the results to get the overall maximum and minimum.

Code Example (Java):

public class MinMax {
    static class Pair {
        int min;
        int max;
    }

    public static Pair findMinMax(int[] arr, int low, int high) {
        Pair result = new Pair();

        // Base case: Only one element
        if (low == high) {
            result.min = result.max = arr[low];
            return result;
        }

        // Base case: Two elements
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                result.max = arr[low];
                result.min = arr[high];
            } else {
                result.max = arr[high];
                result.min = arr[low];
            }
            return result;
        }

        // Divide array into halves
        int mid = (low + high) / 2;
        Pair left = findMinMax(arr, low, mid);
        Pair right = findMinMax(arr, mid + 1, high);

        // Combine results
        result.max = Math.max(left.max, right.max);
        result.min = Math.min(left.min, right.min);

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 2, 9, 6, 4};
        Pair result = findMinMax(arr, 0, arr.length - 1);
        System.out.println("Maximum: " + result.max);
        System.out.println("Minimum: " + result.min);
    }
}

Number of Comparisons:

  • Approximately 3n/2−2.

Approach 6: Using a Priority Queue (Min-Heap and Max-Heap) to Find Maximum and minimum of an array

Description:
You can use a Min-Heap to find the minimum and a Max-Heap to find the maximum. This method leverages data structures to simplify retrieval operations in dynamic datasets.

Steps:

  1. Build a Min-Heap for the array and retrieve the root for the minimum.
  2. Build a Max-Heap for the array and retrieve the root for the maximum.
import java.util.PriorityQueue;
import java.util.Collections;

public class MinMaxHeap {
    public static void findMinMax(int[] arr) {
        // Min-Heap for finding the minimum
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Max-Heap for finding the maximum
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int num : arr) {
            minHeap.add(num);
            maxHeap.add(num);
        }

        int min = minHeap.peek(); // Smallest element
        int max = maxHeap.peek(); // Largest element

        System.out.println("Maximum: " + max);
        System.out.println("Minimum: " + min);
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 2, 9};
        findMinMax(arr);
    }
}

Time Complexity:

  • Building Heaps: O(n).
  • Accessing Max/Min: O(1).

This is particularly useful when the array is frequently updated or when you need to maintain dynamic tracking of max/min values.

Conclusion for Find Maximum and minimum of an array

To Find Maximum and minimum of an array using the minimum number of comparisons is an essential optimization technique in computer science. The Divide and Conquer approach, with 3n/2−2 comparisons, is the most efficient method for large arrays.

Try implementing both methods to understand their differences and choose the one that suits your problem’s requirements.

Related posts:

String to Integer (atoi) - LeetCode 8 Solution
Roman to Integer - Leetcode 13 Solution
4Sum Leetcode | Leetcode 18 Solution

Leave a comment