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

Issue

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]}

Solution

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: []

Answered By – IamGroot

Answer Checked By – David Marino (FixeMe Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *