Problem

Given an array of numbers of length N, find both the minimum and maximum using less than 2 * (N - 2) comparisons.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: 
arr = [3, 1, 4, 1, 5, 9, 2, 6]

Output: 
min = 1, max = 9

Explanation: 
The minimum element is 1 and maximum element is 9. Using the optimal approach, we can find both with fewer than 2 * (8 - 2) = 12 comparisons.

Example 2

1
2
3
4
5
6
7
8

Input: 
arr = [7]

Output: 
min = 7, max = 7

Explanation: 
With a single element, no comparisons are needed. Both min and max are the element itself.

Example 3

1
2
3
4
5
6
7
8

Input: 
arr = [5, 2]

Output: 
min = 2, max = 5

Explanation: 
With two elements, only 1 comparison is needed to determine min and max.

Solution

Method 1 - Divide and Conquer

Intuition

The naive approach would compare each element with both current min and max, requiring 2 comparisons per element (2N comparisons total). We can optimize this by using a divide and conquer approach or by pairing elements and comparing pairs first, then comparing winners and losers separately.

Approach

  1. If array has 1 element, return it as both min and max (0 comparisons)
  2. If array has 2 elements, compare them once and return (1 comparison)
  3. For larger arrays, recursively divide into two halves
  4. Find min and max in each half recursively
  5. Combine results by comparing the mins and maxs from both halves (2 comparisons)
  6. This approach uses approximately 3N/2 comparisons, which is less than 2*(N-2) for N > 2

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    pair<int, int> findMinMax(vector<int>& arr, int left, int right) {
        if (left == right) {
            return {arr[left], arr[left]};
        }
        
        if (right - left == 1) {
            if (arr[left] < arr[right]) {
                return {arr[left], arr[right]};
            } else {
                return {arr[right], arr[left]};
            }
        }
        
        int mid = left + (right - left) / 2;
        auto leftResult = findMinMax(arr, left, mid);
        auto rightResult = findMinMax(arr, mid + 1, right);
        
        int minVal = min(leftResult.first, rightResult.first);
        int maxVal = max(leftResult.second, rightResult.second);
        
        return {minVal, maxVal};
    }
    
    pair<int, int> findMinMax(vector<int>& arr) {
        if (arr.empty()) return {0, 0};
        return findMinMax(arr, 0, arr.size() - 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func findMinMax(arr []int) (int, int) {
    if len(arr) == 0 {
        return 0, 0
    }
    
    var helper func([]int, int, int) (int, int)
    helper = func(arr []int, left, right int) (int, int) {
        if left == right {
            return arr[left], arr[left]
        }
        
        if right-left == 1 {
            if arr[left] < arr[right] {
                return arr[left], arr[right]
            }
            return arr[right], arr[left]
        }
        
        mid := left + (right-left)/2
        leftMin, leftMax := helper(arr, left, mid)
        rightMin, rightMax := helper(arr, mid+1, right)
        
        minVal := leftMin
        if rightMin < minVal {
            minVal = rightMin
        }
        
        maxVal := leftMax
        if rightMax > maxVal {
            maxVal = rightMax
        }
        
        return minVal, maxVal
    }
    
    return helper(arr, 0, len(arr)-1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int[] findMinMax(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0};
        return findMinMax(arr, 0, arr.length - 1);
    }
    
    private int[] findMinMax(int[] arr, int left, int right) {
        if (left == right) {
            return new int[]{arr[left], arr[left]};
        }
        
        if (right - left == 1) {
            if (arr[left] < arr[right]) {
                return new int[]{arr[left], arr[right]};
            } else {
                return new int[]{arr[right], arr[left]};
            }
        }
        
        int mid = left + (right - left) / 2;
        int[] leftResult = findMinMax(arr, left, mid);
        int[] rightResult = findMinMax(arr, mid + 1, right);
        
        int minVal = Math.min(leftResult[0], rightResult[0]);
        int maxVal = Math.max(leftResult[1], rightResult[1]);
        
        return new int[]{minVal, maxVal};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def findMinMax(self, arr: List[int]) -> Tuple[int, int]:
        if not arr:
            return (0, 0)
        return self._findMinMax(arr, 0, len(arr) - 1)
    
    def _findMinMax(self, arr: List[int], left: int, right: int) -> Tuple[int, int]:
        if left == right:
            return (arr[left], arr[left])
        
        if right - left == 1:
            if arr[left] < arr[right]:
                return (arr[left], arr[right])
            else:
                return (arr[right], arr[left])
        
        mid = left + (right - left) // 2
        left_min, left_max = self._findMinMax(arr, left, mid)
        right_min, right_max = self._findMinMax(arr, mid + 1, right)
        
        min_val = min(left_min, right_min)
        max_val = max(left_max, right_max)
        
        return (min_val, max_val)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array. We visit each element exactly once
  • 🧺 Space complexity: O(log n), due to the recursion stack depth in the divide and conquer approach

Method 2 - Pairwise Comparison

Intuition

Instead of comparing each element with both min and max separately, we can pair up elements and compare them first. For each pair, we compare the smaller element with current min and larger element with current max. This reduces the total number of comparisons.

Approach

  1. Handle edge cases: empty array, single element, two elements
  2. Initialize min and max using the first two elements (1 comparison)
  3. Process remaining elements in pairs:
    • Compare the two elements in each pair (1 comparison)
    • Compare the smaller with current min (1 comparison if needed)
    • Compare the larger with current max (1 comparison if needed)
  4. If array length is odd, handle the last unpaired element
  5. Total comparisons: 3⌊n/2⌋ which is approximately 1.5n, well under 2*(n-2)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    pair<int, int> findMinMax(vector<int>& arr) {
        int n = arr.size();
        if (n == 0) return {0, 0};
        if (n == 1) return {arr[0], arr[0]};
        
        int minVal, maxVal;
        int i;
        
        if (arr[0] < arr[1]) {
            minVal = arr[0];
            maxVal = arr[1];
        } else {
            minVal = arr[1];
            maxVal = arr[0];
        }
        
        for (i = 2; i < n - 1; i += 2) {
            int smaller, larger;
            if (arr[i] < arr[i + 1]) {
                smaller = arr[i];
                larger = arr[i + 1];
            } else {
                smaller = arr[i + 1];
                larger = arr[i];
            }
            
            if (smaller < minVal) minVal = smaller;
            if (larger > maxVal) maxVal = larger;
        }
        
        if (i == n - 1) {
            if (arr[i] < minVal) minVal = arr[i];
            if (arr[i] > maxVal) maxVal = arr[i];
        }
        
        return {minVal, maxVal};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func findMinMax(arr []int) (int, int) {
    n := len(arr)
    if n == 0 {
        return 0, 0
    }
    if n == 1 {
        return arr[0], arr[0]
    }
    
    var minVal, maxVal int
    
    if arr[0] < arr[1] {
        minVal, maxVal = arr[0], arr[1]
    } else {
        minVal, maxVal = arr[1], arr[0]
    }
    
    i := 2
    for i < n-1 {
        var smaller, larger int
        if arr[i] < arr[i+1] {
            smaller, larger = arr[i], arr[i+1]
        } else {
            smaller, larger = arr[i+1], arr[i]
        }
        
        if smaller < minVal {
            minVal = smaller
        }
        if larger > maxVal {
            maxVal = larger
        }
        i += 2
    }
    
    if i == n-1 {
        if arr[i] < minVal {
            minVal = arr[i]
        }
        if arr[i] > maxVal {
            maxVal = arr[i]
        }
    }
    
    return minVal, maxVal
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int[] findMinMax(int[] arr) {
        int n = arr.length;
        if (n == 0) return new int[]{0, 0};
        if (n == 1) return new int[]{arr[0], arr[0]};
        
        int minVal, maxVal;
        
        if (arr[0] < arr[1]) {
            minVal = arr[0];
            maxVal = arr[1];
        } else {
            minVal = arr[1];
            maxVal = arr[0];
        }
        
        int i;
        for (i = 2; i < n - 1; i += 2) {
            int smaller, larger;
            if (arr[i] < arr[i + 1]) {
                smaller = arr[i];
                larger = arr[i + 1];
            } else {
                smaller = arr[i + 1];
                larger = arr[i];
            }
            
            if (smaller < minVal) minVal = smaller;
            if (larger > maxVal) maxVal = larger;
        }
        
        if (i == n - 1) {
            if (arr[i] < minVal) minVal = arr[i];
            if (arr[i] > maxVal) maxVal = arr[i];
        }
        
        return new int[]{minVal, maxVal};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def findMinMax(self, arr: List[int]) -> Tuple[int, int]:
        n = len(arr)
        if n == 0:
            return (0, 0)
        if n == 1:
            return (arr[0], arr[0])
        
        if arr[0] < arr[1]:
            min_val, max_val = arr[0], arr[1]
        else:
            min_val, max_val = arr[1], arr[0]
        
        i = 2
        while i < n - 1:
            if arr[i] < arr[i + 1]:
                smaller, larger = arr[i], arr[i + 1]
            else:
                smaller, larger = arr[i + 1], arr[i]
            
            if smaller < min_val:
                min_val = smaller
            if larger > max_val:
                max_val = larger
            i += 2
        
        if i == n - 1:
            if arr[i] < min_val:
                min_val = arr[i]
            if arr[i] > max_val:
                max_val = arr[i]
        
        return (min_val, max_val)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array. We process each element exactly once
  • 🧺 Space complexity: O(1), only using constant extra space for variables

Analysis

Both methods achieve the goal of using fewer than 2 * (N - 2) comparisons:

  • Method 1 (Divide and Conquer): Uses approximately 1.5n comparisons
  • Method 2 (Pairwise): Uses exactly 3⌊n/2⌋ comparisons

For the constraint 2 * (N - 2), when N ≥ 3:

  • Required: < 2N - 4 comparisons
  • Method 1: ≈ 1.5N comparisons
  • Method 2: ≈ 1.5N comparisons

Both methods significantly outperform the naive approach of 2N comparisons and meet the optimization requirement.