Longest Consecutive Sequence

📋

Problem

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.

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

Edge cases: All elements are the same → output is 1Array with one element → output is 1Array with no consecutive numbers → output is 1

</>

IDE

def longestConsecutive(nums: list[int]) -> int:public int longestConsecutive(int[] nums)int longestConsecutive(vector<int>& nums)function longestConsecutive(nums)

def longestConsecutive(nums):
    # Write your solution here
    pass

class Solution {
    public int longestConsecutive(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function longestConsecutive(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty input due to missing base case handling for empty or single-element arrays.✅ Add a check at the start: if not nums: return 0; if len(nums) == 1: return 1.

Wrong: 5Counting duplicates multiple times inflates sequence length incorrectly.✅ Use a set to remove duplicates before counting sequences.

Wrong: 2Failing to detect sequence starts properly, counting sequences from non-start points.✅ Only count sequence length starting from numbers where num-1 is not in the set.

Wrong: 1Failing to handle negative numbers correctly in the hash set or sequence detection.✅ Ensure the hash set supports negative numbers and sequence start detection works for them.

Wrong: TLEUsing brute force nested loops resulting in O(n^2) time complexity.✅ Use a hash set and sequence start detection to achieve O(n) time complexity.

✓

Test Cases

Try testing your code on empty and single-element arrays to handle base cases.

Consider how duplicates and negative numbers affect your sequence detection logic.

Focus on optimizing your solution to run in linear time using hash sets.

t1_01basic

Input{"nums":[100,4,200,1,3,2]}

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Use a hash set to quickly check if a number exists.

💡 Only start counting sequence length from numbers that are sequence starts (num-1 not in set).

💡 For each start, count consecutive numbers until the sequence breaks.

Why it failed: Failed to detect sequence starts properly or incorrectly counted sequence length. Fix by checking if num-1 is not in set before counting.

✓ Correctly identifies sequence starts and counts consecutive sequences.

t1_02basic

Input{"nums":[10,5,12,3,55,30,4,11,2]}

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Check for sequence starts by verifying num-1 is not in the set.

💡 Count consecutive numbers from each start until the sequence breaks.

💡 Return the maximum length found among all sequences.

Why it failed: Incorrectly counted sequences starting at non-start points or missed sequences. Fix by only counting from sequence starts where num-1 not in set.

✓ Correctly finds the longest consecutive sequence length.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no sequences, so longest length is 0.

💡 Consider what the longest sequence length should be if input is empty.

💡 Check if your code handles empty input without errors.

💡 Return 0 immediately if nums is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty input and returning 0.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"nums":[42]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array has longest consecutive sequence length 1.

💡 A single element is a sequence of length 1 by itself.

💡 Ensure your code handles single-element arrays correctly.

💡 Return 1 if nums length is 1.

Why it failed: Code returns 0 or crashes on single element input. Fix by handling single element case properly.

✓ Correctly returns 1 for single element input.

t2_03edge

Input{"nums":[10,30,20,40]}

Expected1

⏱ Performance - must finish in 2000ms

No consecutive numbers, so longest sequence length is 1.

💡 Check if your code correctly handles arrays with no consecutive numbers.

💡 Each number alone forms a sequence of length 1.

💡 Return 1 as the longest sequence length in this case.

Why it failed: Code incorrectly counts sequences by assuming consecutive numbers exist. Fix by verifying sequence continuity properly.

✓ Correctly returns 1 when no consecutive numbers exist.

t3_01corner

Input{"nums":[1,2,2,3]}

Expected3

⏱ Performance - must finish in 2000ms

Duplicates do not extend sequence; longest consecutive sequence is [1, 2, 3].

💡 Remove duplicates by using a set before processing.

💡 Counting duplicates multiple times inflates sequence length incorrectly.

💡 Use a hash set to ignore duplicates and count unique consecutive numbers.

Why it failed: Counting duplicates multiple times inflates sequence length. Fix by using a set to remove duplicates before counting.

✓ Correctly handles duplicates by using a set.

t3_02corner

Input{"nums":[100,4,200,1,3,2,2,3,4,5]}

Expected5

⏱ Performance - must finish in 2000ms

Longest consecutive sequence is [1, 2, 3, 4, 5], duplicates ignored.

💡 Ensure duplicates do not cause incorrect sequence length.

💡 Check sequence start condition carefully to avoid counting partial sequences multiple times.

💡 Use set membership and start detection to count sequences correctly.

Why it failed: Incorrectly counts sequences starting at non-start points or counts duplicates multiple times. Fix by checking num-1 not in set and using set to remove duplicates.

✓ Correctly finds longest sequence ignoring duplicates and counting from proper starts.

t3_03corner

Input{"nums":[-2,-1,0,1,2]}

Expected5

⏱ Performance - must finish in 2000ms

Handles negative and positive numbers; longest sequence is [-2, -1, 0, 1, 2].

💡 Check that negative numbers are handled correctly in the set.

💡 Sequence start detection must work for negative numbers as well.

💡 Counting consecutive numbers should work regardless of sign.

Why it failed: Fails to handle negative numbers correctly, possibly due to incorrect set membership checks. Fix by using a hash set that supports negative values.

✓ Correctly handles negative and positive numbers in sequences.

t4_01performance

Input{"nums":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, sequence is a descending consecutive sequence of length 100, must complete in O(n) time within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use a hash set and only start counting sequences at sequence starts.

💡 Optimal solution runs in O(n) time using set membership and sequence start detection.

Why it failed: TLE due to O(n^2) brute force approach. Fix by using hash set and sequence start detection for O(n) solution.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given two integer arrays and need to find all elements that appear in both arrays, including duplicates, with the output containing each common element as many times as it appears in both arrays. Which approach guarantees the most efficient solution in terms of time complexity for large inputs?

easy

A. Sort both arrays and use two pointers to traverse them simultaneously, collecting common elements.

B. Use dynamic programming to build a table of common elements counts.

C. Use nested loops to check each element of the first array against all elements of the second array.

D. Use a greedy approach to pick elements from the first array that appear earliest in the second array.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding all common elements including duplicates, so a method that preserves counts is needed.

2. Step 2: Evaluate approaches

   Sorting both arrays and using two pointers allows linear traversal after sorting, efficiently finding all duplicates. Nested loops are O(m*n), DP is not applicable here, and greedy does not guarantee correct counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is O(m log m + n log n) and handles duplicates correctly [OK]

Hint: Sorting + two pointers handles duplicates efficiently [OK]

Common Mistakes:

• Thinking nested loops are efficient enough
• Confusing DP applicability
• Assuming greedy works for duplicates

2. You are given two strings s and t. You need to determine if there exists a one-to-one character mapping from s to t such that replacing characters in s with their mapped characters produces t. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to track substring isomorphisms

B. Greedy approach that maps characters as they appear without checking reverse mapping

C. Bidirectional hash map mapping that ensures one-to-one character correspondence

D. Brute force nested loops checking all character pairs for consistency

Solution

1. Step 1: Understand the problem constraints

   The problem requires a one-to-one mapping between characters of two strings, ensuring no two characters in s map to the same character in t and vice versa.

2. Step 2: Identify the approach that enforces bidirectional mapping

   Only the bidirectional hash map approach maintains two maps: one from s to t and another from t to s, ensuring the mapping is consistent and one-to-one.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional mapping prevents false positives like mapping "ab" to "aa" [OK]

Hint: One-to-one mapping requires bidirectional checks [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Using DP which is unnecessary
• Relying on greedy without reverse check

3. Consider the following Python function that finds the length of the longest subarray with sum divisible by k. What is the returned value when called with nums = [2, 7, 6, 1] and k = 5?

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        if remainder < 0:
            remainder += k
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace prefix sums and remainders

   nums = [2,7,6,1], k=5 - i=0: prefix_sum=2, remainder=2, earliest[2]=-2 -> earliest[2]=0 - i=1: prefix_sum=9, remainder=4, earliest[4]=-2 -> earliest[4]=1 - i=2: prefix_sum=15, remainder=0, earliest[0]=-1 -> max_length=max(0,2-(-1))=3 - i=3: prefix_sum=16, remainder=1, earliest[1]=-2 -> earliest[1]=3

2. Step 2: Final max_length is 3

   The longest subarray divisible by 5 has length 3 (from index 0 to 2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Longest subarray length = 3 [OK]

Hint: Track prefix sums and earliest remainder indices carefully [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Forgetting to initialize earliest[0] = -1
• Ignoring negative remainder adjustment

4. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

5. Suppose the problem is modified so that negative integers are allowed as input. Which of the following changes to the optimal Happy Number detection algorithm correctly handles negative inputs without breaking correctness or efficiency?

hard

A. Reject negative inputs immediately as invalid and return false

B. Add negative numbers to the unhappy cycle set to detect cycles quickly

C. Ignore the sign and compute sum of squares of digits of the absolute value; proceed as usual

D. Modify sum_of_squares to include the sign squared (which is always positive) and proceed

Solution

1. Step 1: Consider negative input handling

   Sum of squares of digits depends on digits, not sign; absolute value preserves digits.

2. Step 2: Verify correctness and efficiency

   Using absolute value avoids complexity and maintains correctness; no need to add negatives to cycle set or reject.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Absolute value preserves digit sums and cycle detection [OK]

Hint: Use absolute value to handle negative inputs [OK]

Common Mistakes:

• Adding negatives to cycle set
• Rejecting negatives unnecessarily