Senior 5 min · March 05, 2026

Longest Consecutive Sequence — O(n²) Bug in Login Streak

Q: What is the time complexity of the longest consecutive sequence using a hash set?

It's O(n) time and O(n) space. The set is built in one linear pass, and although there's a nested while loop in the algorithm, each number is visited by the while loop at most once across all outer-loop iterations — that's amortised O(n) for the whole traversal, not O(n²).

Q: Why does the longest consecutive sequence problem use a HashSet and not a HashMap?

You only need to answer 'does this number exist?' — a yes/no question. A HashSet is perfectly designed for membership queries and uses less memory than a HashMap. A HashMap would make sense if you also needed to store metadata per number (like index or frequency), but the core algorithm needs none of that.

Q: Does the algorithm work correctly if the input array has duplicate numbers?

Yes, and it handles them more cleanly than the sorting approach. When you load the array into a HashSet, duplicates are silently dropped because sets only store unique values. The algorithm then operates on unique numbers only, so duplicates never inflate the sequence length or cause double-counting.

Q: How do I handle the case where the input contains Integer.MIN_VALUE?

Cast to long before subtraction. In Java, `Integer.MIN_VALUE - 1` wraps to `Integer.MAX_VALUE`, so the guard `!numberSet.contains(num - 1)` checks for the wrong value. Use `!numberSet.contains((long) num - 1)` and store the numbers as Long in the set to avoid underflow.

A missing guard caused 50M inner steps for a 10k streak — the O(n²) bug that almost killed login streaks.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

The algorithm uses a HashSet to find the longest run of consecutive numbers in O(n) time.
Only start counting from sequence starts — numbers without a left neighbour in the set.
Each number is visited at most twice: once as a start candidate, once during a forward walk.
Total work stays O(n) because the inner while loop never revisits elements already counted.
In production, forgetting the start guard turns O(n) into O(n²) for large inputs.

Plain-English First

Imagine you have a shoebox full of random numbered tickets — 4, 2, 100, 3, 1, 101. You want to find the longest unbroken run of numbers, like 1-2-3-4. Instead of sorting all the tickets first, you tip them into a lookup board (a hash set) so you can instantly check 'is this number here?' Then for each ticket, you only start counting a run if it's the very first in a chain — meaning the number one below it is NOT on the board. That's the entire trick: the hash set turns 'does this number exist?' from a slow search into an instant yes-or-no, letting you count every chain in one pass.

Consecutive sequence problems appear everywhere in the real world — think about detecting unbroken login streaks in a fitness app, finding contiguous ID ranges in a database audit, or identifying runs of sensor readings in IoT pipelines. Whenever you need to find structure inside a pile of unsorted numbers, this problem and its pattern keep showing up. It's also one of the most frequently asked medium-level questions at FAANG-tier interviews because it forces you to think about data access patterns, not just loops.

The naive approach — sort the array and scan for breaks — costs O(n log n) and tempts almost everyone at first glance. But sorting is expensive, and it destroys the original order. The real insight is that you don't need sorted order at all. You just need to answer one question in O(1): 'Does the number X exist in the input?' A hash set is purpose-built for exactly that. With it, you can scan the array once and trace every consecutive chain from its true starting point, bringing the total cost down to O(n).

By the end of this article you'll understand exactly why the hash set approach works and not just mechanically how to code it, you'll be able to trace through any example by hand, spot the two most common implementation bugs before they bite you, and confidently explain your reasoning in an interview when the follow-up questions start flying.

Why Sorting Is the Wrong First Instinct

When most developers see 'find the longest run of consecutive numbers', their brain jumps straight to sorting. Sort the array, walk through it, count runs, track the max. Clean, simple, done. And it works — but it's costing you more than you need to pay.

