Find the maximum and minimum element in an array
Problem
Given an array of integers, return its minimum and maximum values. The follow-up asks you to use as few comparisons as possible.
Example 1
Input: [3, 5, 4, 1, 9] Output: min = 1, max = 9
Also asked as: Maximum and minimum of an array using minimum number of comparisons
Test cases
Case 1
Input: [3,5,4,1,9]
Expected: {"min":1,"max":9}Case 2
Input: [4,4,2,9]
Expected: {"min":2,"max":9}Case 3
Input: [-2,-8,-1]
Expected: {"min":-8,"max":-1}Case 4
Input: [7]
Expected: {"min":7,"max":7}View solutionHide solution2 approaches
1. Single pass
Time O(n)Space O(1)
Track the running min and max in one sweep.
function minMax(a) { let mn = a[0], mx = a[0]; for (const x of a) { if (x < mn) mn = x; if (x > mx) mx = x; } return { min: mn, max: mx };}2. Pairwise comparison (fewer comparisons)
Time O(n)Space O(1)
Compare elements in pairs first, then each to min/max — ~3n/2 comparisons instead of 2n.
function minMax(a) { let i = 0, mn, mx; if (a.length % 2) { mn = mx = a[0]; i = 1; } else { [mn, mx] = a[0] < a[1] ? [a[0], a[1]] : [a[1], a[0]]; i = 2; } for (; i < a.length; i += 2) { const [lo, hi] = a[i] < a[i + 1] ? [a[i], a[i + 1]] : [a[i + 1], a[i]]; if (lo < mn) mn = lo; if (hi > mx) mx = hi; } return { min: mn, max: mx };}