Maximum and minimum of an array using minimum number of comparisons

Problem Statement

Given an array of integers, find the maximum and minimum elements using the minimum number of comparisons.

Constraints:

• Array has at least one element
• Elements can be positive, negative, or zero

Example:

• Input: arr = [1000, 11, 445, 1, 330, 3000]
• Output: min = 1, max = 3000

Comparison Count Analysis:

• Brute force: 2(n-1) comparisons
• Optimal (Tournament): 3n/2 - 2 comparisons

Approach 1: Brute Force (Linear Search)

Intuition

Initialize min and max with the first element, then compare each element with both min and max.

Algorithm

1. Initialize min = max = arr[0]
2. For each element from index 1 to n-1:
   • If arr[i] < min, update min
   • If arr[i] > max, update max
3. Return min and max

public class Solution {
    public int[] findMinMax(int[] arr) {
        if (arr.length == 0) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
        
        int minVal = arr[0];
        int maxVal = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
            }
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        
        return new int[]{minVal, maxVal};
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only two variables
• Comparisons: 2(n-1) = 2n - 2

Approach 2: Tournament Method (Optimal - Pair Comparison)

Intuition

Compare elements in pairs first. The smaller of each pair is a candidate for minimum, and the larger is a candidate for maximum. This reduces the total number of comparisons.

Algorithm

1. If n is odd, initialize min = max = arr[0], start from index 1
2. If n is even, compare arr[0] and arr[1], set min and max accordingly, start from index 2
3. Process elements in pairs:
   • Compare arr[i] with arr[i+1]
   • Compare smaller with current min
   • Compare larger with current max

Comparison Count:

• For n elements: 3 comparisons per 2 elements
• Total: 3 * (n/2) = 3n/2 comparisons (approximately)
• Exact: 3n/2 - 2 for even n, 3(n-1)/2 for odd n

public class Solution {
    public int[] findMinMaxOptimal(int[] arr) {
        int n = arr.length;
        if (n == 0) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
        if (n == 1) return new int[]{arr[0], arr[0]};
        
        int minVal, maxVal;
        int i;
        
        // Initialize based on odd/even length
        if (n % 2 == 0) {
            if (arr[0] < arr[1]) {
                minVal = arr[0];
                maxVal = arr[1];
            } else {
                minVal = arr[1];
                maxVal = arr[0];
            }
            i = 2;
        } else {
            minVal = maxVal = arr[0];
            i = 1;
        }
        
        // Process pairs
        while (i < n - 1) {
            if (arr[i] < arr[i + 1]) {
                if (arr[i] < minVal) minVal = arr[i];
                if (arr[i + 1] > maxVal) maxVal = arr[i + 1];
            } else {
                if (arr[i + 1] < minVal) minVal = arr[i + 1];
                if (arr[i] > maxVal) maxVal = arr[i];
            }
            i += 2;
        }
        
        return new int[]{minVal, maxVal};
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only variables
• Comparisons: 3n/2 - 2 (for even n) or 3(n-1)/2 (for odd n)

Approach 3: Divide and Conquer

Intuition

Divide the array into two halves, find min and max of each half recursively, then combine results.

public class Solution {
    private int[] findMinMaxDC(int[] arr, int left, int right) {
        // Base case: single element
        if (left == right) {
            return new int[]{arr[left], arr[left]};
        }
        
        // Base case: two elements
        if (right == left + 1) {
            if (arr[left] < arr[right]) {
                return new int[]{arr[left], arr[right]};
            } else {
                return new int[]{arr[right], arr[left]};
            }
        }
        
        // Recursive case
        int mid = left + (right - left) / 2;
        
        int[] leftResult = findMinMaxDC(arr, left, mid);
        int[] rightResult = findMinMaxDC(arr, mid + 1, right);
        
        return new int[]{
            Math.min(leftResult[0], rightResult[0]),
            Math.max(leftResult[1], rightResult[1])
        };
    }
    
    public int[] findMinMax(int[] arr) {
        if (arr.length == 0) {
            return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
        }
        return findMinMaxDC(arr, 0, arr.length - 1);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each element visited once
• Space Complexity: O(log n) - Recursion stack
• Comparisons: 3n/2 - 2 (same as tournament method)

Comparison of Approaches

| Approach | Time | Space | Comparisons | |----------|------|-------|-------------| | Brute Force | O(n) | O(1) | 2(n-1) | | Tournament/Pair | O(n) | O(1) | 3n/2 - 2 | | Divide & Conquer | O(n) | O(log n) | 3n/2 - 2 |

Example with n = 100:

• Brute Force: 198 comparisons
• Optimal: 148 comparisons
• Savings: 25% fewer comparisons

Key Takeaways

1. Comparison Minimization: Tournament method achieves minimum comparisons by pairing elements
2. Same Time Complexity: All approaches are O(n), but differ in constant factors
3. Pair Comparison Insight: Comparing elements in pairs first determines which is a min candidate and which is a max candidate
4. Divide & Conquer: Elegant but uses extra stack space
5. Practical Use: For small arrays, difference is negligible; matters for very large arrays or comparison-expensive operations
6. Lower Bound: 3n/2 - 2 is proven to be the minimum number of comparisons needed