Sorting is O(n log n). For an array of 10 million elements, that's a meaningful difference from O(n). More importantly, the sorting instinct reveals a deeper misunderstanding: you're paying to impose order on the entire dataset when you only care about local neighbourhood relationships — 'is num+1 in the array?' and 'is num-1 in the array?'.

This is the mental shift that separates intermediate from advanced thinking. Instead of restructuring the data, change how you query it. A HashSet gives you O(1) membership checks. Once every number is in the set, you can ask 'does 5 exist?' or 'does 6 exist?' for free, without touching any sorted structure.

The sorted approach also doesn't handle duplicates gracefully without extra logic — you have to skip them manually. The hash set absorbs duplicates automatically because a set stores only unique values. Two problems solved with one data structure choice.

NaiveSortVsHashSet.javaJAVA

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class NaiveSortVsHashSet {

    // ---- APPROACH 1: Sort-based O(n log n) ----
    public static int longestConsecutiveSorting(int[] numbers) {
        if (numbers.length == 0) return 0;

        Arrays.sort(numbers); // O(n log n) — reorders entire array

        int longestRun = 1;
        int currentRun = 1;

        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == numbers[i - 1]) {
                continue; // skip duplicates manually
            }
            if (numbers[i] == numbers[i - 1] + 1) {
                currentRun++; // extend the current run
                longestRun = Math.max(longestRun, currentRun);
            } else {
                currentRun = 1; // break in sequence, reset
            }
        }
        return longestRun;
    }

    // ---- APPROACH 2: HashSet-based O(n) ----
    public static int longestConsecutiveHashing(int[] numbers) {
        // Load every number into a set — O(n) time, duplicates disappear
        Set<Integer> numberSet = new HashSet<>();
        for (int num : numbers) {
            numberSet.add(num);
        }

        int longestRun = 0;

        for (int num : numberSet) {
            // Only start counting from the BEGINNING of a sequence.
            // If (num - 1) exists in the set, this number is NOT a sequence start.
            boolean isSequenceStart = !numberSet.contains(num - 1);

            if (isSequenceStart) {
                int currentNumber = num;
                int currentRun = 1;

                // Walk forward as long as consecutive numbers exist
                while (numberSet.contains(currentNumber + 1)) {
                    currentNumber++;
                    currentRun++;
                }

                longestRun = Math.max(longestRun, currentRun);
            }
        }
        return longestRun;
    }

    public static void main(String[] args) {
        int[] input = {100, 4, 200, 1, 3, 2, 2, 3}; // note duplicate 2s and 3s

        System.out.println("Input: " + Arrays.toString(input));
        System.out.println("Sorting approach:  " + longestConsecutiveSorting(input));
        System.out.println("HashSet approach:  " + longestConsecutiveHashing(input));
    }
}

Output

Input: [100, 4, 200, 1, 3, 2, 2, 3]

Sorting approach: 4

HashSet approach: 4

Why Both Give 4:

The longest run is 1→2→3→4. Duplicates (2, 3 appear twice) don't extend the sequence — they're just noise. The HashSet discards them automatically; the sort approach needs an explicit skip. Same answer, but the HashSet path is cleaner and faster.

Production Insight

Sorting destroys the original order.

In a login streak system, you'd lose the temporal sequence of login days — but for pure length detection, order doesn't matter.

Rule: if you only need membership queries, never sort.

Key Takeaway

Sorting is overkill for neighbourhood queries.

A HashSet answers 'does X exist?' in O(1) — that's all you need.

Trade O(n) space to eliminate O(n log n) time.

The Core Insight — Only Count From Sequence Starts

Here's the question that unlocks everything: what would happen if you started counting a chain from every single number in the set? You'd recount the same sequence multiple times. Starting from 1 you'd count 1→2→3→4 (length 4). Starting from 2 you'd count 2→3→4 (length 3). Starting from 3, length 2. You'd do redundant work proportional to the square of the sequence length in the worst case.

