Longest Consecutive Sequence in Java DSA: Brute Force, Sorting, and the HashSet Trick

Solve Longest Consecutive Sequence in Java DSA three ways — brute force, sorting, and the O(n) HashSet trick — with full step-by-step dry runs for beginners.

1. Introduction

The Longest Consecutive Sequence in Java is a problem that looks harder than it really is. You get an array of numbers that sit in no special order. Your job is to find the length of the longest run of numbers that follow each other, like 1, 2, 3, 4.

The numbers do not have to be next to each other in the array. They just need to exist somewhere in it. So an array like 100, 4, 200, 1, 3, 2 hides the run 1, 2, 3, 4 scattered across it, and the answer is 4.

There is one twist that makes this fun. The best solution runs in linear time, even though sorting feels like the obvious path. That gap between the easy idea and the fast idea is what interviewers love to test.

We build the answer in three steps, like always. Brute force checks every number as a possible start. Sorting lines the numbers up first. The HashSet trick skips sorting and still finishes in one pass over the data.

Every approach gets a full, step-by-step dry run on the same array. Nothing is skipped, so you can watch each number get checked and see exactly why the count grows or resets.

2. Understanding the Problem

Let us pin down the rules before we write any code.

• You get an array of integers, for example nums = 100, 4, 200, 1, 3, 2, 4.
• Return the length of the longest run of consecutive numbers.
• Consecutive means each number is exactly one more than the last, like 1, 2, 3, 4.
• The numbers can sit anywhere in the array, in any order.
• Duplicates do not add to the length. Two 4’s still count as one 4.

For our array the answer is 4, because the numbers 1, 2, 3, 4 all appear. The stray 100 and 200 sit alone, and the extra 4 is just a repeat that changes nothing.

3. Concepts You Need Here

3.1 A Sequence Grows One Step at a Time

A consecutive run is built by adding one each time. If you have the number 1, you look for 2. If 2 is there, you look for 3, and so on until the next number is missing.

• The run length is how many numbers you chained together this way.
• A missing next number ends the run right there.

3.2 A HashSet Gives Instant Lookups

A HashSet stores numbers and lets you ask “is this number here?” almost instantly. That single power is what turns a slow search into a fast one.

• Checking if a number exists in a set takes O(1) time on average.
• A set also drops duplicates for free, so repeats stop bothering us.

4. Approach 1: Brute Force

Take each number and pretend it starts a run. From that number, look for the next one, then the one after that, and keep going. Count how far you get. Do this for every number and keep the longest count you saw.

4.1 Pseudocode

best = 0

for each num in nums:
    current = num
    length = 1

    while (current + 1) exists in nums:   // scan the array
        current = current + 1
        length = length + 1

    best = max(best, length)

return best

4.2 Pseudocode Explained

The plan is simple to picture. We treat every number as if it might be the first number of a run, then measure how long that run stretches. Whichever start gives the longest run wins.

Setting up the tracker. Before the loop, best starts at 0. This one variable remembers the longest run we have seen across all starting points. It only ever moves up, never down.

Starting a fresh run. For each number in the array, two things get set:

• current holds the number we are standing on right now. It begins at the number itself.
• length holds how many numbers this run has so far. It begins at 1, because the start number alone is already a run of one.

Growing the run. The while loop asks one question over and over: is current + 1 somewhere in the array? Each time the answer is yes, the run can reach one number higher.

• We move current up by one, so we are now standing on the next number.
• We add one to length, because the run just got one number longer.
• The loop keeps repeating with the new current, chaining numbers together.

Ending and saving. The moment current + 1 is missing from the array, the run cannot grow, so the while loop stops. Then best = max(best, length) keeps whichever is bigger, the old best or this run. After every number has taken its turn as a start, best holds the answer.

4.3 Java Code

public class LongestConsecutiveBrute {

    public static int longestConsecutive(int[] nums) {
        int best = 0;
        for (int num : nums) {
            int current = num;
            int length = 1;
            while (contains(nums, current + 1)) {
                current = current + 1;
                length = length + 1;
            }
            best = Math.max(best, length);
        }
        return best;
    }

