Java 8 - Finding Leaders in an Array
I am trying to learn the specifics of Java 8, especially in the functional programming aspect. So I am trying to solve a problem: find leaders in an array. The leader is the element that is larger than all the elements in the array on the right.
For example:
Input array: {98, 23, 54, 12, 20, 7, 27}
Conclusion: Leaders - 27 54 98
I have now solved this using the usual iterative approach as shown below.
private static void findLeaders(int[] array) {
int currentLeader = array[array.length - 1];
System.out.println(currentLeader);
for(int i = array.length - 1; i >= 0; i--) {
if(array[i] > currentLeader) {
System.out.println(array[i]);
currentLeader = array[i];
}
}
}
I tried to solve it with Java 8, but I couldn't do anything other than writing this piece of code that again had a compile error:
Function<Integer, Integer> checkLeader = i -> i > currentLeader ? i : currentLeader;
Error: Local variable currentLeader defined in the enclosing scope must be final or effectively final
Now how to solve the same problem using Java 8 features.
source to share
The traditional, imperative approach seems best to me, both in terms of performance and readability / ease of maintenance. However, here's my attempt at using streams and a little functional programming:
List<Integer> leaders = IntStream.rangeClosed(1, array.length)
.mapToObj(i -> array[array.length - i])
.collect(toLeaders());
Here I am creating a closed range 1..n
and then in mapToObj
, converting index 1
to n - 1
, index 2
to n - 2
, etc. I immediately use this transformed index to get the corresponding element of the array, which is finally compiled into a list using a custom collector. This custom collector is returned by a helper method toLeaders()
:
private static Collector<Integer, ?, List<Integer>> toLeaders() {
BiConsumer<List<Integer>, Integer> accumulator = (leaders, n) -> {
if (leaders.isEmpty() || n > leaders.get(leaders.size() - 1)) {
leaders.add(n);
}
};
return Collector.of(ArrayList::new, accumulator, (leaders1, leaders2) -> {
leaders2.forEach(n -> accumulator.accept(leaders1, n));
return leaders1;
});
}
BiConsumer<List<Integer>, Integer> accumulator
takes two values: a list containing the leaders found so far, and an element from the stream. This one Biconsumer
checks if the given number is a leader, and if the test succeeds, adds the number to the specified leaderboard.
Then the collector that uses this drive is created with a utility Collector.of
that also accepts a Supplier
volatile structure that will hold the leaders (this ArrayList::new
) and BinaryOperator
that is responsible for merging the two leaderboards that were created earlier (this should only be used when the stream is parallel ). This adder uses the previously announced accumulator
biconsumer.
source to share
How about this? you can use IntBinaryOperator instead Function<Integer, Integer>
as checkLeader
it is not effectively final variable , so it cannot be accessed in the lambda expression, but you can pass checkLeader
as parameters to the lambda expression:
private static void findLeaders(int[] array) {
IntBinaryOperator checkLeader = (left, right) -> left > right ? left : right;
int currentLeader = array[array.length - 1];
System.out.println(currentLeader);
for (int i = array.length - 1; i >= 0; i--) {
// pass `currentLeader` for each call ---v
if (checkLeader.applyAsInt(array[i], currentLeader) == array[i]) {
System.out.println(array[i]);
currentLeader = array[i];
}
}
}
Let it refactor the use of the api stream step by step
The first , using IntBinaryOperator, cannot know if less checkLeader
array[i]
because it returns the final larger result (when checkLeader
== array[i]
then the program has errors). so you need a Comparator , not an IntBinaryOperator :
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Integer::compareTo;
int currentLeader = array[array.length - 1];
System.out.println(currentLeader);
for (int i = array.length - 1; i >= 0; i--) {
// check whether array[i] > currentLeader ---v
if (comparator.compare(array[i], currentLeader) > 0) {
System.out.println(array[i]);
currentLeader = array[i];
}
}
}
Then we can use the comparator nullsFirst # , to remove the first statement println
because it is duplicated in the cycle:
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Comparator.nullsFirst(Integer::compareTo);
Integer currentLeader = null;
for (int i = array.length - 1; i >= 0; i--) {
// array[0] is always > currentLeader since it is null at the first time
// |
if (comparator.compare(array[i], currentLeader) > 0) {
System.out.println(array[i]);
currentLeader = array[i];
}
}
}
Prepare thread-api we need separates display logic from collecting logic with Stack
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Comparator.nullsFirst(Integer::compareTo);
Stack<Integer> stack = new Stack<>();
stack.push(null);
for (int i = array.length - 1; i >= 0; i--) {
// comparing array[i] with the top leaders ---v
if (comparator.compare(array[i], stack.peek()) > 0) {
stack.push(array[i]);
}
}
//take 1st element away from stack since it is just a initial value for comparision
// |
System.out.println(stack.subList(1, stack.size()));
}
By using IntStream # range up to inverse array, then we can use Instead of for-each
:
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Comparator.nullsFirst(Integer::compareTo);
Stack<Integer> stack = new Stack<>();
stack.push(null);
int[] reversed = IntStream.range(0, array.length)
// v--- reverse array elements
.map(i -> array[array.length - i - 1]).toArray();
for (int candidate : reversed) {
if (comparator.compare(candidate, stack.peek()) > 0) {
stack.push(candidate);
}
}
System.out.println(stack.subList(1, stack.size()));
}
Then we can inline all the statements on one line except comparator
by using IntStream # collect , but wait, an error is thrownStack#peek
because the stack is empty:
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Comparator.nullsFirst(Integer::compareTo);
List<Integer> result = IntStream.range(0, array.length)
.map(i -> array[array.length - i - 1])
.collect(
Stack::new,
(stack, candidate) -> {
// failed at the first time since the stack is empty
// |
if (comparator.compare(candidate, stack.peek()) > 0) {
stack.push(candidate);
}
},
Stack::addAll
);
System.out.println(result.subList(1, result.size()));
}
To fix the error checking if empty or empty:
private static void findLeaders(int[] array) {
Comparator<Integer> c = Comparator.nullsFirst(Integer::compareTo);
List<Integer> result = IntStream.range(0, array.length)
.map(i -> array[array.length - i - 1])
.collect(
Stack::new,
(stack, candidate) -> {
// v-- just add 1st candidate when stack is empty
if (stack.isEmpty() || c.compare(candidate, stack.peek()) > 0) {
stack.push(candidate);
}
},
Stack::addAll
);
System.out.println(result);
}
Finally, we can use the ternary operator ?:
to inline the body of the lambda expression:
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Comparator.nullsFirst(Integer::compareTo);
List<Integer> result = IntStream.range(0, array.length)
.map(i -> array[array.length - i - 1])
.collect(
Stack::new,
(stack, candidate) -> stack.push(
stack.isEmpty() || comparator.compare(candidate, stack.peek()) > 0 ?
candidate :
stack.pop()
),
Stack::addAll
);
System.out.println(result);
}
Edit
Thanks for @FedericoPeraltaSchaffner to check my answer, Comparator#nullsFirst
no longer required as the code never pops the initial value null
for comparison.
private static void findLeaders(int[] array) {
Comparator<Integer> comparator = Integer::compareTo;
List<Integer> result = IntStream.rangeClosed(1, array.length)
.map(i -> array[array.length - i])
.collect(
Stack::new,
(stack, candidate) -> stack.push(
stack.isEmpty() || comparator.compare(candidate, stack.peek()) > 0 ?
candidate :
stack.pop()
// ^--- just push the top back to the stack if top<=candidate
),
Stack::addAll
);
System.out.println(result);
}
source to share