The genius of the algorithm is the guard: only begin a chain-count when the current number has no left-neighbour in the set. If num - 1 is absent, then num must be the true beginning of a consecutive run. You can safely count forward from there, knowing you'll never double-count that sequence.

This single condition — !numberSet.contains(num - 1) — is what keeps the whole algorithm at O(n). Every number is visited at most twice: once when you check it as a potential sequence start, and once when it's stepped over during a forward count from an earlier start. Those two passes across n elements together are still O(n).

Think of it like painting. You only dip your brush at the leftmost edge of each white stripe. You never start mid-stripe. The result: every stripe gets painted exactly once.

LongestConsecutiveSequence.javaJAVA

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {

    public static int findLongestConsecutiveSequence(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return 0; // guard against empty or null input
        }

        // Step 1: Populate the set — O(n)
        // Using a Set means duplicates are ignored for free.
        Set<Integer> numberSet = new HashSet<>();
        for (int num : numbers) {
            numberSet.add(num);
        }

        int longestSequenceLength = 0;

        // Step 2: Iterate over unique numbers only (iterating the set, not the array)
        for (int num : numberSet) {

            // THE KEY GUARD: skip this number if it's not a sequence start.
            // If (num - 1) exists, some smaller number already owns this chain.
            if (numberSet.contains(num - 1)) {
                continue; // not a start — skip entirely
            }

            // We've confirmed: num IS the start of a new consecutive sequence.
            int sequenceStart = num;
            int currentLength = 1;

            // Walk forward one step at a time until the chain breaks
            while (numberSet.contains(sequenceStart + currentLength)) {
                currentLength++; // found the next consecutive number
            }

            // Update the global maximum
            longestSequenceLength = Math.max(longestSequenceLength, currentLength);
        }

        return longestSequenceLength;
    }

    public static void main(String[] args) {
        // Test Case 1: multiple sequences, clear winner
        int[] mixed = {10, 5, 6, 100, 7, 101, 8, 102, 9, 103};
        System.out.println("Test 1 — Mixed sequences:");
        System.out.println("  Input length: " + mixed.length + " numbers");
        System.out.println("  Longest consecutive: " + findLongestConsecutiveSequence(mixed));
        // Sequences: [5,6,7,8,9,10] length 6 and [100,101,102,103] length 4

        // Test Case 2: all elements form one sequence
        int[] continuous = {3, 2, 1, 0, -1, -2};
        System.out.println("\nTest 2 — Continuous descending input:");
        System.out.println("  Longest consecutive: " + findLongestConsecutiveSequence(continuous));

        // Test Case 3: single element
        int[] single = {42};
        System.out.println("\nTest 3 — Single element:");
        System.out.println("  Longest consecutive: " + findLongestConsecutiveSequence(single));

        // Test Case 4: all duplicates
        int[] duplicates = {5, 5, 5, 5};
        System.out.println("\nTest 4 — All duplicates:");
        System.out.println("  Longest consecutive: " + findLongestConsecutiveSequence(duplicates));
    }
}

Output

Test 1 — Mixed sequences:

Input length: 10 numbers

Longest consecutive: 6

Test 2 — Continuous descending input:

Longest consecutive: 6

Test 3 — Single element:

Longest consecutive: 1

Test 4 — All duplicates:

Longest consecutive: 1

Pro Tip: Iterate the Set, Not the Array

Notice the for-loop iterates over numberSet, not the original numbers array. This means duplicates are never visited a second time during the outer loop, tightening the constant factor of your O(n) runtime. It's a small detail that signals precision in interviews.

Production Insight

Forgetting the guard is the #1 reason this algorithm goes O(n²) in prod.

A login streak pipeline with 10M events and one long streak becomes unresponsive.

Rule: always verify that the guard is present before you ship.

Key Takeaway

The guard !numberSet.contains(num - 1) is the entire reason for O(n).

Without it, you get O(n²) on any input with long sequences.

Never implement this algorithm without the start check.

