Finds the length of the longest chain of consecutive integers in an unsorted list.

FindLongestConsecutiveIntegerLength.java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

/**
 * @author Roi Atalla
 */
public class FindLongestConsecutiveIntegerLength {
  public static void main(String[] args) {
    printLongestConsecutiveInterval(Arrays.asList(1, 2, 3, 4, 5, 6)); // should be 6
    printLongestConsecutiveInterval(Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29)); // should be 1
    printLongestConsecutiveInterval(Arrays.asList(1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, -1, -3, -4, -6, -7, -8, -9, -10, -11, -12, -13)); // should be 8
  }
  
  // best case scenario: entire list is consecutive integers with (n+2) hits.
  // worst case scenario: no consecutive integers with (3n) hits.
  public static void printLongestConsecutiveInterval(List<Integer> values) {
    HashSet<Integer> set = new HashSet<>(values);
    
    int bestCount = 1;
    
    int hits = 0;
    int replacements = 0;
    
    // Get a new iterator each time otherwise we see a ConcurrentModificationException
    for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext(); iterator = set.iterator()) {
      int value = iterator.next();
      iterator.remove();
      
      hits++;
      
      int currentCount = 1;
      int currentValue = value + 1;
      hits++;
      while(set.remove(currentValue++)) {
        hits++;
        currentCount++;
      }
      currentValue = value - 1;
      hits++;
      while(set.remove(currentValue--)) {
        hits++;
        currentCount++;
      }
      
      if(currentCount > bestCount) {
        replacements++;
        bestCount = currentCount;
      }
    }
    
    System.out.println(values);
    System.out.printf("Input: %d, hits: %d, replacements: %d, longest length: %d\n\n", values.size(), hits, replacements, bestCount);
  }
}