    private static boolean contains(int[] nums, int target) {
        for (int n : nums) {
            if (n == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2, 4};
        System.out.println(longestConsecutive(nums)); // 4
    }
}

4.4 Java Code Explained

This is the same plan in Java. The helper method contains does the searching for us, so the main logic stays clean.

• Line 4 sets best to 0. Every run we find will be compared against it.
• Line 5 loops over each number and treats it as a possible start.
• Lines 8 to 11 grow the run. contains scans the whole array to check if the next number is present.
• Line 12 saves the longest run using Math.max.
• The contains helper on lines 17 to 24 walks the array and returns true the moment it finds the target.

4.5 Dry Run of the Brute Force

Let us trace the array nums = 100, 4, 200, 1, 3, 2, 4. We treat each number as a start and see how far its run goes. Every time we ask for a next number, contains scans the array to answer.

After checking all seven numbers, the longest run we saw was 4, from the start number 1. So the method returns 4.

4.6 Reading the Dry Run

Let us walk every starting number one at a time. For each, we watch the while loop ask for the next number, and we see why the run either grows or dies right away.

Start 100. We set current to 100 and length to 1. The while loop now asks if 101 is in the array. contains scans all seven numbers, 100, 4, 200, 1, 3, 2, 4, and finds no 101. So the loop never runs even once. The run stays at length 1. Since best was 0, best = max(0, 1) makes best become 1.

Start 4 (the first 4). Next we set current to 4 and length to 1. The loop asks if 5 is in the array. contains scans everything and finds no 5. The loop stops immediately, so this run is length 1. best = max(1, 1) leaves best at 1, unchanged.

Start 200. Now current is 200 and length is 1. The loop asks for 201. Again contains finds nothing, so the run is length 1. best stays at 1. Notice a pattern forming: every lone number with no neighbour above it dies at length 1.

Start 1, the long run. Here we set current to 1 and length to 1, and this time the loop keeps going. Let us trace each pass:

• Pass 1: the loop asks for 2. contains finds 2 in the array. So current becomes 2 and length becomes 2.
• Pass 2: now the loop asks for 3, since current is 2. contains finds 3. So current becomes 3 and length becomes 3.
• Pass 3: the loop asks for 4, since current is 3. contains finds 4 (either copy works). So current becomes 4 and length becomes 4.
• Pass 4: the loop asks for 5, since current is 4. contains finds no 5, so the loop stops here.

The run ended at length 4. best = max(1, 4) jumps best up to 4. This is the answer, though the loop does not know that yet and keeps checking the rest.

Start 3. We set current to 3 and length to 1. The loop asks for 4, finds it, so current becomes 4 and length becomes 2. Then it asks for 5, finds nothing, and stops. This run is length 2. best = max(4, 2) keeps best at 4. Notice we just re-walked 3 to 4, ground the start at 1 already covered.

Start 2. We set current to 2 and length to 1. The loop finds 3, so current becomes 3 and length becomes 2. It then finds 4, so current becomes 4 and length becomes 3. Finally it asks for 5, finds nothing, and stops. This run is length 3, but best stays at 4. Once again we re-walked numbers the start at 1 already handled.

Start 4 (the second 4). The duplicate 4 gets its own turn. current is 4 and length is 1. The loop asks for 5, finds nothing, and stops. Length 1, and best stays at 4.

Two starting numbers, 3 and 2, walked over the exact same 3 to 4 path that the start at 1 already traced. That repeated walking is wasted work, and it is precisely what the HashSet approach removes.

💡 Interview Insight Interviewers often ask “why is brute force slow here?” Point out that many numbers re-walk the same run. Starting at 1, 2, and 3 all end at 4, so the same steps get repeated again and again.

4.7 Time and Space Cost

• Time is O(n squared) or worse, because each contains call scans the whole array.
• Space is O(1), since we only use a couple of counters.

The brute force is easy to picture, but that repeated scanning kills its speed. Sorting is our next step, and it removes the need to scan for every next number.

5. Approach 2: Sort the Array

Sort the numbers first. Once they are in order, a consecutive run sits right next to each other. Walk the sorted array and count how long each run of back-to-back numbers gets. Duplicates are skipped so they do not break the count.

5.1 Pseudocode

if nums is empty:
    return 0

sort(nums)

best = 1
current = 1

for i from 1 to length(nums) - 1:
    if nums[i] == nums[i-1]:
        skip   // duplicate, ignore
    else if nums[i] == nums[i-1] + 1:
        current = current + 1
        best = max(best, current)
    else:
        current = 1   // run broke, reset

return best

5.2 Pseudocode Explained

Once the numbers are sorted, a consecutive run turns into a stretch of neighbours that each go up by exactly one. So instead of searching, we just walk left to right and watch the gaps between neighbours.

The empty guard. First we handle the empty array. With no numbers there is no run at all, so we return 0 straight away. This also stops us from reading nums[i-1] when there is nothing to read.

The two trackers. After sorting, we set up two variables, both starting at 1:

• current is the length of the run we are building right now, as we walk.
• best is the longest run we have finished seeing so far. It starts at 1 because a single number already counts as a run of one.

Walking and comparing. The loop starts at index 1 so we can always compare nums[i] with the number just before it, nums[i-1]. Each step falls into one of three cases:

• The two numbers are equal. This is a duplicate, so we skip it. Skipping means current stays exactly where it is, so a repeat never grows or breaks the run.
• A number exactly one bigger than the one before means the run continues, so current goes up by one, and best takes the larger of best and current.
• A number that jumps by more than one breaks the run here, so we reset current back to 1 and start counting a fresh run from this number.

The result. Because best only ever climbs and never falls, a reset in the else branch never loses the longest run we already found. After the walk, best holds the answer.

5.3 Java Code

import java.util.*;

public class LongestConsecutiveSort {