Proving O(n) — Walking Through the Work Count

When interviewers push back with 'but isn't there a nested while loop inside your for loop — doesn't that make it O(n²)?', this is the moment that separates candidates who understand their own code from those who memorised it.

The answer lies in amortised analysis. Ask: how many total times can any single number be visited by the while loop? Exactly once. The while loop only runs when we're at a confirmed sequence start. Every number that gets consumed by a while-loop forward-walk is never itself a sequence start (because its predecessor exists in the set), so it will hit the continue in the outer for-loop and never trigger its own while-walk.

Total outer loop iterations: at most n (one per unique number). Total inner while-loop steps across ALL iterations: also at most n, because each of the n numbers is stepped over by a while loop at most once. That's 2n operations total — O(n).

This is the same amortised reasoning used to prove that a dynamic array's push operation is O(1) amortised. The expensive step is rare and its cost is spread evenly across all operations. Knowing this explanation cold will visibly impress an interviewer.

ComplexityTracer.javaJAVA

import java.util.HashSet;
import java.util.Set;

/**
 * This version adds counters to PROVE the O(n) complexity claim.
 * Run it and watch that totalSteps stays proportional to input size,
 * not to input size squared.
 */
public class ComplexityTracer {

    public static void tracedLongestConsecutive(int[] numbers) {
        Set<Integer> numberSet = new HashSet<>();
        for (int num : numbers) {
            numberSet.add(num);
        }

        int longestSequenceLength = 0;
        int outerLoopCount = 0; // how many times the for-loop body executes
        int innerWhileSteps = 0; // total steps across ALL while-loop runs

        for (int num : numberSet) {
            outerLoopCount++;

            if (numberSet.contains(num - 1)) {
                continue; // not a sequence start, skip
            }

            // Confirmed start: count forward
            int sequenceStart = num;
            int currentLength = 1;

            while (numberSet.contains(sequenceStart + currentLength)) {
                currentLength++;
                innerWhileSteps++; // track each forward step
            }

            longestSequenceLength = Math.max(longestSequenceLength, currentLength);
        }

        int uniqueCount = numberSet.size();
        System.out.println("  Unique numbers (n):       " + uniqueCount);
        System.out.println("  Outer loop iterations:    " + outerLoopCount);
        System.out.println("  Inner while total steps:  " + innerWhileSteps);
        System.out.println("  Combined total steps:     " + (outerLoopCount + innerWhileSteps));
        System.out.println("  Longest sequence:         " + longestSequenceLength);
        System.out.println("  Steps / n ratio:          "
            + String.format("%.2f", (double)(outerLoopCount + innerWhileSteps) / uniqueCount));
    }

