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. Consider the following Python function implementing the optimal approach for checking if a continuous subarray sum is a multiple of k. What is the return value when called with nums = [5, 0, 0] and k = 3?

easy

A. False

B. Returns True only if k divides the sum of the entire array

C. Raises an error due to modulo by zero

D. True

Solution

1. Step 1: Trace running_sum and remainder_map for each iteration

   i=0: running_sum=5%3=2, remainder_map={0:-1,2:0} i=1: running_sum=2+0=2%3=2, 2 in map at index 0, i-0=1 (not >1), continue i=2: running_sum=2+0=2%3=2, 2 in map at index 0, i-0=2 (>1), return True

2. Step 2: Confirm return value

   Function returns True because subarray [0,0] starting at index 1 has sum 0 which is multiple of 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Subarray length check and remainder map usage confirm True [OK]

Hint: Check remainder_map and subarray length > 1 carefully [OK]

Common Mistakes:

• Off-by-one error in subarray length check
• Ignoring initial remainder 0 at index -1
• Modulo by zero confusion when k=0

2. Consider the following code snippet implementing the optimal sliding window approach to find all anagrams of p in s. Given s = "abab" and p = "ab", what is the content of res after the loop completes?

easy

A. [0, 2]

B. [0, 1, 2]

C. [1, 2]

D. [0, 1]

Solution

1. Step 1: Initialize frequency counts for p = "ab" and first window in s = "ab"

   p_count and s_count both have counts for 'a' and 'b' as 1, so matches = 26 initially except for other letters.

2. Step 2: Slide window over s and update res

   At r=2, window is "ba" starting at index 1, matches == 26, append 0. At r=3, window is "ab" starting at index 2, matches == 26, append 1. After loop, append last index 2 if matches == 26. Final res = [0,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches found at indices 0 and 1 for "ab" and "ba" [OK]

Hint: Sliding window updates res at matches == 26 [OK]

Common Mistakes:

• Off-by-one errors in appending indices
• Forgetting last window check
• Miscounting matches after updates

3. Consider the following buggy code for counting subarrays with exactly k odd numbers. Which line contains the subtle bug that causes incorrect results for some inputs?

medium

A. Line with 'if nums[right] % 2 == 1: odd_count += 1'

B. Line with 'while odd_count >= k:'

C. Line with 'count += right - left + 1'

D. Line with 'return at_most_k(nums, k) - at_most_k(nums, k - 1)'

Solution

1. Step 1: Understand the window shrinking condition

   The window should shrink when odd_count > k, not when odd_count >= k, to correctly count subarrays with at most k odd numbers.

2. Step 2: Identify impact of bug

   Using '>=' shrinks the window too early, missing valid subarrays and causing undercount.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '>=' to '>' fixes the counting [OK]

Hint: Window shrinks only when odd_count exceeds k, not equals [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscounting subarrays due to early shrinking
• Confusing at_most_k with exactly k logic

4. What is the time complexity of the optimal dynamic programming solution that uses an array of hash maps to find the longest arithmetic subsequence length for an input array of size n?

medium

A. O(n^3) due to triple nested loops checking all subsequences

B. O(n^2 * W) where W is the range of possible differences

C. O(n log n) by sorting and binary searching differences

D. O(n^2) because each pair (i, j) is processed once with constant-time hash map operations on average

Solution

1. Step 1: Identify loops and operations

   The code has two nested loops over n, and inside uses hash map get/set which is average O(1).

2. Step 2: Confirm no hidden factors

   Difference range W does not affect complexity since hash maps handle keys efficiently; no sorting or extra loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two nested loops with O(1) hash ops -> O(n^2) time [OK]

Hint: Two nested loops with hash map ops yield O(n^2) time [OK]

Common Mistakes:

• Confusing difference range W as multiplicative factor
• Assuming triple nested loops from brute force
• Thinking sorting is involved

5. What is the time complexity of the optimal prefix sum with hash map solution for the Subarray Sum Equals K problem, given an input array of length n?

medium

A. O(n) because each element is processed once and hash map operations are O(1) on average

B. O(n) for iteration plus O(n) for prefix sum storage, total O(n) space and time

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n^2) due to nested loops over the array

Solution

1. Step 1: Identify main operations

   The algorithm iterates over the array once, updating running_sum and hash map counts.

2. Step 2: Analyze hash map operations

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

Hint: Hash map lookups are average O(1), not O(log n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming hash map operations are O(log n)
• Counting prefix sum storage as extra time