Longest Consecutive Sequence

🎯

Longest Consecutive Sequence

mediumHASH_MAPAmazonFacebookGoogle

Imagine you have a messy list of dates when a user logged into a system, and you want to find the longest streak of consecutive login days to reward loyalty.

💡 This problem tests your ability to efficiently find sequences in an unsorted array. Beginners often struggle because the naive approach is slow and they don't immediately see how to use a hash set to speed up membership checks.

📋

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Your algorithm must run in O(n) time.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

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

Output4

The longest consecutive sequence is [1, 2, 3, 4].

• All elements are the same → output is 1
• Array with one element → output is 1
• Array with no consecutive numbers → output is 1
• Array with negative and positive numbers → correctly find longest sequence

⚠️

Common Mistakes

Checking consecutive numbers by scanning array instead of using a hash set

Leads to O(n^2) time and TLE on large inputs

✅ Use a hash set for O(1) membership checks

Not skipping duplicates after sorting

Incorrectly counts duplicates as consecutive, inflating sequence length

✅ Add a condition to skip duplicates during linear scan

Starting to count sequences from every number instead of only sequence starts

Redundant counting causes inefficiency and possible TLE

✅ Only start counting if number-1 is not in the set

Not handling empty input array

Code may crash or return wrong result

✅ Add explicit check for empty input and return 0

Using sorting without considering negative numbers or large ranges

May cause incorrect results or inefficiency

✅ Sorting works regardless of sign; just ensure stable numeric sort

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by trying all possibilities, even though it's inefficient.

Intuition

Check for every number how long the consecutive sequence starting from it is by incrementing and searching for next numbers.

Algorithm

1. For each number in the array, start counting consecutive numbers incrementally.
2. Check if the next consecutive number exists in the array by scanning it.
3. Keep track of the longest consecutive count found so far.
4. Return the maximum count after checking all numbers.

💡 This approach is straightforward but inefficient because it repeatedly scans the array for each number, leading to many redundant checks.

</>

Code

def longestConsecutive(nums):
    max_len = 0
    for num in nums:
        length = 1
        current = num + 1
        while current in nums:
            length += 1
            current += 1
        max_len = max(max_len, length)
    return max_len

# Driver code
if __name__ == '__main__':
    print(longestConsecutive([100, 4, 200, 1, 3, 2]))  # Output: 4

Line Notes

for num in nums:Iterate over each number to consider it as a potential sequence start

while current in nums:Check if the next consecutive number exists by scanning the list (slow)

length += 1Increment length for each consecutive number found

max_len = max(max_len, length)Update the maximum length found so far

import java.util.*;
public class Solution {
    public static int longestConsecutive(int[] nums) {
        int maxLen = 0;
        for (int num : nums) {
            int length = 1;
            int current = num + 1;
            while (contains(nums, current)) {
                length++;
                current++;
            }
            maxLen = Math.max(maxLen, length);
        }
        return maxLen;
    }
    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};
        System.out.println(longestConsecutive(nums)); // Output: 4
    }
}

Line Notes

for (int num : nums)Loop over each number to try as sequence start

while (contains(nums, current))Check existence of next consecutive number by scanning array

length++Increment length for each consecutive number found

maxLen = Math.max(maxLen, length)Keep track of the longest sequence length

#include <iostream>
#include <vector>
using namespace std;

bool contains(const vector<int>& nums, int target) {
    for (int n : nums) {
        if (n == target) return true;
    }
    return false;
}

int longestConsecutive(vector<int>& nums) {
    int maxLen = 0;
    for (int num : nums) {
        int length = 1;
        int current = num + 1;
        while (contains(nums, current)) {
            length++;
            current++;
        }
        maxLen = max(maxLen, length);
    }
    return maxLen;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << longestConsecutive(nums) << endl; // Output: 4
    return 0;
}

Line Notes

for (int num : nums)Try each number as a potential sequence start

while (contains(nums, current))Check if next consecutive number exists by scanning vector

length++Increase length for each found consecutive number

maxLen = max(maxLen, length)Update maximum sequence length found

function longestConsecutive(nums) {
    let maxLen = 0;
    for (let num of nums) {
        let length = 1;
        let current = num + 1;
        while (nums.includes(current)) {
            length++;
            current++;
        }
        maxLen = Math.max(maxLen, length);
    }
    return maxLen;
}

// Test
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // Output: 4

Line Notes

