Course contentsShow
← Computer Science
Lesson 829 of 2,87219. Searching and SelectionFree lesson

Simultaneous Min and Max

Finding both minimum and maximum in a single pass using at most 3n/2 comparisons with paired element processing.

Simultaneous Min and Max

You'll learn how to find both the smallest and largest elements in an array more efficiently by comparing elements in pairs.


The Core Idea

When you need to find both the minimum and maximum values in an array, the naive approach is to scan through the array twice—once for min and once for max—requiring 2(n - 1) comparisons total.

But there's a clever optimization: process elements in pairs.

Here's how it works:

  1. Compare each pair of elements to each other first (1 comparison)
  2. Compare the smaller one to the current minimum (1 comparison)
  3. Compare the larger one to the current maximum (1 comparison)

Each pair costs 3 comparisons, but processes 2 elements.

Why This Is Better

For an array of n elements:

  • Pairs to process: n/2
  • Comparisons per pair: 3
  • Total: 3n/2 comparisons (plus a few for initialization)

Compare this to scanning twice: 2n comparisons. You've saved roughly 25% of comparisons!

The Intuition

Think of it like sorting mail into "small" and "large" bins. Instead of comparing every letter to both bins, you first compare two letters to each other, then send the smaller one toward the "small" bin and the larger toward the "large" bin. This preprocessing step eliminates redundant comparisons.

Handling Odd-Length Arrays

If the array has an odd number of elements, initialize both min and max to the first element, then process the remaining even number of elements in pairs.

Key Takeaway: By comparing elements in pairs before checking against min/max, you can find both the minimum and maximum values in a single pass using only ~3n/2 comparisons instead of 2n.