Beginner LevelData Structures & Algorithms
How do you find the maximum and minimum in an array with fewest comparisons?
ā Interview Prompt: Find the max and min of an array in O(N) time using the Tournament / pair comparison method, minimising total comparisons.
Naive Approach: 2N ā 2 comparisons (two separate scans).
Tournament Method: ~3N/2 comparisons (optimal).
ā¢
Process elements in pairs: compare the pair with each other first (1 comparison).
ā¢
Compare the larger with the current max (1 comparison).
ā¢
Compare the smaller with the current min (1 comparison).
ā¢
Total: 3 comparisons per 2 elements = 3N/2 ā 2 total.
This is the information-theoretically optimal minimum number of comparisons for this problem.
Code Implementation Example
typescript
function minMax(arr: number[]): { min: number; max: number } {
if (arr.length === 0) throw new Error('Empty array');
let min = arr[0], max = arr[0];
// Process pairs for ~3N/2 comparisons
let i = (arr.length % 2 === 1) ? 1 : 0;
if (arr.length % 2 === 0) {
min = Math.min(arr[0], arr[1]);
max = Math.max(arr[0], arr[1]);
i = 2;
}
for (; i < arr.length - 1; i += 2) {
const [lo, hi] = arr[i] < arr[i + 1]
? [arr[i], arr[i + 1]]
: [arr[i + 1], arr[i]];
if (lo < min) min = lo;
if (hi > max) max = hi;
}
return { min, max };
}š”Tournament method finding min/max using ~3N/2 comparisons.
šÆ Interview Key Takeaway
The tournament method finds min+max using only 3N/2 comparisons vs 2N for naive separate scans ā a classic optimisation problem.
#DSA#Arrays#Min Max#Comparisons#Beginner
Back to all Data Structures & Algorithms Questionsā