    public static int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int best = 1;
        int current = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            } else if (nums[i] == nums[i - 1] + 1) {
                current = current + 1;
                best = Math.max(best, current);
            } else {
                current = 1;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2, 4};
        System.out.println(longestConsecutive(nums)); // 4
    }
}

5.4 Java Code Explained

The Java version follows the same walk. Arrays.sort does the ordering, and continue handles the duplicate case neatly.

• Lines 6 to 8 guard the empty array so we do not read a missing element.
• Line 9 sorts the array in place, so runs line up next to each other.
• Lines 10 and 11 start best and current at 1.
• Line 13 checks for a duplicate. continue jumps to the next number without touching current.
• Lines 15 to 17 handle a step of exactly one, growing the run and saving best.
• Line 19 resets current to 1 when the gap is bigger than one.

5.5 Dry Run of the Sort Approach

We start with nums = 100, 4, 200, 1, 3, 2, 4. After Arrays.sort the array becomes 1, 2, 3, 4, 4, 100, 200. Now we walk from index 1 and compare each number with the one before it.

The legend: current is the length of the run we are on right now, and best is the longest run seen so far.

After the walk, best holds 4, which is the length of the run 1, 2, 3, 4. So the method returns 4.

5.6 Reading the Dry Run

We walk the sorted array 1, 2, 3, 4, 4, 100, 200 from index 1. At every step we compare nums[i] with nums[i-1] and decide which of the three cases we are in. Let us take each index in turn.

Index 1, number 2. We compare 2 with the number just before it, which is 1. The gap is exactly one, so we are in the “one bigger” case. The run is alive, so current climbs from 1 to 2. Then best = max(1, 2) lifts best to 2 as well. Our run so far is 1, 2.

Index 2, number 3. Now we compare 3 with 2. Once more the gap is exactly one, so the run keeps going. current rises from 2 to 3, and best = max(2, 3) lifts best to 3. The run is now 1, 2, 3.

Index 3, number 4. Here we compare 4 with 3. The step is one again, so the run extends. current reaches 4, and best = max(3, 4) lifts best to 4. The run is now 1, 2, 3, 4, and this is the peak.

Index 4, the duplicate 4. This time we compare 4 with the previous 4. They are equal, so we hit the duplicate case and skip. Skipping is important here:

• current is left untouched at 4, so the duplicate does not falsely add to the run.
• best is also left at 4, so nothing is lost.
• If we had not skipped, the equal number would look like a break and wrongly reset current to 1.

