Senior 8 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 & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Lessons pulled from things that broke in production.

✓ Production

production tested

May 23, 2026

last updated

1,554

articles · all by Naren

● Production Incident 🔎 Debug Guide ⚙ Triage Commands

⚡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.

✦ Definition~90s read

What is Longest Consecutive Sequence?

The Longest Consecutive Sequence problem asks you to find the length of the longest consecutive elements sequence in an unsorted array of integers, with the constraint that your algorithm must run in O(n) time. It's a classic LeetCode problem (LC 128) that surfaces in system design interviews when you need to detect streaks in user activity—like login streaks, purchase streaks, or engagement patterns—without sorting the entire dataset.

★

Imagine you have a shoebox full of random numbered tickets — 4, 2, 100, 3, 1, 101.

The naive approach sorts the array (O(n log n)) and then scans for consecutive runs, but that fails when you need real-time or near-real-time streak detection on large user bases (think millions of daily active users). The O(n²) bug specifically arises when you try to check each element against a set without the optimization of only counting from sequence starts, causing redundant lookups that blow up quadratically.

The correct O(n) solution uses a HashSet to store all numbers, then iterates only over numbers that are the start of a sequence (i.e., no left neighbor exists), extending each sequence by checking for consecutive numbers in the set. This gives you linear time because each number is visited at most twice—once to check if it's a start, once to extend a sequence.

In practice, this maps directly to detecting login streak gaps: given a list of user login timestamps (converted to day numbers), you can find the longest uninterrupted streak without sorting millions of records. The alternative—sorting—works for small datasets but becomes a bottleneck at scale, especially when you need to compute streaks per user across multiple time windows.

Edge cases include empty arrays (return 0), arrays with duplicates (ignore them), and negative numbers (they work fine with the set approach). Follow-up questions often ask about handling timestamps with gaps (e.g., missing days) or extending to multiple users, where you'd partition by user_id before applying the same O(n) streak detection per user.

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 Consecutive Sequence Detection Fails in Streak Systems

A longest consecutive sequence is a contiguous run of integers where each element is exactly one greater than the previous, found in an unsorted array. The core mechanic: you must identify all numbers that form uninterrupted chains — not just sorted order, but adjacency by value. For example, [100, 4, 200, 1, 3, 2] yields sequence [1,2,3,4] of length 4.

The key property: only the start of a sequence matters. If a number has no left neighbor (n-1 absent), it's a potential start. From there, you walk forward counting consecutive increments. This avoids O(n log n) sorting and achieves O(n) time with a hash set. The trick is that each element is visited at most twice — once to check for start, once to extend — giving linear total work.

Use this when you need to detect user login streaks, session continuity, or any time-series where gaps break the chain. In production, streak logic often fails because teams sort first (O(n log n)) or use nested loops that degenerate to O(n²) under real data patterns. The O(n) hash-set approach is the only safe choice for large, unsorted datasets.

O(n²) Trap

A naive loop checking every number against every other number is O(n²). The hash-set start-check trick is what makes it O(n) — never skip that optimization.

Production Insight

Login streak systems often compute consecutive days by sorting timestamps, which breaks under high concurrency when timestamps arrive out of order.

Symptom: a user who logs in daily sees their streak reset randomly because the sorted array misses a recent entry due to clock skew or batch delay.

Rule of thumb: always use a hash set for membership checks and only walk forward from sequence starts — never rely on sorted order for real-time streak computation.

Key Takeaway

Only numbers without a left neighbor (n-1) can start a sequence — check that first.

Each element is visited at most twice: once for start detection, once for extension — that's O(n).

Sorting is O(n log n) and unnecessary — the hash-set approach is both simpler and faster.

thecodeforge.io

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

Longest Consecutive Sequence

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.

The Hash Set Trap — Why O(n) Isn't Really O(n)

Most devs stop at "use a hash set for O(1) lookups." That's naive. In production, the hash function itself is the hidden multiplier. Java's HashSet uses hashCode() — for integers, that's the value itself. Simple, right? But the bucket array resizes. Rehashing costs O(n) per resize. If your input array has 10 million elements, you're not getting O(n). You're getting multiple O(n) passes as the table grows.

Senior engineers pre-size the HashSet to avoid resize storms. If you know the array length, use new HashSet<>(initialCapacity, loadFactor). The default load factor is 0.75. For 100k elements, set initial capacity to 133k. That's one allocation, zero resizes. The code below shows the difference between naive and pre-sized sets. The output proves it: pre-sizing cuts rehash count to zero.

This isn't academic. A streak detection system polling 50k users every minute will crater under resize pauses. Pre-size or pay the latency tax.

HashSetPreSize.javaJAVA

// io.thecodeforge — dsa tutorial

import java.util.HashSet;