for (let num of nums)Iterate over each number to check sequences

while (nums.includes(current))Check if next consecutive number exists by scanning array

length++Increment length for each consecutive number found

maxLen = Math.max(maxLen, length)Track the longest sequence length

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each number, we scan the entire array to check for consecutive numbers, leading to quadratic time.

💡 For n=20, this means up to 400 checks, which grows quickly and becomes impractical for large n.

Interview Verdict: TLE

This approach is too slow for large inputs and will time out in interviews, but it helps understand the problem.

🧠

Sorting + Linear Scan

💡 Sorting the array first helps by putting numbers in order, so consecutive sequences become adjacent, making it easier to count.

Intuition

Sort the array, then scan once to count lengths of consecutive runs by comparing adjacent elements.

Algorithm

1. Sort the array.
2. Initialize max length and current length counters.
3. Iterate through the sorted array, increment current length if consecutive, else reset.
4. Return the maximum length found.

💡 Sorting simplifies the problem but costs O(n log n) time; the linear scan then efficiently finds sequences.

</>

Code

def longestConsecutive(nums):
    if not nums:
        return 0
    nums.sort()
    max_len = 1
    current_len = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            continue  # skip duplicates
        elif nums[i] == nums[i-1] + 1:
            current_len += 1
        else:
            max_len = max(max_len, current_len)
            current_len = 1
    max_len = max(max_len, current_len)
    return max_len

# Driver code
if __name__ == '__main__':
    print(longestConsecutive([100, 4, 200, 1, 3, 2]))  # Output: 4

Line Notes

if not nums:Handle empty input edge case

nums.sort()Sort the array to bring consecutive numbers together

if nums[i] == nums[i-1]:Skip duplicates to avoid counting them multiple times

elif nums[i] == nums[i-1] + 1:Check if current number continues the consecutive sequence

import java.util.*;
public class Solution {
    public static int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int maxLen = 1, currentLen = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) continue;
            else if (nums[i] == nums[i-1] + 1) currentLen++;
            else {
                maxLen = Math.max(maxLen, currentLen);
                currentLen = 1;
            }
        }
        maxLen = Math.max(maxLen, currentLen);
        return maxLen;
    }
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums)); // Output: 4
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty input

Arrays.sort(nums);Sort array to group consecutive numbers

if (nums[i] == nums[i-1]) continue;Skip duplicates to avoid false increments

else if (nums[i] == nums[i-1] + 1)Detect consecutive numbers to increment current length

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    sort(nums.begin(), nums.end());
    int maxLen = 1, currentLen = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == nums[i-1]) continue;
        else if (nums[i] == nums[i-1] + 1) currentLen++;
        else {
            maxLen = max(maxLen, currentLen);
            currentLen = 1;
        }
    }
    maxLen = max(maxLen, currentLen);
    return maxLen;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << longestConsecutive(nums) << endl; // Output: 4
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input case

sort(nums.begin(), nums.end());Sort to bring consecutive numbers together

if (nums[i] == nums[i-1]) continue;Skip duplicates to avoid counting them multiple times

else if (nums[i] == nums[i-1] + 1)Check if current number continues the consecutive sequence

function longestConsecutive(nums) {
    if (nums.length === 0) return 0;
    nums.sort((a, b) => a - b);
    let maxLen = 1, currentLen = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i-1]) continue;
        else if (nums[i] === nums[i-1] + 1) currentLen++;
        else {
            maxLen = Math.max(maxLen, currentLen);
            currentLen = 1;
        }
    }
    return Math.max(maxLen, currentLen);
}

// Test
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // Output: 4

Line Notes

if (nums.length === 0) return 0;Handle empty input edge case

nums.sort((a, b) => a - b);Sort array numerically to group consecutive numbers

if (nums[i] === nums[i-1]) continue;Skip duplicates to avoid false increments

else if (nums[i] === nums[i-1] + 1)Detect consecutive numbers to increment current length

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n), then a single pass O(n) to find longest consecutive sequence.

💡 For n=100000, sorting is feasible but slower than linear solutions; still acceptable in many interviews.

Interview Verdict: Accepted

This approach passes but is not optimal; it is a good intermediate step to show improvement over brute force.

🧠

Optimal Hash Set with Sequence Start Detection

💡 Using a hash set allows O(1) membership checks, enabling a linear time solution by only starting sequences at their minimal element.

Intuition

