Problem

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

Examples

Example 1

1
2
3

Input: arr = [3, 1, 7, 4, 2]
Output: min = 1, max = 7
Explanation: The smallest value is 1 and the largest is 7.

Example 2

1
2
3

Input: arr = [-5, 0, 12, 8, -2]
Output: min = -5, max = 12
Explanation: The smallest value is -5 and the largest is 12.
Similar Problems

Solution

Method 1 – Single Pass (Naive)

Intuition

Scan the array once, updating the minimum and maximum as you go.

Approach

Finding the minimum

Finding the minimum value in an array is straightforward. The simplest approach is to start with the first element as the current minimum, then compare it with each remaining element in the array. Whenever a smaller value is found, update the current minimum. After checking all elements, the smallest value will be identified.

For e.g., Suppose the array is: [5, 3, 8, 2, 7].

1
2
3
4
5

[5]  3   8   2   7   ; min = 5)
 5  [3]  8   2   7   ; 3 < 5 ✅  ⇨ min = 3
 5   3  [8]  2   7   ; 8 < 3 ❌  ⇨ min = 3
 5   3   8  [2]  7   ; 2 < 3 ✅  ⇨ min = 2
 5   3   8   2  [7]  ; 7 < 2 ❌  ⇨ min = 2

It’s important to realize that finding the minimum (or maximum) requires exactly n-1 comparisons for an array of n elements. This is optimal, because every element must be checked to ensure that none are smaller (or larger) than the current candidate. We cannot guarantee the result without examining each value in the array.

Finding the maximum

Finding the maximum value in an array follows the same logic as finding the minimum and requires n-1 comparisons!. Start with the first element as the current maximum, then compare it with each remaining element. Whenever a larger value is found, update the current maximum. After checking all elements, the largest value will be identified. We have also covered this problem here: Find the max element in array

For e.g., Suppose the array is: [5, 3, 8, 2, 7].

1
2
3
4
5

[5]  3   8   2   7   ; max = 5
 5  [3]  8   2   7   ; 3 > 5 ❌  ⇨ max = 5
 5   3  [8]  2   7   ; 8 > 5 ✅  ⇨ max = 8
 5   3   8  [2]  7   ; 2 > 8 ❌  ⇨ max = 8
 5   3   8   2  [7]  ; 7 > 8 ❌  ⇨ max = 8
Summarizing Approach

The approach described above is straightforward and provably optimal for finding either the minimum or the maximum. Both operations individually require O(n) time and n-1 comparisons.

And when we combine the search for both minimum and maximum into a single pass naively, we will have time complexity of O(n) and 2n - 2 comparisons.

So, we can:

  1. Initialize min_val and max_val to the first element.
  2. For each element, update min_val and max_val as needed.
  3. Return both values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <vector>