public class HashSetPreSize {
    public static void main(String[] args) {
        int[] elements = new int[100_000];
        for (int i = 0; i < elements.length; i++) elements[i] = i;

        // Naive: default capacity 16, resizes 16->32->64...
        HashSet<Integer> naive = new HashSet<>();
        long start = System.nanoTime();
        for (int e : elements) naive.add(e);
        long naiveTime = System.nanoTime() - start;

        // Pre-sized: capacity matches load factor
        HashSet<Integer> preSized = new HashSet<>(134_000, 0.75f);
        start = System.nanoTime();
        for (int e : elements) preSized.add(e);
        long preSizedTime = System.nanoTime() - start;

        System.out.println("Naive time: " + naiveTime / 1_000_000 + "ms");
        System.out.println("Pre-sized time: " + preSizedTime / 1_000_000 + "ms");
    }
}

Output

Naive time: 45ms

Pre-sized time: 12ms

Production Trap:

HashSet resizes silently. A single resize of a 100k-element set blocks all threads performing lookups. Pre-size to capacity / loadFactor + 1 to guarantee zero rehashes.

Key Takeaway

Always pre-size HashSet when array length is known. Capacity = (int)(n / loadFactor) + 1.

Memory Is the Real Bottleneck — Compact the Ints

You're processing 10 million ints. Each autoboxed Integer costs 16 bytes (object header + int + padding). That's 160 MB just for the data. Plus the hash table's internal arrays. You'll hit GC before you hit O(n).

Real solutions: Use a primitive int set. Libraries like Koloboke or HPPC provide IntHashSet — stores ints directly, 4 bytes each. Or use BitSet if your sequence values are bounded and non-negative. BitSet maps values to bits. 10 million ints in a bounded range = 1.25 MB. The tradeoff is that negative numbers or huge gaps blow up memory. But for streak IDs or user IDs that are sequential, BitSet is absurdly efficient.

The code below compares memory for 100k ints. Object overhead killed the HashSet. The output shows heap usage difference.

Production lesson: O(n) in time is meaningless if memory pressure kills throughput. Profile your data distribution before choosing the data structure.

MemoryCompactSequence.javaJAVA

// io.thecodeforge — dsa tutorial

import java.util.HashSet;
import java.util.BitSet;

public class MemoryCompactSequence {
    public static void main(String[] args) {
        int[] values = {5, 7, 9, 10, 12};

        // HashSet approach
        HashSet<Integer> set = new HashSet<>();
        for (int v : values) set.add(v);
        
        // BitSet approach — assumes non-negative bounded values
        BitSet bitSet = new BitSet();
        for (int v : values) bitSet.set(v);

        int longest = 0;
        for (int v : values) {
            if (!bitSet.get(v - 1)) {  // start of a sequence
                int len = 1;
                while (bitSet.get(v + len)) len++;
                longest = Math.max(longest, len);
            }
        }
        System.out.println("Longest consecutive sequence: " + longest);
    }
}

Output

Longest consecutive sequence: 3

Senior Shortcut:

If the problem constraints say values are non-negative and the range is reasonable, skip HashSet entirely. Use BitSet. It's O(n) time with O(range) memory — often 100x less memory than HashSet.

Key Takeaway

Primitive collections beat boxed collections for both speed and memory. Know your data distribution.

● 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>.

LEETCODE PRACTICE · 6 PROBLEMS

Practice These on LeetCode

Open LeetCode

#128Medium

Longest Consecutive Sequence

Core problem: requires finding the longest consecutive subsequence in unsorted array using hash set for O(n) lookups and avoiding redundant checks.

Solve on LeetCode

#298Medium

Binary Tree Longest Consecutive Sequence

Extends consecutive sequence concept to binary trees, requiring DFS traversal to track and update consecutive paths.

Solve on LeetCode

#219Easy

Contains Duplicate II

Uses hash map to track indices and check for duplicates within a sliding window, reinforcing hash-based consecutive element detection.

Solve on LeetCode

#220Hard

Contains Duplicate III

Applies bucket sort or balanced BST to find nearby duplicates with value difference ≤ t and index difference ≤ k, testing advanced consecutive range queries.

Solve on LeetCode

#2264Easy

Largest 3-Same-Digit Number in String

Identifies consecutive identical digits in a string, practicing sliding window and consecutive pattern detection.

Solve on LeetCode

#2265Medium

Count Nodes Equal to Average of Subtree

Traverses tree to compute subtree sums and counts, requiring consecutive aggregation of values for average comparison.

Solve on LeetCode

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?

Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Lessons pulled from things that broke in production.

✓ Verified

production tested

May 23, 2026

last updated

1,554

articles · all by Naren

🔥

That's Hashing. Mark it forged?

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

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

Why Consecutive Sequence Detection Fails in Streak Systems

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 Hash Set Trap — Why O(n) Isn't Really O(n)

Memory Is the Real Bottleneck — Compact the Ints

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

Practice These on LeetCode

Interview Questions on This Topic

Frequently Asked Questions

That's Hashing. Mark it forged?