CODEWITHSUNDEEP
javaarraysintegersequence
Rilind Ramadani
Rilind Ramadani

Reputation: 11

How to extract longest consecutive sequence of integers from array in Java?

I want is to display all consecutive sequences from a given array of ints. Finally I want to display the longest one with text.

What I tried

Below is only a small piece of code, because I know the rest doesn't work:

int[] myArray = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
ArrayList<Integer> secuence = new ArrayList<>();
Arrays.sort(myArray);

for (int i = 0; i < myArray.length - 1; i++) {
  if ((myArray[i] + 1) == myArray[i + 1] || (myArray[i] - 1) == myArray[i - 1]) {
    secuence.add(myArray[i]);
  }
}

I tried many different ways, but can't figure out.

Upvotes: 1

Views: 1688

Answers (3)

Tamzid Haque
Tamzid Haque

Reputation: 1

public class consecutive {

    public static void main(String[] args) {
        LongestConsecutive();
    }

    public static void LongestConsecutive() {

        int[] a = {56,57,58,89,45,46,47,48,12,52,31};
        int count=1; int max=0;
        int l = a.length-1;
        int i =0;
        //Arrays.sort(a); optional 
        while(i<l) {
            if(a[i] == a[i+1]-1) {
                count = count+1;
                i++;
            } else
                max = Math.max(max, count);
                i++;
        }
        System.out.println("The Longest Consecutive Array: " + max);
    }
}

Upvotes: 0

hc_dev
hc_dev

Reputation: 9377

I approached the solution as follows:

Data structures

  1. a consecutive sequence (what we want to find) is a List of at least 2 consecutive Integers (pair)
  2. to return all foundSequences you need one result List containing 0 or more Lists
  3. to check for consecutive-ness you need the current and previous element

Algorithm

Logic applied (if):

  1. Consecutive-ness is found if current == previous + 1, otherwise an existing consecutive sequence is broken
  2. If a sequence has at least 2 elements, i.e. sequence.size() > 1, then it should be added to the result list (i.e. foundSequences)
  3. Before the first element and after each broken sequence, the previous == null
  4. After the last element there could be an open sequence with sequence.size() > 1. If so, then this sequence is not broken, but completed and should be added to the result list (i.e. foundSequences)

Iterating over elements (loop):

  1. Use a for-each loop to process all elements of the (sorted!) array
  2. The for-loop automatically fills the current element (iterating variable)
  3. You must keep track of the previous element (thus initialized null before the loop). It must archive the current element of each loop, so we can compare the next element against it.
  4. Unless the current element is not consecutive anymore (a break happened), then the previous will become null to start a fresh collection.
  5. In case of a break the currently found sequence may be added to the result. Then the sequence needs to be reset to null to start a fresh collection.
  6. After the last element was checked and the loop ended, there could be still a sequence (that was not yet broken). This needs to be added to the result. 8.