Index 5, number 100. We compare 100 with 4. The gap is 96, far more than one, so the run is broken. We fall into the else case and reset current back to 1, starting a fresh run at 100. best stays safely at 4, because the reset only touches current, never best.

Index 6, number 200. Finally we compare 200 with 100. The gap is 100, so again the run breaks. current resets to 1 once more. There is no real run out here among the big numbers, so best holds its 4 all the way to the end.

Sorting did the heavy lifting by placing 1, 2, 3, 4 right next to each other, which made the run trivial to count. The price we paid was the sort itself, and that is the cost the HashSet approach avoids.

💡 Interview Insight A common follow-up is “why not just return the longest run without the duplicate check?” Without skipping duplicates, a repeated number looks like a break and wrongly resets your count. The skip keeps equal neighbours from spoiling the run.

5.7 Time and Space Cost

• Time is O(n log n), because sorting is the heaviest step.
• Space is O(1) extra if the sort is in place, ignoring the sort’s own needs.

Sorting is a big jump over brute force. Still, that log n factor is avoidable. The HashSet approach does the same job in linear time by walking only true starts.

6. Approach 3: HashSet in Linear Time

Put every number in a HashSet. Then, for each number, ask a smart question first: is the number before it in the set? If yes, this number sits in the middle of some run, so skip it. If no, this number is a true start, so walk forward counting until the next number is missing. Because we only ever walk from real starts, each number is touched a small, fixed number of times.

6.1 Pseudocode

put all numbers into a set
best = 0

for each num in set:
    if (num - 1) is NOT in set:   // num is a start
        current = num
        length = 1

        while (current + 1) is in set:
            current = current + 1
            length = length + 1

        best = max(best, length)

return best

6.2 Pseudocode Explained

The whole trick sits in one small question we ask before counting. Instead of walking a run from every number, we only walk from the number that truly begins a run. That single filter is what removes all the repeated work.

Building the set. First we drop every number into a set. The set does two jobs for us. It removes duplicates, so a repeated number cannot cause extra walks. It also lets us check “is this number here?” almost instantly, which we lean on heavily below.

The start check. For each number, we ask: is num – 1 in the set?

• If num – 1 is present, then num sits in the middle or end of some run, not the start. Someone smaller will handle this run, so we skip num entirely.
• If num – 1 is absent, then nothing comes before num. That makes num the true first number of its run, so we count from here.

Walking forward from a start. Once we know num is a start, we set current to num and length to 1. Then the while loop steps forward:

• It checks if current + 1 is in the set. A yes means the run reaches one higher.
• On a yes, current moves up by one and length grows by one.
• The loop stops the moment current + 1 is missing, which marks the end of this run.

Why this stays fast. Because we only ever walk from a real start, each run is counted exactly once, no matter how many of its numbers we loop over. After all numbers are checked, best = max(best, length) leaves the answer in best.

6.3 Java Code

import java.util.*;

public class LongestConsecutiveSet {

    public static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        int best = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;
                while (set.contains(current + 1)) {
                    current = current + 1;
                    length = length + 1;
                }
                best = Math.max(best, length);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2, 4};
        System.out.println(longestConsecutive(nums)); // 4
    }
}

6.4 Java Code Explained

The code builds the set, then loops over it. The single if on line 12 is the whole idea, and set.contains gives the fast lookups.

• Lines 6 to 9 fill the set with every number, dropping duplicates on the way.
• Line 10 sets best to 0 for the longest run.
• Line 12 checks if num minus 1 is absent. Only then is num a real start.
• Lines 15 to 18 walk forward while the next number keeps existing, counting as they go.
• Line 19 saves the run length in best.

6.5 Dry Run of the HashSet Approach

We start with nums = 100, 4, 200, 1, 3, 2, 4. First we build the set, which drops the duplicate 4. The set holds 1, 2, 3, 4, 100, 200.

Now we loop over the set. For small integers Java visits them in rising order, so we go 1, 2, 3, 4, 100, 200. For each one, we first check if the number below it is present.

Only the true starts 1, 100, and 200 triggered a walk. The start at 1 gave the run of length 4, and the method returns 4.

6.6 Reading the Dry Run

We loop over the set 1, 2, 3, 4, 100, 200. For each number, the first thing we do is the start check: is the number one smaller in the set? That check decides whether we walk or skip. Let us go through each number.

