Find all longest ascending(not necessarily consecutive) number sequences in List

Question

I am given an array of numbers(unsorted):

[1,2,1,2,3,1,3,7]

My task is to write a method which returns ALL longest ascending sequences of numbers. In this case for given input,the output should be:

[[1,2,3],[1,3,7]]

I have a problem in appending arrays in resulting list

public List<List<Integer>> getAscendingSequences(String url) {
    List<Integer> numbers = createListFromFile(url);
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> longestArray = new ArrayList<>();
    List<Integer> currentArray = new ArrayList<>();
    int maxSize = 0;
    for (int i = 1; i < numbers.size(); i++) {
        if (currentArray.isEmpty()) {
            currentArray.add(numbers.get(i - 1));
        }
        if (numbers.get(i) > numbers.get(i - 1)) {
            currentArray.add(numbers.get(i));
        } else {
            if (longestArray.size() < currentArray.size()) {
                longestArray.clear();
                longestArray.addAll(currentArray);
            }
            if(currentArray.size()==longestArray.size()){
                results.add(currentArray);
            }
            currentArray.clear();
        }
    }
    results.add(longestArray);
    return results;
}

This returns {[1,3,7],[1,3,7],[1,2,3]}

Answer 1

I'm coming a bit late to this, but this sort of problem is quite amenable to array programming techniques such as those that appear in APL and J programming languages. (The solution is probably a one-liner in those languages.) A transliteration into Java is somewhat verbose, though not as verbose as conventional iterative techniques. Here's my solution; discussion below.

List<List<Integer>> getAscendingSequences(List<Integer> in) {
    var edges = IntStream.rangeClosed(0, in.size())
                         .filter(i -> i == 0 || i == in.size() || in.get(i-1) >= in.get(i))
                         .boxed()
                         .toList();

    int max = IntStream.range(0, edges.size()-1)
                       .map(i -> edges.get(i+1) - edges.get(i))
                       .max()
                       .orElse(0);

    return IntStream.range(0, edges.size()-1)
                    .filter(i -> /* max > 1 && */ max == edges.get(i+1) - edges.get(i))
                    .mapToObj(i -> in.subList(edges.get(i), edges.get(i+1)))
                    .toList();
}

The approach is conceptually similar to that shown in IamGroot's answer: first, run through the array and find ascending sequences; second, run through the sequences and find the maximum length; and third, select the sequences whose lengths match the maximum length. However, the implementation technique is completely different. Instead of loops, it uses the IntStream-over-indexes trick.

There are three stream pipelines.

The first finds the indexes of "edges" of the sequences. The key insight is that a the beginning of a new sequence occurs when the previous value is greater or equal to the current one. (This is the inverse of the more intuitive condition: we are in the midst of an ascending sequence if the previous value is less than the current value.) The filter condition also includes special cases for indexes zero and size. The resulting edges list contains indexes of all the boundaries of ascending sequences, including the head and tail boundaries.

Note that there is one more index in the edges list than there are ascending sequences. This is because each sequence is the half-open interval (lower-inclusive, upper-exclusive) between each pair of boundaries.

The second stream determines the length of each sequence by subtracting the lower boundary from the higher boundary, and then it finds the maximum length of all sequences.

The third stream processes every sequence again and selects only those whose length equals the maximum length. The sequence boundaries are also converted into a sequence using the List::subList method, which avoids creation and copying of a bunch of temporary lists.

To me, it's possible for there to be ascending sequences of length one. If you don't like these, it can be filtered out by uncommenting the additional condition in the filter of the third stream pipeline.

Sample output:

Input:  [1, 2, 1, 2, 3, 1, 3, 7]
Output: [[1, 2, 3], [1, 3, 7]]

Input:  [1, 2, 1, 2, 3, 1, 3, 7, 1, 3, 8]
Output: [[1, 2, 3], [1, 3, 7], [1, 3, 8]]

Input:  [1, 2, 1, 2, 3, 1, 3, 7, 8]
Output: [[1, 3, 7, 8]]

Input:  [3, 2, 1]
Output: [[3], [2], [1]]

Input:  [1, 1, 1, 1, 2, 3, 4]
Output: [[1, 2, 3, 4]]

Input:  [1, 2]
Output: [[1, 2]]

Input:  [1]
Output: [[1]]

Input:  []
Output: []

Answer 2

You can try with this approach, it is slightly different from your implementation of the logic.

Approach Here:

The below logic will prepare the listOfList with all the sequences that are in ascending order and then I am finding the maximum sequence size i.e highestListSize as the task is to prepare the list with longest sequence so, filtering the main list based on this size.

public static List<List<Integer>> getAscendingSequences(String url) {
        List<Integer> numbers = createListFromFile(url);
        List<List<Integer>> listOfList = new ArrayList<>();
        int count = 0;
        List<Integer> list = new ArrayList<>();
        for (int j = count; j < numbers.size() - 1; j++) {
            if (numbers.get(j + 1) > numbers.get(j)) {
                list = new ArrayList<>(list);
                if (!list.contains(numbers.get(j))) {
                    list.add(numbers.get(j));
                }
                list.add(numbers.get(j+1));
            } else {
                list = new ArrayList<>();
                count++;
            }
            if (!list.isEmpty()) {
                listOfList.add(list);
            }
        }
        if(!listOfList.isEmpty()){
          int highestListSize = listOfList.stream().mapToInt(List::size).max()
                                                   .getAsInt();
        listOfList = listOfList.stream().filter(x -> x.size() == highestListSize)
                                   .collect(Collectors.toList());
          } else {
                  listOfList = Collections.emptyList();
                }
       return listOfList;
    }

Testcases:

Input: {1, 2 ,1 ,2 ,3 ,1 ,3 ,7 ,1 ,3 ,8}
Output: [[1, 2, 3], [1, 3, 7], [1, 3, 8]]

Input: {1,2,1,2,3,1,3,7}
Output: [[1, 2, 3], [1, 3, 7]]

Input: {1,2,1,2,3,1,3,7,8}
Output: [[1, 3, 7, 8]]

Input: {3,2,1}
Output: []

Answer 3

Check this out, the problem in the code was that it wasn't handling last occurrence :-

public static List<List<Integer>> getAscendingSequences(String url) {
        List<Integer> numbers = createListFromFile(url);
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> longestArray = new ArrayList<>();
        List<Integer> currentArray = new ArrayList<>();
        boolean set = false;
        for (int i = 1; i < numbers.size(); i++) {
            set = true;
            if (currentArray.isEmpty()) {
                currentArray.add(numbers.get(i - 1));
                set = false;
            }
            if (numbers.get(i) > numbers.get(i - 1)) {
                currentArray.add(numbers.get(i));
                set = false;
            } else {
                if (longestArray.size() < currentArray.size()) {
                    longestArray.clear();
                    longestArray.addAll(currentArray);
                }
                currentArray.clear();
            }
        }
        results.add(longestArray);
        // For handling last running condition
        if(!set && currentArray.size() == longestArray.size()) {
            results.add(currentArray);
        }
        // For handling condition where last running condition was greater than existing
        if(!set && currentArray.size() > longestArray.size()) {
            results.clear();
            results.add(currentArray);
        }
        return results;
    }