    public static void main(String[] args) {
        System.out.println("--- Small input (n=8) ---");
        tracedLongestConsecutive(new int[]{1, 2, 3, 4, 10, 11, 50, 51});

        System.out.println("\n--- Medium input: one long chain (n=10) ---");
        tracedLongestConsecutive(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

        System.out.println("\n--- Worst-case-looking input: many chains (n=10) ---");
        tracedLongestConsecutive(new int[]{1, 3, 5, 7, 9, 11, 13, 15, 17, 19});
    }
}

Output

--- Small input (n=8) ---

Unique numbers (n): 8

Outer loop iterations: 8

Inner while total steps: 6

Combined total steps: 14

Longest sequence: 4

Steps / n ratio: 1.75

--- Medium input: one long chain (n=10) ---

Unique numbers (n): 10

Outer loop iterations: 10

Inner while total steps: 9

Combined total steps: 19

Longest sequence: 10

Steps / n ratio: 1.90

--- Worst-case-looking input: many chains (n=10) ---

Unique numbers (n): 10

Outer loop iterations: 10

Inner while total steps: 0

Combined total steps: 10

Longest sequence: 1

Steps / n ratio: 1.00

What the Ratio Tells You:

The Steps/n ratio is always between 1.0 and 2.0, regardless of input shape. One long chain gives ratio close to 2 (each element appears in both the outer loop and one inner step). All isolated numbers gives ratio exactly 1 (inner while never runs). Both are O(n) — the ratio never grows with n.

Production Insight

In production, the ratio stays ≤2 only if you iterate the set, not the array.

If you mistakenly iterate the array and the input has many duplicates, the outer loop runs for each copy, breaking the amortised bound.

Rule: always iterate the set — duplicates amplify work silently.

Key Takeaway

Amortised analysis proves total inner steps ≤ n.

The guard ensures each number is counted only once from its start.

\(2n\) operations is still O(n) — not O(n²).

When to Explain Amortized Analysis in an Interview

IfInterviewer asks about nested loop complexity

→

UseStart with the counter example: show that total inner steps ≤ n across all iterations.

IfInterviewer asks about worst-case input

→

UseExplain that one long chain gives 2n steps, many short chains give n steps — both O(n).

IfInterviewer compares to sorting approach

→

UsePoint out that O(n) is strictly better than O(n log n) for large n, and the hash set handles duplicates automatically.

Here's a scenario you'll actually encounter. Your app tracks which calendar days (as day-numbers since epoch) a user logged in. You want to find the user's longest unbroken login streak. The login days come from a database query — unsorted, possibly containing duplicates if the schema logs multiple events per day.

This is the Longest Consecutive Sequence problem in production clothing. The 'array of integers' is your list of day numbers. The 'consecutive sequence' is unbroken daily logins. The hash set approach handles duplicates (multiple logins on one day) without special casing, works in O(n) time even for users with years of history, and doesn't require you to sort a potentially large dataset.

The same pattern applies to: finding contiguous free blocks in a memory allocator, detecting unbroken sensor uptime windows in an IoT dashboard, finding runs of consecutive student attendance days, and identifying sequential order IDs to spot gaps in an audit trail.

Whenever your domain has 'find the longest run of something that can be modelled as consecutive integers', this algorithm is your friend.

LoginStreakAnalyzer.javaJAVA

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Real-world simulation: find a user's longest consecutive login streak.
 * Login days are represented as integers (days since epoch).
 * Data is unsorted and may contain duplicates (multiple logins in one day).
 */
public class LoginStreakAnalyzer {

    /**
     * Returns the length of the longest unbroken daily login streak.
     *
     * @param loginDays list of day-numbers when the user logged in (unsorted, may repeat)
     * @return number of consecutive days in the longest streak
     */
    public static int longestLoginStreak(List<Integer> loginDays) {
        if (loginDays == null || loginDays.isEmpty()) {
            return 0;
        }

        // Load into a set — duplicates (multiple logins per day) vanish automatically
        Set<Integer> uniqueLoginDays = new HashSet<>(loginDays);

        int longestStreak = 0;

        for (int day : uniqueLoginDays) {
            // Only start counting from the first day of a streak block.
            // If the previous day also has a login, this is mid-streak — skip.
            boolean isStreakStart = !uniqueLoginDays.contains(day - 1);

            if (isStreakStart) {
                int streakDay = day;
                int streakLength = 1;

                // Advance through consecutive login days
                while (uniqueLoginDays.contains(streakDay + 1)) {
                    streakDay++;
                    streakLength++;
                }

                longestStreak = Math.max(longestStreak, streakLength);

                System.out.println("  Streak found: days " + day
                    + " to " + streakDay
                    + " (" + streakLength + " days)");
            }
        }

        return longestStreak;
    }

