Minimum and Maximum in the Array
Problem
Given an array of integers, find the minimum and maximum value in it.
Examples
Example 1
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
Input: arr = [-5, 0, 12, 8, -2]
Output: min = -5, max = 12
Explanation: The smallest value is -5 and the largest is 12.
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].
[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](find-largest-element-in-array)
For e.g., Suppose the array is: [5, 3, 8, 2, 7].
[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:
- Initialize
min_valandmax_valto the first element. - For each element, update
min_valandmax_valas needed. - Return both values.
Code
C++
#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};
}
Go
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
}
Java
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};
}
Kotlin
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)
}
Python
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
Rust
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:
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
- If the array has an odd number of elements, start with the first as both min and max.
- Otherwise, initialize min and max with the first two elements.
- For each pair, compare the two, then compare the smaller to min and the larger to max.
Code
C++
#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};
}
Go
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
}
Java
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};
}
Kotlin
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)
}
Python
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
Rust
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 isO(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 about1.5n(specifically,3 * ceil(n/2)), instead of the2n – 2comparisons 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:
- 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.
- Using techniques like sentinels can further optimize algorithms and help avoid unnecessary comparisons, as seen in sequential search.