Smallest and Biggest in One Pass (teeing)
Problem
Print the smallest and the biggest value of the array, separated by a space. Read the data only once.
Constraints
- 1 <= n <= 10^5
Examples
Input
5 3 1 4 1 5
Output
1 5
Solutions
teeing solves a real streaming problem: two results from one pass over data that cannot be read twice. The last argument combines both results.
Collectors.teeing was added in Java 12.
/*
* Problem : Process an array.
* Input : n, then n integers.
* Output : The smallest and the biggest value.
* Approach: Collectors.teeing.
* Time : O(n)
* Space : O(n)
* Java : 12 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(int[] a) {
// Step 1: A stream can be read only once. Collectors.teeing (Java 12) sends every value to two collectors at the same time
// and joins their two results with a function.
return java.util.Arrays.stream(a).boxed().collect(java.util.stream.Collectors.teeing(
java.util.stream.Collectors.minBy(Integer::compare),
java.util.stream.Collectors.maxBy(Integer::compare),
(smallest, biggest) -> smallest.get() + " " + biggest.get()));
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
System.out.println(solve(a));
}
}
Hints (1)
- What does the third argument of teeing do?