What happens if you not skipping duplicates after sorting?

Incorrectly counts duplicates as consecutive, inflating sequence length Fix: Add a condition to skip duplicates during linear scan

What happens if you not handling empty input array?

Code may crash or return wrong result Fix: Add explicit check for empty input and return 0

Interview Prephash-maps-setsmediumAmazonFacebookGoogleBloomberg

Longest Consecutive Sequence

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

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

For each number in the array, start counting consecutive numbers incrementally.
Check if the next consecutive number exists in the array by scanning it.
Keep track of the longest consecutive count found so far.
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.

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

Practice

(1/5)

1. Given an array of integers and an integer k, you need to determine if the array can be partitioned into pairs such that the sum of each pair is divisible by k. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map to count remainders modulo k and verify complementary counts.

B. Check all pairs with nested loops to find valid pairs.

C. Use dynamic programming to find subsets whose sums are divisible by k.

D. Use a greedy approach by pairing elements with the smallest remainder first.

4. The following code attempts to check if an array can be paired such that sums are divisible by k. Which line contains a subtle bug that causes incorrect results on some inputs?

def canArrange(nums, k):
    if len(nums) % 2 != 0:
        return True
    freq = {}
    for num in nums:
        r = ((num % k) + k) % k
        freq[r] = freq.get(r, 0) + 1
    if freq.get(0, 0) % 2 != 0:
        return False
    for r in freq:
        if r != 0:
            complement = (k - r) % k
            if freq.get(r, 0) != freq.get(complement, 0):
                return False
    if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
        return False
    return True

medium

A. Line 5: computing remainder without adjusting for negative numbers

B. Line 2: returning True when array length is odd

C. Line 8: checking if freq[0] count is even

D. Line 13: checking if freq[k//2] count is even when k is even

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that efficiently tracks remainder frequencies

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Trace iterations for input [1, 2, 3, 4], k=5

Step 2: Final count returned

Final Answer:

Quick Check:

Solution

Step 1: Check array length condition

Step 2: Verify other lines

Final Answer:

Quick Check:

Solution

Step 1: Examine dp update line

Step 2: Check other lines

Final Answer:

Quick Check:

Ready to prove it?