Find Min and Max in a Single Scan Using Comparison and Assignment

Finding the minimum and maximum elements in an array usually involves scanning the array twice. However, you can find both in a single pass by using two variables, min and max. During each iteration, compare the current array element to both min and max, updating these variables as needed. This approach has a time complexity of O(n), making it an efficient way to find both minimum and maximum values.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Main {
  public static void main(String[] args) {
    int[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    int min = array[0];
    int max = array[0];

    for (int num : array) {
      if (num < min) {
        min = num;
      }
      if (num > max) {
        max = num;
      }
    }

    System.out.println("Min: " + min);
    System.out.println("Max: " + max);
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main() {
  int array[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
  int min = array[0];
  int max = array[0];
  int length = sizeof(array) / sizeof(array[0]);

  for (int i = 0; i < length; i++) {
    if (array[i] < min) {
      min = array[i];
    }
    if (array[i] > max) {
      max = array[i];
    }
  }

  cout << "Min: " << min << endl;
  cout << "Max: " << max << endl;
  return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
array = [3, 1, 4, 1, 5, 9, 2, 6, 5]
min_val = array[0]
max_val = array[0]

for num in array:
    if num < min_val:
        min_val = num
    if num > max_val:
        max_val = num

print(f"Min: {min_val}")
print(f"Max: {max_val}")

Key Takeaways

Both minimum and maximum elements can be found in a single pass through the array.
Two variables, min and max, are initialized with the first array element and updated during each iteration.
The approach is efficient with a time complexity of O(n), reducing the number of scans needed compared to separate scans for min and max.