Source

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class ConsecutiveSequenceFinder {

    private int[] unsortedNumbers;

    public ConsecutiveSequenceFinder(int[] numbers) {
        this.unsortedNumbers = numbers;
    }

    public int[] sorted() {
        int[] sortedNumbers = Arrays.copyOf(this.unsortedNumbers, this.unsortedNumbers.length);
        Arrays.sort(sortedNumbers);
        return sortedNumbers;
    }

    public List<List<Integer>> findSequences() {
        // one sequence is List of integers; thus list of sequences is list of list of integers
        List<List<Integer>> foundSequences = new ArrayList<>();
        // first we sort the array
        int[] ascending = this.sorted();
        // this working variable will hold the currently found sequence
        List<Integer> sequence = new ArrayList<Integer>();
        Integer previous = null;
        System.out.println("Finding sequences ..");
        for (int current : ascending) {
            // check if current value is first or one more than (consecutive to) previous
            if (previous == null || current == previous + 1) {
                sequence.add(current);
                previous = current;
            } else {
                System.out.printf("\tsequence of %d consecutive is broken at: %d\n", sequence.size(), current);
                // if sequence found (at least a pair) then add
                if (sequence.size() > 1) {
                    foundSequences.add(sequence);
                }
                // and finally prepare a new sequence, to collect fresh again
                sequence = new ArrayList<>();
                previous = null;
            }
        }
        // if sequence left, then add
        if (sequence.size() > 1) {
            System.out.printf("\tsequence of %d consecutive was completed with last array element\n", sequence.size());
            foundSequences.add(sequence);
        }
        return foundSequences;
    }

    public static void main (String[] args) throws java.lang.Exception {
        // demo numbers
        int[] values = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
        // starting demo
        System.out.println("Input: " + Arrays.toString(values));
        ConsecutiveSequenceFinder finder = new ConsecutiveSequenceFinder(values);
        System.out.println("Sorted: " + Arrays.toString(finder.sorted()));
        List<List<Integer>> foundSequences = finder.findSequences();
        System.out.println("Found sequences: " + foundSequences.size());
        // print for each sequence the size and its elements
        for (List<Integer> sequence : foundSequences) {
            System.out.printf("\t %d elements: %s\n",sequence.size(), sequence.toString());
        }
        // check for each sequence if it is the longest
        List<Integer> longestSequence = new ArrayList<>();
        for (List<Integer> sequence : foundSequences) {
            if (sequence.size() > longestSequence.size()) {
                longestSequence = sequence;
            }
        }
        System.out.printf("Longest sequence has %d elements: %s\n",longestSequence.size(), longestSequence.toString());
    }
}

Actual Output

Input: [202, 203, 204, 205, 206, 100, 1, 3, 200, 2, 4, 201, 5]
Sorted: [1, 2, 3, 4, 5, 100, 200, 201, 202, 203, 204, 205, 206]
Finding sequences ..
    sequence of 5 consecutive is broken at: 100
    sequence of 7 consecutive was completed with last array element
Found sequences: 2
     5 elements: [1, 2, 3, 4, 5]
     7 elements: [200, 201, 202, 203, 204, 205, 206]
Longest sequence has 7 elements: [200, 201, 202, 203, 204, 205, 206]

Process finished with exit code 0

Upvotes: 0

tevemadar
tevemadar

Reputation: 13195

A couple remarks, suggestions:

  • As sort() sorts the array in increasing order, actually you do not have to check for decreasing elements
  • For finding the "anything"est thing, you need to store the "anything"est thing found so far, and a current candidate. This applies to finding largest element or longest sequence of consecutive elements too
  • For dealing with subparts of an array, it is not necessary to make an actual copy of the elements, it is enough to store beginning index and ending index or length.

Putting them together:

var myArray = [202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5];
myArray.sort((a,b)=>a-b);
console.log("Sorted array:",...myArray);

var longstart=0;
var longlength=0;

var currstart=0;
while(currstart<myArray.length){
  var currlength=0;
  while(currstart+currlength<myArray.length
    && myArray[currstart]+currlength==myArray[currstart+currlength])
    currlength++;
  if(currlength>longlength){
    longlength=currlength;
    longstart=currstart;
  }
  console.log("Sequence:",...myArray.slice(currstart,currstart+currlength));
  currstart+=currlength;
}
console.log("Longest:",...myArray.slice(longstart,longstart+longlength));

This code is JavaScript so it can be run here, a Java variant (just with less printing) would look very similar:

int[] myArray = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
Arrays.sort(myArray);

int longstart=0;
int longlength=0;

int currstart=0;
while(currstart<myArray.length){
  int currlength=0;
  while(currstart+currlength<myArray.length
    && myArray[currstart]+currlength==myArray[currstart+currlength])
    currlength++;
  if(currlength>longlength){
    longlength=currlength;
    longstart=currstart;
  }
  currstart+=currlength;
}
for(int i=0;i<longlength;i++)
  System.out.print((i==0?"Longest: ":", ")+myArray[longstart+i]);

The key thing is to have the check work with a growing distance, so the fixed [i]+1==[i+1] check in your initial code became [i]+distance==[i+distance].

Upvotes: 1

Related Questions