BL
U

22. Single Pass Min and Max with Comparisons

Easy

Problem Description

Find the minimum and maximum element in an array of NN integers in one traversal. Compare elements in pairs so that total comparisons between array elements is at most ⌈3N/2⌉\lceil 3N/2 \rceil.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,A2,…,ANA_1, A_2, \dots, A_N.

Output Format

  • •Line 1: Two space-separated integers: min_val max_val
  • •Line 2: An integer representing total element comparisons performed.
Example 1:
Input:
5
3 1 9 7 2
Output:
1 9
6
Explanation: Pairs evaluated in 6 comparisons <= ceil(3*5/2)=8.
Example 2:
Input:
1
100
Output:
100 100
0
Explanation: Single element requires 0 comparisons.
Example 3:
Input:
2
5 8
Output:
5 8
1
Explanation: Comparing 5 and 8 takes 1 comparison.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online