#include <utility>
std::pair<int, int> findMinAndMax(const std::vector<int>& arr) {
    int minVal = arr[0], maxVal = arr[0];
    for (size_t i = 1; i < arr.size(); ++i) {
        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

func findMinAndMax(arr []int) (int, int) {
    minVal, maxVal := arr[0], arr[0]
    for _, v := range arr[1:] {
        if v < minVal {
            minVal = v
        }
        if v > maxVal {
            maxVal = v
        }
    }
    return minVal, maxVal
}
1
2
3
4
5
6
7
8

public int[] findMinAndMax(int[] arr) {
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    return new int[]{min, max};
}
1
2
3
4
5
6
7
8
9

fun findMinAndMax(arr: IntArray): Pair<Int, Int> {
    var min = arr[0]
    var max = arr[0]
    for (i in 1 until arr.size) {
        if (arr[i] < min) min = arr[i]
        if (arr[i] > max) max = arr[i]
    }
    return Pair(min, max)
}
1
2
3
4
5
6
7
8

def find_min_and_max(arr):
    min_val = max_val = arr[0]
    for x in arr[1:]:
        if x < min_val:
            min_val = x
        if x > max_val:
            max_val = x
    return min_val, max_val
1
2
3
4
5
6
7
8
9

pub fn find_min_and_max(arr: &[i32]) -> (i32, i32) {
    let mut min = arr[0];
    let mut max = arr[0];
    for &x in &arr[1..] {
        if x < min { min = x; }
        if x > max { max = x; }
    }
    (min, max)
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 – Pairwise Comparison (Fewer Comparisons)

Intuition

In previous method, we had 2n - 2 comparsons, which can be improved. Lets see how.

Instead of comparing each element individually to both the current minimum and maximum, we can process the array in pairs. For each pair, first compare the two elements to each other. Then, compare the smaller one to the current minimum and the larger one to the current maximum. This way, each pair requires only 3 comparisons instead of 4.

So, comparing elements in pairs to reduce the total number of comparisons.

Lets look at the example (nums = [5, 3, 8, 2, 7]) again:

1
2
3

5   3   8    2   7   ; min = 5, max = 5
5  [3   8]   2   7   ; 3 < 8 → min = min(3, 5) = 3, max = max(8, 5) = 8
5   3   8   [2   7]  ; 2 < 7 → min = min(2, 3) = 2, max = max(7, 8) = 8

After all pairs:

min = 2, max = 8

Approach

  1. If the array has an odd number of elements, start with the first as both min and max.
  2. Otherwise, initialize min and max with the first two elements.
  3. For each pair, compare the two, then compare the smaller to min and the larger to max.

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

#include <vector>
#include <algorithm>
#include <utility>
std::pair<int, int> findMinAndMaxPairwise(const std::vector<int>& arr) {
    int n = arr.size();
    int minVal, maxVal, i;
    if (n % 2 == 0) {
        minVal = std::min(arr[0], arr[1]);
        maxVal = std::max(arr[0], arr[1]);
        i = 2;
    } else {
        minVal = maxVal = arr[0];
        i = 1;
    }
    while (i < n - 1) {
        int a = arr[i], b = arr[i+1];
        if (a < b) {
            minVal = std::min(minVal, a);
            maxVal = std::max(maxVal, b);
        } else {
            minVal = std::min(minVal, b);
            maxVal = std::max(maxVal, a);
        }
        i += 2;
    }
    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

func findMinAndMaxPairwise(arr []int) (int, int) {
    n := len(arr)
    var minVal, maxVal, i int
    if n%2 == 0 {
        if arr[0] < arr[1] {
            minVal, maxVal = arr[0], arr[1]
        } else {
            minVal, maxVal = arr[1], arr[0]
        }
        i = 2
    } else {
        minVal, maxVal = arr[0], arr[0]
        i = 1
    }
    for i < n-1 {
        a, b := arr[i], arr[i+1]
        if a < b {
            if a < minVal {
                minVal = a
            }
            if b > maxVal {
                maxVal = b
            }
        } else {
            if b < minVal {
                minVal = b
            }
            if a > maxVal {
                maxVal = a
            }
        }
        i += 2
    }
    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

public int[] findMinAndMaxPairwise(int[] arr) {
    int n = arr.length;
    int min, max, i;
    if (n % 2 == 0) {
        min = Math.min(arr[0], arr[1]);
        max = Math.max(arr[0], arr[1]);
        i = 2;
    } else {
        min = max = arr[0];
        i = 1;
    }
    while (i < n - 1) {
        int a = arr[i], b = arr[i+1];
        if (a < b) {
            min = Math.min(min, a);
            max = Math.max(max, b);
        } else {
            min = Math.min(min, b);
            max = Math.max(max, a);
        }
        i += 2;
    }
    return new int[]{min, max};
}
 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

fun findMinAndMaxPairwise(arr: IntArray): Pair<Int, Int> {
    val n = arr.size
    var min: Int
    var max: Int
    var i: Int
    if (n % 2 == 0) {
        min = minOf(arr[0], arr[1])
        max = maxOf(arr[0], arr[1])
        i = 2
    } else {
        min = arr[0]
        max = arr[0]
        i = 1
    }
    while (i < n - 1) {
        val a = arr[i]
        val b = arr[i + 1]
        if (a < b) {
            min = minOf(min, a)
            max = maxOf(max, b)
        } else {
            min = minOf(min, b)
            max = maxOf(max, a)
        }
        i += 2
    }
    return Pair(min, max)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def find_min_and_max_pairwise(arr):
    n = len(arr)
    if n % 2 == 0:
        min_val = min(arr[0], arr[1])
        max_val = max(arr[0], arr[1])
        i = 2
    else:
        min_val = max_val = arr[0]
        i = 1
    while i < n - 1:
        a, b = arr[i], arr[i+1]
        if a < b:
            min_val = min(min_val, a)
            max_val = max(max_val, b)
        else:
            min_val = min(min_val, b)
            max_val = max(max_val, a)
        i += 2
    return min_val, max_val
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub fn find_min_and_max_pairwise(arr: &[i32]) -> (i32, i32) {
    let n = arr.len();
    let (mut min, mut max, mut i) = if n % 2 == 0 {
        if arr[0] < arr[1] {
            (arr[0], arr[1], 2)
        } else {
            (arr[1], arr[0], 2)
        }
    } else {
        (arr[0], arr[0], 1)
    };
    while i < n - 1 {
        let (a, b) = (arr[i], arr[i + 1]);
        if a < b {
            if a < min { min = a; }
            if b > max { max = b; }
        } else {
            if b < min { min = b; }
            if a > max { max = a; }
        }
        i += 2;
    }
    (min, max)
}

Complexity

  • ⏰ Time complexity: O(n). The overall time complexity for finding both the minimum and maximum is O(n), whether you do them separately or together in a single pass. However, with the pairwise method, you can reduce the total number of comparisons to about 1.5n (specifically, 3 * ceil(n/2)), instead of the 2n – 2 comparisons required by the naive approach.
  • 🧺 Space complexity: O(1)

Application

This algorithm is fundamental and finds use in many areas of computer science. Its importance comes from two key insights:

  1. Combining two related tasks—like finding the minimum and maximum—doesn’t necessarily double the work. With a clever approach, you can reduce the total number of operations.
  2. Using techniques like sentinels can further optimize algorithms and help avoid unnecessary comparisons, as seen in sequential search.