Find Longest Consecutive Sequence in Java
Problem
A consecutive sequence is a run of integers that increase by exactly one each step, like 1, 2, 3, 4 — the elements don't need to be next to each other in the original array, only present somewhere in it.
Given an unsorted array of integers, find the length of its longest run of consecutive integers.
Java Program
import java.util.HashSet;
import java.util.Set;
public class LongestConsecutiveSequence {
public static void main(String[] args) {
int[] arr = {8, 1, 9, 3, 10, 4, 2};
Set<Integer> numSet = new HashSet<>();
for (int num : arr) numSet.add(num);
int longest = 0;
for (int num : numSet) {
// Only start counting from a number with no predecessor in the set
if (!numSet.contains(num - 1)) {
int length = 1;
int current = num;
while (numSet.contains(current + 1)) {
current++;
length++;
}
longest = Math.max(longest, length);
}
}
System.out.println("Longest consecutive sequence: " + longest);
}
}Output
Core Logic
Only starting a count from a number that has no predecessor in the set avoids re-walking the same sequence from every one of its members.
- 1Every element is added to a
HashSet<Integer>namednumSet, which also removes any duplicates. - 2For each number in the set,
!numSet.contains(num - 1)checks whether it's the start of a sequence — a number with no predecessor present. - 3Only sequence starts trigger a count: a
whileloop walks forward throughnum + 1,num + 2, and so on, as long as each next number is also in the set. - 4The longest run found across every sequence start becomes the final answer.
[8, 1, 9, 3, 10, 4, 2], 1 has no predecessor and starts a walk through 1, 2, 3, 4 — length 4; 8 also has no predecessor and starts a walk through 8, 9, 10 — length 3. The longer of the two, 4, is reported.Key Point: Skipping numbers that DO have a predecessor in the set is what keeps this O(n) overall — every number is only ever walked as part of one sequence, the one starting from its true beginning.
Why: Building the set costs O(n), and although there's a while loop inside a for loop, every number is only ever visited by the inner while loop once across the entire run, since only true sequence starts trigger a walk.
Key Concepts
Approach 2: Sorting
import java.util.Arrays;
public class LongestConsecutiveSequenceSort {
public static void main(String[] args) {
int[] arr = {8, 1, 9, 3, 10, 4, 2};
Arrays.sort(arr);
int longest = 1, currentLength = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1] + 1) {
currentLength++; // genuine consecutive step
} else if (arr[i] != arr[i - 1]) {
currentLength = 1; // gap found, start a fresh run
}
longest = Math.max(longest, currentLength);
}
System.out.println("Longest consecutive sequence: " + longest);
}
}
Output
Core Logic
Sorting the array first lines up every consecutive run into an adjacent stretch, so a single pass counting consecutive steps finds the longest one.
- 1
Arrays.sort(arr)puts every element into ascending order. - 2A running
currentLengthincreases by one whenever the current element is exactly one more than the previous — a genuine consecutive step. - 3A repeated value, where
arr[i] == arr[i - 1], is skipped without breaking or extending the run, since duplicates don't start a new sequence. - 4Any other gap resets
currentLengthback to1, starting a fresh run from the current element.
[8, 1, 9, 3, 10, 4, 2] gives [1, 2, 3, 4, 8, 9, 10]; the run from 1 to 4 has length 4, and the run from 8 to 10 has length 3 — the longer one, 4, is reported.Key Point: This trades the HashSet version's O(n) time for O(n log n), since sorting dominates the cost — but it needs no extra data structure beyond the array itself.
Why: Arrays.sort() dominates the cost with its O(n log n) comparison sort, while the single pass afterward only needs a couple of running counters.