Find the maximum and minimum element in an array

Problem Statement

Given an array of integers, find the maximum and minimum element in the array.

Example:

• Input: [3, 5, 4, 1, 9]
• Output: Maximum = 9, Minimum = 1

Approach 1: Linear Search

Intuition

Traverse the entire array while keeping track of the maximum and minimum values seen so far.

Algorithm

1. Initialize max and min with the first element
2. Traverse the array from index 1
3. Update max if current element is greater
4. Update min if current element is smaller

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

Complexity Analysis

• Time Complexity: O(n) - Single pass, 2(n-1) comparisons
• Space Complexity: O(1) - Only two variables used

Approach 2: Tournament Method (Divide and Conquer)

Intuition

Use divide and conquer to reduce the number of comparisons. Compare elements in pairs.

Algorithm

1. If array has one element, it's both min and max
2. If array has two elements, compare them
3. Divide array into two halves
4. Recursively find min-max in both halves
5. Compare results from both halves

Complexity Analysis

• Time Complexity: O(n) - Approximately 3n/2 - 2 comparisons
• Space Complexity: O(log n) - Recursion stack depth

Approach 3: Compare in Pairs

Intuition

Process elements in pairs to minimize comparisons.

Algorithm

1. Compare elements in pairs
2. Compare smaller with current min
3. Compare larger with current max

Complexity Analysis

• Time Complexity: O(n) - Exactly 3n/2 - 2 comparisons for even n
• Space Complexity: O(1) - Constant extra space

Key Takeaways

1. Pair comparison reduces total comparisons from 2(n-1) to 3n/2-2
2. Divide and conquer provides an elegant recursive solution
3. For interviews, the linear approach is usually sufficient
4. The pair comparison approach is optimal in terms of comparisons