    public static void main(String[] args) {
        // Simulated login days for a user over several weeks
        // Days 101-105: 5-day streak
        // Days 110-112: 3-day streak
        // Day 120: isolated login
        // Day 103 appears twice — user logged in twice that day
        List<Integer> userLoginHistory = List.of(
            101, 102, 103, 103, 104, 105,
            110, 111, 112,
            120
        );

        System.out.println("=== Login Streak Analysis ===");
        System.out.println("Raw login events: " + userLoginHistory.size());
        System.out.println("Streaks detected:");

        int best = longestLoginStreak(userLoginHistory);

        System.out.println("\nLongest login streak: " + best + " day(s)");
    }
}

Output

=== Login Streak Analysis ===

Raw login events: 10

Streaks detected:

Streak found: days 101 to 105 (5 days)

Streak found: days 110 to 112 (3 days)

Streak found: days 120 to 120 (1 days)

Longest login streak: 5 day(s)

Design Tip for Production Code:

In a real system you'd also want to return the start day of the longest streak, not just its length. Tweak the algorithm to track bestStreakStart alongside longestStreak — it's a one-line addition and immediately makes the result actionable in a UI (e.g., 'Your best streak ran from Jan 5 to Jan 9').

Production Insight

Memory footprint matters: for a user with 10 years of daily logins, that's ~3652 unique days — the hash set is trivial.

But if you use this for a system that processes millions of users concurrently, the O(n) memory per user adds up.

Rule: consider using a bitset if the range of values is known and bounded, to trade memory for speed.

Key Takeaway

This algorithm is ready for production login streaks.

It handles duplicates, unsorted input, and runs in O(n) time.

Add a start-day tracker to make the result user-facing.

Edge Cases, Variants, and Follow-Up Questions

The basic algorithm is elegant, but interviewers love to push on the edges. Let's cover the most common follow-ups.

Integer underflow at MIN_VALUE: num - 1 when num = Integer.MIN_VALUE wraps to Integer.MAX_VALUE. The guard will think MAX_VALUE exists and skip a legitimate start. Fix: cast to long before subtraction.

Returning the actual sequence: Track bestStart and bestLength. After the loop, reconstruct: IntStream.range(bestStart, bestStart + bestLength).toArray(). That's a common extension.

Distributed variant: What if the data is sharded across thousands of servers? You can't load everything into a single hash set. The pattern shifts to MapReduce: map each number to its bucket (num / segmentSize), find sequences per bucket, then merge across bucket boundaries. This appears in real-time streaming systems.

Memory-constrained environment: If you can't afford O(n) memory, you're back to sorting (O(1) extra space) or use a Bloom filter as a probabilistic membership test if exactness isn't required. That's a rare but advanced trade-off.

EdgeCaseDemonstration.javaJAVA

import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class EdgeCaseDemonstration {

    public static void main(String[] args) {
        // Underflow example
        int[] withMinValue = {Integer.MIN_VALUE, Integer.MIN_VALUE + 1};
        int result = longestConsecutiveFixed(withMinValue);
        System.out.println("With MIN_VALUE: " + result); // Expected 2
    }

    public static int longestConsecutiveFixed(int[] numbers) {
        if (numbers == null || numbers.length == 0) return 0;
        Set<Long> numberSet = new HashSet<>(); // Use Long to avoid overflow
        for (int num : numbers) {
            numberSet.add((long) num);
        }
        int longest = 0;
        for (long num : numberSet) {
            if (!numberSet.contains(num - 1)) {
                long current = num;
                int count = 1;
                while (numberSet.contains(current + 1)) {
                    current++;
                    count++;
                }
                longest = Math.max(longest, count);
            }
        }
        return longest;
    }
}

Output

With MIN_VALUE: 2

Watch Out for Integer Underflow

Java's int arithmetic wraps around on overflow. If the input contains Integer.MIN_VALUE, the expression num - 1 overflows to Integer.MAX_VALUE. Always cast to long when doing arithmetic on array values in this algorithm.

Production Insight

In a real system, login days are often stored as epoch seconds or millis — a 64-bit long removes the underflow concern.

But your data pipeline might pass 32-bit integer IDs. Always validate the range of your input domain.

Rule: if the data source can produce MIN_VALUE, use long in the set.

Key Takeaway

Integer.MIN_VALUE breaks the guard if you use int.

Cast to long to avoid overflow.

Returning the actual sequence is a one-line addition.

● Production incidentPOST-MORTEMseverity: high

The O(n²) That Almost Killed a Login Streak Feature

Symptom

API endpoint computing longest login streak returns correct results but takes over 40 seconds for a user with 100k login events.

Assumption

You assume the HashSet-based algorithm is O(n) by construction — the nested loop must be fine because it's just a while walking consecutive numbers.

Root cause

Without the guard if (numberSet.contains(num - 1)) continue;, the inner while loop runs for every number, not just sequence starts. For a sequence of length L, it's executed L times from each element, turning the algorithm into O(n²). Here, a single streak of 10,000 consecutive logins caused 10,000 * 10,000 / 2 ≈ 50 million inner steps.

Fix

Add the one-line guard before starting any while-loop. Also iterate over the set instead of the array to avoid revisiting duplicates.

Key lesson

Always validate O(n) claims with data from both worst-case (one long chain) and worst-case-looking (many short chains) inputs.
Amortised analysis isn't just theory — it's the difference between a 200ms response and a failed deployment.
When performance degrades unexpectedly in prod, suspect hidden quadratic behaviour from missing loop guards.

Production debug guideReal signals that your algorithm is broken or slow4 entries

Symptom · 01

Correct results but endpoint timeouts on large inputs

→

Fix

Insert a counter inside the while loop and log total steps. If steps grow with n², you're missing the sequence-start guard.

Symptom · 02

Duplicates cause inflated sequence length

→

Fix

Check if you iterate the original array or the set. Iterating the array causes duplicates to be re-processed as potential sequence starts. Switch to for (int num : numberSet).

Symptom · 03

Integer overflow when num is Integer.MIN_VALUE

→

Fix

Cast to long before subtraction: !numberSet.contains((long) num - 1). Java's int underflows MIN_VALUE - 1 to MAX_VALUE, breaking the guard.

Symptom · 04

NullPointerException on null input

→

Fix

Add a guard at function entry: if (numbers == null) return 0;

★ Quick Debug Cheat SheetFix the algorithm fast when it's returning wrong results or running too slowly.

Algorithm returns wrong length on duplicates−

Immediate action

Stop iterating the original array. Change outer loop to iterate `numberSet`.

Commands

Copy input into a HashSet and log its size: Set<Integer> set = new HashSet<>(Arrays.asList(input)); System.out.println(set.size());

Assert that set size matches unique count: assert set.size() == expectedUniqueCount;

Fix now

Replace for (int num : numbers) with for (int num : numberSet).

Response time grows quadratically with input size+

Algorithm fails when input contains Integer.MIN_VALUE+

Sort-Based vs HashSet Approach

Aspect	Sort-Based Approach O(n log n)	HashSet Approach O(n)
Time Complexity	O(n log n) — dominated by sort	O(n) — two linear passes total
Space Complexity	O(1) extra if in-place sort	O(n) for the hash set
Handles Duplicates	Manual skip logic needed	Set absorbs duplicates automatically
Preserves Input Order	No — array is sorted in-place	Yes — original array untouched
Handles Negatives	Yes, sorts correctly	Yes, hash set is key-agnostic
Code Complexity	Simple to write and read	Slightly more logic, but still concise
Best Use Case	When input is nearly sorted already	General case, large unsorted inputs
Interview Preference	Acceptable baseline answer	Expected optimal answer at FAANG level
Vulnerable to Underflow	No (uses comparison, not arithmetic)	Yes — must cast to long for MIN_VALUE

Key takeaways

The hash set's O(1) lookup is what makes O(n) possible

the algorithm is essentially trading O(n) space for the elimination of sorting.

The sequence-start guard (!numberSet.contains(num - 1)) is the entire reason the nested loop doesn't blow up to O(n²)

never implement this algorithm without it.

Iterating over the set (not the original array) in the outer loop silently eliminates duplicate processing

a small detail that matters for correctness on inputs with repeated values.

This pattern

load into a set, then query cheaply — generalises to dozens of problems: anagram detection, two-sum, first missing positive. Recognising it as a pattern is more valuable than memorising this one problem.

Always cast to long for arithmetic on array values to avoid integer overflow with MIN_VALUE.

Common mistakes to avoid

4 patterns

Missing the sequence-start guard

Symptom

The algorithm returns correct results but runs in O(n²) time on inputs with long consecutive runs. In production with large datasets (e.g., 1M numbers forming one streak of 500k), response times explode.

Fix

Add if (numberSet.contains(num - 1)) continue; before the inner while loop. This single line keeps the algorithm linear.

Iterating the original array instead of the set in the outer loop

Symptom

Duplicates cause the outer loop to revisit sequence starts multiple times, potentially counting the same sequence twice and inflating the answer. For input [1,1,2,2,3] you might get length 3 (correct) but processing is slower and output is correct only by chance.

Fix

Replace for (int num : numbers) with for (int num : numberSet). Iterating the set guarantees each unique value is processed exactly once.

Forgetting null or empty input handling

Symptom

NullPointerException or ArrayIndexOutOfBoundsException on edge-case inputs, costing you the question in an interview even if the main logic is perfect.

Fix

Add a null-and-length guard at the top: if (numbers == null || numbers.length == 0) return 0;.

Not accounting for integer overflow with MIN_VALUE

Symptom

When the input contains Integer.MIN_VALUE, the guard !numberSet.contains(num - 1) incorrectly checks for Integer.MAX_VALUE (because of wraparound), potentially skipping a legitimate sequence start. The result is a missed streak.

Fix

Cast all numbers to long before insertion and in all contains() calls. Or use a Set<Long>.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

Can you walk me through why your solution is O(n) even though there's a ...

Q02SENIOR

What changes if the input can contain negative numbers or Integer.MIN_VA...

Q03SENIOR

How would you modify this to return the actual sequence, not just its le...

Q04SENIOR

What if the input is too large to fit in memory? How would you find the ...

Q01 of 04SENIOR

Can you walk me through why your solution is O(n) even though there's a while loop nested inside a for loop?

ANSWER

Yes. The key is amortised analysis. The while loop only runs when we're at a confirmed sequence start — a number whose predecessor does not exist in the set. Each number that gets visited by the while loop (as we walk forward) is then skipped as a start candidate in the outer loop because its predecessor now exists. So every unique number is visited at most twice: once when it's checked as a potential start, and once when it's stepped over in a forward walk. That gives a maximum of 2n total operations, which is O(n).

FAQ · 4 QUESTIONS

Frequently Asked Questions

What is the time complexity of the longest consecutive sequence using a hash set?

Why does the longest consecutive sequence problem use a HashSet and not a HashMap?

Does the algorithm work correctly if the input array has duplicate numbers?

How do I handle the case where the input contains Integer.MIN_VALUE?

🔥

That's Hashing. Mark it forged?

5 min read · try the examples if you haven't

Longest Consecutive Sequence — O(n²) Bug in Login Streak

Why Sorting Is the Wrong First Instinct

The Core Insight — Only Count From Sequence Starts

Proving O(n) — Walking Through the Work Count

Real-World Application — Detecting Login Streak Gaps in a User System

Edge Cases, Variants, and Follow-Up Questions

The O(n²) That Almost Killed a Login Streak Feature

Key takeaways

Common mistakes to avoid

Missing the sequence-start guard

Iterating the original array instead of the set in the outer loop

Forgetting null or empty input handling

Not accounting for integer overflow with MIN_VALUE

Interview Questions on This Topic

Frequently Asked Questions

That's Hashing. Mark it forged?