medium Longest Consecutive Sequence

Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive sequence of numbers in it. A consecutive sequence means the numbers in the sequence are contiguous without any gaps. For instance, 1, 2, 3, 4 is a consecutive sequence, but 1, 3, 4, 5 is not.

Examples

- Input: [10, 11, 14, 12, 13]
- Output: 5
- Justification: The entire array forms a consecutive sequence from 10 to 14.
- Input: [3, 6, 4, 100, 101, 102]
- Output: 3
- Justification: There are two consecutive sequences, [3, 4] and [100,101,102]. The latter has a maximum length of 3.
- Input: [4, 3, 6, 2, 5, 8, 4, 7, 0, 1]
- Output: 9
- Justification: The longest consecutive sequences here are [0, 1, 2,, 3, 4, 5, 6, 7, 8].
- Input: [7, 8, 10, 11, 15]
- Output: 2
- Justification: The longest consecutive sequences here are [7,8] and [10,11], both of length 2.

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Longest Consecutive Sequence medium

Why this concept exists (judgment layer)

Longest run of values x,x+1,… in an unsorted array in O(n). HashSet membership turns "is x+1 present?" into O(1); only start streaks when x-1 absent — total extensions O(n).

Worked example with complexity derivation

[100,4,200,1,3,2]: set; starts 100,200,1 (not 4,3,2).
From 1: 2,3,4 → len 4; 100→1; 200→1 → answer 4.
Sort approach O(n log n) also works but violates O(n) follow-up.
Naive from every num scan up without start-filter → O(n²).

Pattern + when-NOT / named alternative

PATTERN: SET + ONLY-START-WHEN-PRED-MISSING (amortized O(n) chain walks). WHEN NOT: O(n log n) OK → sort + linear scan runs. Not union-find unless teaching DSU. Not sliding window (not subarray contiguous indices).

Edge case / failure mode

Edges: empty → 0; single; all dups; negatives; already consecutive; gaps. Duplicates must not extend length (set collapses).

Hostile-panel drills (defend the decision)

Q1. Why only start at num-1 missing?
Model answer: Each streak counted once from its minimum; interior points would re-walk same chain.

Q2. Prove O(n) time.
Model answer: Each num enters set once; while extends only from starts; each value visited ≤1 in while across algorithm → O(n) contains checks.

Q3. Index-contiguous vs value-consecutive?
Model answer: This is value space consecutive; subarray problems need window/Kadane family.

✅ Solution Longest Consecutive Sequence

Problem Statement

Examples

- Input: [10, 11, 14, 12, 13]
- Output: 5
- Justification: The entire array forms a consecutive sequence from 10 to 14.
- Input: [3, 6, 4, 100, 101, 102]
- Output: 3
- Justification: There are two consecutive sequences, [3, 4] and [100,101,102]. The latter has a maximum length of 3.
- Input: [4, 3, 6, 2, 5, 8, 4, 7, 0, 1]
- Output: 9
- Justification: The longest consecutive sequences here are [0, 1, 2,, 3, 4, 5, 6, 7, 8].
- Input: [7, 8, 10, 11, 15]
- Output: 2
- Justification: The longest consecutive sequences here are [7,8] and [10,11], both of length 2.

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Solution

To solve this problem, the key observation is that if n is part of a consecutive sequence, then n+1 and n-1 must also be in that sequence.

HashSet: Begin by inserting all elements of the array into a HashSet. The reason for using a HashSet is to ensure O(1) time complexity during look-up operations.
Initial Scan: Iterate through each element of the array. For every number, check if it's the starting point of a possible sequence. This can be determined by checking if n-1 exists in the HashSet. If not, then it means n is the start of a sequence.
Building Sequences: For each starting number identified in step 2, keep checking if n+1, n+2... exist in the HashSet. For each present number, increase the length of the sequence and move to the next number.
Result: Store the length of each sequence found in step 3. The answer will be the longest of all sequences identified.

Algorithm Walkthrough

Given the input: [3, 6, 4, 100, 101, 102]

Initialize an empty HashSet and populate it with all numbers from the input.
Start with the first number, 3. Since 2 (which is 3-1) is not in the HashSet, we recognize 3 as the starting of a sequence.
- Check for 4. It's there. Move to 5. It's not there. So, the sequence is [3,4] with a length of 2.
Next, take 6. 5 is not there, so 6 might be the start of a new sequence. However, 7 isn't in the HashSet. So, the sequence is just [6].
For 100, 99 isn't there, so 100 is a starting point.
- Check for 101. It's there. Check for 102. It's there. Check for 103. It's not there. The sequence is [100,101,102] with a length of 3.
The algorithm returns 3, which is the length of the longest sequence.

Code

java

import java.util.HashSet;

public class Solution {

  public int longestConsecutive(int[] nums) {
    // Using a HashSet to store numbers for constant time lookup
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
      set.add(num);
    }

    int longestSequence = 0;
    for (int num : set) {
      // Checking if current number is the start of a sequence
      if (!set.contains(num - 1)) {
        int currentNum = num;
        int currentStreak = 1;

        // Extend the streak for as long as possible
        while (set.contains(currentNum + 1)) {
          currentNum += 1;
          currentStreak += 1;
        }

        // Keep track of the longest streak
        longestSequence = Math.max(longestSequence, currentStreak);
      }
    }

    return longestSequence;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.longestConsecutive(new int[] { 10, 11, 14, 12, 13 })
    ); // 5
    System.out.println(
      sol.longestConsecutive(new int[] { 3, 6, 4, 100, 101, 102 })
    ); // 3
    System.out.println(sol.longestConsecutive(new int[] { 7, 8, 10, 11, 15 })); // 2
  }
}

Complexity Analysis

Time Complexity: O(n). Although it seems that the while loop runs for each number, it only runs for the numbers that are the starting points of sequences. So, in total, each number is processed only once.
Space Complexity: O(n). The space used by our set.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Longest Consecutive Sequence

Why this concept exists (judgment layer)

Solution implements HashSet + start filter correctly. Elevation hardens complexity proof and edges (empty, dups, negatives) interviewers always ask.

Worked example with complexity derivation

[3,6,4,100,101,102] (page):
starts 3→[3,4] len2; 6→1; 100→[100,101,102] len3 → 3.
Iterate set not array to skip dup work.
Time O(n): build set O(n); each element O(1) start test; while visits each element at most once as currentNum → O(n) total.
Space O(n) set.

Pattern + when-NOT / named alternative

PATTERN: HashSet longest consecutive values. WHEN NOT: need actual subsequence indices → different problem. Memory tight O(1) extra → sort in place O(n log n) if allowed mutate.

Edge case / failure mode

Hand-run [] → 0; [1,2,0,1] → set{0,1,2} length 3; negatives [-2,-1,1] → 2. Failure: while from every num without !contains(num-1) → O(n²).

Hostile-panel drills (defend the decision)

Q1. Show O(n) accounting.
Model answer: Sum of while iterations ≤ n because each value is currentNum at most once.

Q2. Why HashSet not TreeSet?
Model answer: TreeSet gives O(log n) contains → O(n log n); need average O(1).

Q3. Duplicates in input?
Model answer: Set size < n; length counts distinct values only — correct for consecutive values.

🧩 Pattern · Hashing

Recognize it: Membership / frequency / “have I seen this?” in O(1) → a hash map or set.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Longest Consecutive Sequence? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Longest Consecutive Sequence** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Longest Consecutive Sequence** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Longest Consecutive Sequence**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Longest Consecutive Sequence**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Group Anagrams Problem 4 Longest Substring Withou →