num = 1, a true start. We ask if 0 is in the set. It is not, so 1 has nothing before it, which makes it a real start. We set current to 1 and length to 1, then walk forward:

• Pass 1: we check for 2. It is in the set, so current becomes 2 and length becomes 2.
• Pass 2: we check for 3. It is in the set, so current becomes 3 and length becomes 3.
• Pass 3: we check for 4. It is in the set, so current becomes 4 and length becomes 4.
• Pass 4: we check for 5. It is not in the set, so the walk stops.

This run finished at length 4, so best = max(0, 4) sets best to 4. The entire longest run got counted in this one walk.

num = 2, skipped. We ask if 1 is in the set. It is, so 2 is not a start, it sits in the middle of a run. We skip it without walking at all. This matters: the run through 2 was already counted when we started at 1, so walking again would be pure waste.

num = 3, skipped. We ask if 2 is in the set. It is, so 3 is not a start either. We skip it. Again, the run covering 3 was already handled by the start at 1.

num = 4, skipped. We ask if 3 is in the set. It is, so 4 is not a start. We skip it too. So the three numbers 2, 3, and 4 each cost only a single set lookup, not a full walk. That is the exact repeated work that made brute force slow, now avoided.

num = 100, a lone start. We ask if 99 is in the set. It is not, so 100 is a start. We set current to 100 and length to 1, then check for 101. It is missing, so the walk stops at once. This run is length 1, and best = max(4, 1) keeps best at 4.

num = 200, another lone start. We ask if 199 is in the set. It is not, so 200 is a start as well. We check for 201, find nothing, and stop. This run is also length 1, so best stays at 4 to the very end.

The heart of this approach is that start check. It guarantees we only walk a run from its first number, so no number is ever part of two walks. Add up all the walk steps and they total the number of elements, which is why the whole method runs in linear time.

💡 Interview Insight The classic question is “how is this O(n) when there is a loop inside a loop?” Explain that the inner while only runs from a start, and each number is visited by at most one walk. So across the whole run the inner steps add up to n, not n squared.

6.7 Comparing the Three Traces

7. Comparing the Three Approaches

All three return the same answer. They just pay different prices to get there.

The HashSet spends extra memory to store the set, but it buys linear time in return. That trade is almost always worth it for this problem.

In an interview, mention brute force to show you understand the naive path. Then bring up sorting as a clear improvement. Land on the HashSet for the linear-time answer, and be ready to explain why the inner loop does not make it quadratic.

💡 Interview Insight If pushed on the space cost, admit the set uses O(n) memory. Then point out that this is the price for skipping the sort and reaching O(n) time, which is the whole goal of the problem.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Forgetting the num minus 1 check turns the HashSet version back into slow, repeated walking.
• Missing the duplicate skip in the sort version makes a repeated number wrongly reset the count.
• Returning 0 for a single-element array is wrong. One number is a run of length 1.
• An empty array must return 0, so guard it before you read any element.
• Negative numbers work fine, since consecutive just means a step of one either way.

Run an empty array and a single-number array through your code before you call it done. These edge cases catch more bugs than any normal input will.

9. Interview Questions

10. Conclusion

The Longest Consecutive Sequence in Java teaches a habit worth keeping: a smart check can beat a heavy tool. Sorting feels natural, but a set plus one clever question does the job faster.

Our seven-number array showed the payoff clearly. Brute force wasted effort re-walking the same run. Sorting lined things up but paid for the ordering. The HashSet walked each run exactly once and finished in linear time.

So take the pattern, not just the answer. When you find yourself re-doing the same work, look for a way to start only from the real beginning. That single idea shows up again and again in array problems.

Master this one, and you will spot the same trick in many harder questions further down the list.

11. Further Reading

• LeetCode Longest Consecutive Sequence problem — practice the original problem and submit your own solution.
• Oracle Java HashSet documentation — the official reference for the set used in the fast approach.
• Previous in this series: Top K Frequent Elements in Java — find the k numbers that appear most often using a bucket or a heap.
• Next in this series: Subarray Sum Equals K in Java — count subarrays that add up to a target using a running sum and a map.