Put all numbers in a set. For each number, only start counting if it is the start of a sequence (no smaller consecutive number exists). Then count forward until the sequence ends.

Algorithm

1. Insert all numbers into a hash set for O(1) lookups.
2. Iterate over each number; if number-1 is not in the set, this number is a sequence start.
3. From each start, count consecutive numbers by checking number+1, number+2, etc. in the set.
4. Track and update the maximum sequence length found.
5. Return the maximum length after processing all numbers.

💡 This approach avoids redundant work by only counting sequences from their smallest element, ensuring linear time complexity.

</>

Code

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        if num - 1 not in num_set:
            current_num = num
            length = 1
            while current_num + 1 in num_set:
                current_num += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

# Driver code
if __name__ == '__main__':
    print(longestConsecutive([100, 4, 200, 1, 3, 2]))  # Output: 4

Line Notes

num_set = set(nums)Create a hash set for O(1) membership checks

for num in num_set:Iterate over unique numbers only

if num - 1 not in num_set:Check if current number is start of a sequence

while current_num + 1 in num_set:Count consecutive numbers forward efficiently

import java.util.*;
public class Solution {
    public static int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) numSet.add(num);
        int maxLen = 0;
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int length = 1;
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    length++;
                }
                maxLen = Math.max(maxLen, length);
            }
        }
        return maxLen;
    }
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums)); // Output: 4
    }
}

Line Notes

Set<Integer> numSet = new HashSet<>();Use hash set for O(1) lookups

for (int num : numSet)Iterate over unique numbers only

if (!numSet.contains(num - 1))Identify sequence starts by absence of predecessor

while (numSet.contains(currentNum + 1))Count consecutive numbers efficiently

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int maxLen = 0;
    for (int num : numSet) {
        if (numSet.find(num - 1) == numSet.end()) {
            int currentNum = num;
            int length = 1;
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum++;
                length++;
            }
            maxLen = max(maxLen, length);
        }
    }
    return maxLen;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << longestConsecutive(nums) << endl; // Output: 4
    return 0;
}

Line Notes

unordered_set<int> numSet(nums.begin(), nums.end());Initialize hash set for O(1) membership

for (int num : numSet)Iterate over unique elements only

if (numSet.find(num - 1) == numSet.end())Check if current number is sequence start

while (numSet.find(currentNum + 1) != numSet.end())Count consecutive numbers forward efficiently

function longestConsecutive(nums) {
    const numSet = new Set(nums);
    let maxLen = 0;
    for (const num of numSet) {
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let length = 1;
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                length++;
            }
            maxLen = Math.max(maxLen, length);
        }
    }
    return maxLen;
}

// Test
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // Output: 4

Line Notes

const numSet = new Set(nums);Create a set for O(1) membership checks

for (const num of numSet)Iterate over unique numbers only

if (!numSet.has(num - 1))Detect sequence starts by checking absence of predecessor

while (numSet.has(currentNum + 1))Count consecutive numbers efficiently

⏱

Complexity

TimeO(n)

SpaceO(n)

Each number is processed at most twice: once when checking if it's a sequence start, and once when counting forward.

💡 For n=100000, this means roughly 200000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the optimal and recommended approach for interviews, demonstrating mastery of hash sets and sequence detection.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal hash set approach; mention brute force and sorting to show progression.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	No	Mention only - never code
2. Sorting + Linear Scan	O(n log n)	O(1) or O(n)	No	Yes	Good intermediate step if stuck
3. Optimal Hash Set	O(n)	O(n)	No	Yes	Code this in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to show understanding.Improve to sorting-based approach to optimize time.Present the optimal hash set approach as the final solution.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem-solving progression, ability to optimize, and knowledge of hash sets and sequence detection.

Common Follow-ups

• What if duplicates are present? → Skip duplicates in sorting or use set.
• Can you reconstruct the actual longest sequence? → Store sequence starts and build sequence.
• What if input is a stream? → Use dynamic data structures or sliding window.
• How to handle very large ranges? → Use hash sets, avoid sorting.

💡 These follow-ups test your ability to handle variations and extensions of the problem, common in interviews.

🔍

Pattern Recognition

When to Use

1) Need to find consecutive sequences in unsorted data; 2) O(n) time required; 3) Hash set membership checks possible; 4) Sequence start detection is feasible.

Signature Phrases

'longest consecutive elements sequence''unsorted array''must run in O(n) time'

