Find longest consecutive numbers in a list of sorted numbers using java 8 stream

Question

I have a working piece of code written using traditional for loop as follows. I want to refactor it to use java 8 streams and remove the for loop. The output of the below code should be 3 as that is the longest consecutive list of numbers (4, 5 and 6)

    List<Integer> weekDays = Lists.newArrayList(1, 2, 4, 5, 6);

    List<Integer> consecutiveIntervals = Lists.newArrayList();
    int maxConsecutiveTillNow = 1;
    for (int i = 1; i < weekDays.size(); i++) {
        if (weekDays.get(i) - weekDays.get(i - 1) == 1) {
            maxConsecutiveTillNow++;
        } else {
            consecutiveIntervals.add(maxConsecutiveTillNow);
            maxConsecutiveTillNow = 1;
        }
    }
    consecutiveIntervals.add(maxConsecutiveTillNow);

    System.out.println(consecutiveIntervals.stream()
                                           .max(Integer::compareTo)
                                           .get()
                      );

score 5 · Accepted Answer · edited May 23 '17 at 12:00

The Stream API is not well suited for this kind of problems. It is hardly possible to keep track of seen elements of a Stream in a correct way. So you have to go for multiple Streams.

Based on one of Stuart Marks' answers.

List<Integer> weekDays = Arrays.asList(1, 2, 4, 5, 6);
int[] indices = IntStream.rangeClosed(0, weekDays.size())
   .filter(i -> i == 0 || i == weekDays.size() || weekDays.get(i - 1) + 1 != weekDays.get(i))
   .toArray();
int longest = IntStream.range(0, indices.length - 1).map(i -> indices[i + 1] - indices[i])
   .max().orElseThrow(NoSuchElementException::new);
System.out.println(longest);

Output

3

score 3 · Answer 2 · answered Dec 27 '16 at 12:08

3

Well the idea of streams is to process the items in the stream independently of each other. The great benefit of the pattern is that you can parallelize the execution since the design of stream APIs is concurrent(i.e. you should not maintain a state between the processing of sequential items of the stream). In your particular task the usage of arrays is most appropriate.

answered Dec 27 '16 at 12:08

egelev

1,175
2
11
27

I know what you are trying to say. But I wanted to solve it using java 8 streams even if its not the most ideal solution. – Rishikesh Dhokare Dec 27 '16 at 12:12

score 3 · Answer 3 · answered Dec 28 '16 at 07:44

Creating list of sequences and sorting it for longest sequence in the all sequence list.

For example if there is a List[1,2,4,5,6], its broken into :

[[1,2], [4,5,6]]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.function.Supplier;

public class NumberSequence {
    public static void main(String[] args) {
        List<Integer> weekDays = Arrays.asList(1, 2, 4, 5, 6);

        List<List<Integer>> allWeekdaySequences = weekDays.stream()
                                                          .collect(
                                                                    (Supplier<List<List<Integer>>>) ArrayList::new,
                                                                    (sequences, currentElement) -> generateCombinedBatchesFor(sequences, currentElement),
                                                                    List::addAll);

        System.out.println(allWeekdaySequences);

        Optional<List<Integer>> longestSequence = allWeekdaySequences.stream()
                                                           .sorted((seq1, seq2) -> seq2.size() - seq1.size())
                                                           .findFirst();

        System.out.println(longestSequence.isPresent() ? longestSequence.get().size() : "Nothing found!!");
    }

    private static void generateCombinedBatchesFor(List<List<Integer>> sequences, Integer currentElement) {
        if (needsNewSequence(sequences, currentElement)) {
            sequences.add(new ArrayList<>());
        }
        getLastSequence(sequences).add(currentElement);
    }

    private static boolean needsNewSequence(List<List<Integer>> sequences, Integer currentElement) {
        return sequences.size() == 0 || !isConsecutiveDay(getLastElement(getLastSequence(sequences)),
                currentElement);
    }

    private static boolean isConsecutiveDay(Integer lastElement, Integer currentElement) {
        return currentElement - lastElement == 1;
    }

    private static Integer getLastElement(List<Integer> lastSequence) {
        return !lastSequence.isEmpty() ? lastSequence.get(lastSequence.size()-1) : -1;
    }

    private static List<Integer> getLastSequence(List<List<Integer>> sequences) {
        return sequences.get(sequences.size()-1);
    }
}

Output

3

score 2 · Answer 4 · edited May 23 '17 at 11:53

2

For that you would need a partial reduction (batching), which the java 8 stream API does not provide.

You can either implement that yourself through spliterators (similar to this answer) or use a library that offers it, such as streamex or proton-pack

edited May 23 '17 at 11:53

Community

1
1

answered Dec 27 '16 at 12:40

the8472

40,999
5
70
122

score 2 · Answer 5 · answered Dec 28 '16 at 07:57

If you don't mind using third party libraries, I may recommend my free StreamEx library which enhances the standard Stream API and, among other things, provides operators for partial reduction:

StreamEx.of(weekDays)
        .collapse((a, b) -> b - a == 1, Collectors.counting())
        .max(Comparator.naturalOrder())

Here the collapse is a partial reduction operator. The first BiPredicate tells for given adjacent pair of elements whether they should be reduced together or new reduction group should start. Here the rule is that adjacent elements should differ by 1. The second parameter is a collector used to perform a reduction (simply counting() collector here). So after collapse we have the stream of group lengths (2 and 3 for your input). Finally we use a standard max() operator.

StreamEx library is fully compatible with Stream API (Stream created by StreamEx can be used as normal stream). The collapse operator is lazy, quite fast and parallel friendly.

Find longest consecutive numbers in a list of sorted numbers using java 8 stream

5 Answers5