NOT This Pattern When

Sorting-based problems without membership checks or problems requiring subsequence (not necessarily consecutive) detection

Similar Problems

Longest Increasing Subsequence - similar but order matters and not necessarily consecutiveMaximum Consecutive Ones - simpler consecutive counting in binary arraysLongest Consecutive Path in a Matrix - similar concept extended to 2D

Practice

1. You are given a positive integer and need to determine if repeatedly replacing the number by the sum of the squares of its digits eventually leads to 1 or falls into a repeating cycle. Which approach guarantees an optimal solution with constant space and known cycle detection?

easy

A. Use a mathematical insight with a known set of cycle numbers to detect unhappy cycles

B. Use a greedy approach that picks the largest digit's square sum at each step

C. Use dynamic programming to store intermediate sums and avoid recomputation

D. Use brute force with a hash set to detect cycles by storing all seen numbers

Solution

1. Step 1: Understand the problem pattern

   The problem requires detecting if a number eventually reaches 1 or cycles indefinitely by repeatedly summing squares of digits.

2. Step 2: Identify the optimal approach

   Using a known set of unhappy cycle numbers allows constant space cycle detection, avoiding overhead of storing all seen numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known cycle detection uses constant space and is optimal [OK]

Hint: Known unhappy cycles enable constant space detection [OK]

Common Mistakes:

• Assuming greedy or DP approaches solve cycle detection optimally

2. Consider the following Python function to check if two strings are isomorphic:

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    t_to_s = {}
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
        if c2 in t_to_s:
            if t_to_s[c2] != c1:
                return False
        else:
            t_to_s[c2] = c1
    return True

print(isIsomorphic("egg", "add"))

What is the output of this code?

easy

A. True

B. None

C. Raises an exception

D. False

Solution

1. Step 1: Trace first iteration with c1='e', c2='a'

   Both maps are empty, so s_to_t['e'] = 'a' and t_to_s['a'] = 'e'.

2. Step 2: Trace second and third iterations

   Second iteration: c1='g', c2='d', maps updated similarly. Third iteration: c1='g' already maps to 'd', and c2='d' maps back to 'g', so no conflict.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mapping is consistent for all characters, so returns True [OK]

Hint: Check mapping consistency at each iteration [OK]

Common Mistakes:

• Confusing output with 'foo' and 'bar'
• Assuming length mismatch causes exception

3. Identify the bug in the following code snippet for grouping anagrams:

medium

A. Line 4: defaultdict initialization

B. Line 7: Incrementing count array

C. Line 10: Appending string to map

D. Line 9: Using ''.join(count) to create key

Solution

1. Step 1: Understand key creation

   Count is a list of integers; ''.join(count) tries to join integers as strings, causing TypeError or incorrect keys.

2. Step 2: Correct key creation

   Key should be a tuple of counts to be hashable and unique, e.g., key = tuple(count).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using ''.join on int list causes errors or wrong grouping [OK]

Hint: Keys must be hashable types like tuples, not joined strings of ints [OK]

Common Mistakes:

• Joining int list without conversion
• Using list as dict key
• Forgetting to convert count to tuple

4. What is the time complexity of the optimal bidirectional hash map approach to check if two strings of length n are isomorphic?

medium

A. O(n) because each character is processed once with constant-time hash map operations

B. O(n²) due to nested loops checking all character pairs

C. O(n log n) due to sorting characters before mapping

D. O(1) since hash maps provide constant-time lookups

Solution

1. Step 1: Identify the main loop over string length

   The algorithm iterates once over the strings of length n, processing each character pair exactly once.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are average O(1), so total time is O(n) * O(1) = O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) [OK]

Hint: Single pass with hash maps -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring hash map average case

5. The following code attempts to check if two strings are isomorphic:

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
    return True

What is the bug in this code?

medium

A. Not checking length equality before processing

B. Missing check for reverse mapping from t to s, allowing multiple s chars to map to same t char

C. Using zip instead of indexing causes index errors

D. Returning True prematurely inside the loop

Solution

1. Step 1: Identify missing reverse mapping check

   The code only maps from s to t but does not verify if multiple characters in s map to the same character in t.

2. Step 2: Understand consequences

   This allows incorrect cases like s="ab" and t="aa" to return True incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional mapping is required to ensure one-to-one mapping [OK]

Hint: Check both s->t and t->s mappings [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Ignoring length check
• Misusing zip causing errors