Longest Consecutive Sequence

▶

Steps

setup

Initialize hash set with all numbers

All numbers from the input array are inserted into a hash set to enable O(1) membership checks.

💡 Creating the hash set upfront allows the algorithm to quickly check if a number exists without sorting.

Line:

num_set = set(nums)

💡 Hash sets provide constant-time lookups, which is key to the algorithm's efficiency.

compare

Check if 100 is a sequence start

Check if 99 (100 - 1) is in the set to determine if 100 is the start of a sequence.

💡 A number is a sequence start only if the previous number is not in the set.

Line:

if num - 1 not in num_set:

💡 Detecting sequence starts avoids redundant counting of sequences from middle elements.

traverse

Count consecutive numbers starting at 100

Check if 101 (100 + 1) is in the set to count consecutive numbers after 100.

💡 Counting consecutive numbers confirms the length of the sequence starting at 100.

Line:

while current_num + 1 in num_set:

💡 Sequence starting at 100 has length 1 because 101 is missing.

update

Update max_len after sequence starting at 100

Update the maximum sequence length found so far to 1, the length of the sequence starting at 100.

💡 Tracking max_len ensures we remember the longest sequence found during iteration.

Line:

max_len = max(max_len, length)

💡 max_len is now 1, reflecting the longest sequence found so far.

compare

Check if 4 is a sequence start

Check if 3 (4 - 1) is in the set to determine if 4 is the start of a sequence.

💡 If the previous number exists, 4 is not a sequence start and will be skipped.

Line:

if num - 1 not in num_set:

💡 Skipping 4 avoids redundant counting since sequence starting at 1 will cover it.

compare

Check if 200 is a sequence start

Check if 199 (200 - 1) is in the set to determine if 200 is the start of a sequence.

💡 Sequence starts are only numbers without a predecessor in the set.

Line:

if num - 1 not in num_set:

💡 200 starts a sequence of length 1 since no consecutive numbers follow.

traverse

Count consecutive numbers starting at 200

Check if 201 (200 + 1) is in the set to count consecutive numbers after 200.

💡 Counting confirms the length of the sequence starting at 200.

Line:

while current_num + 1 in num_set:

💡 Sequence starting at 200 has length 1 because 201 is missing.

update

Update max_len after sequence starting at 200

Compare current sequence length 1 with max_len 1 and update max_len if needed.

💡 max_len remains 1 since the sequence length is not longer.

Line:

max_len = max(max_len, length)

💡 max_len stays 1 after processing 200.

compare

Check if 1 is a sequence start

Check if 0 (1 - 1) is in the set to determine if 1 is the start of a sequence.

💡 1 is a sequence start if 0 is not in the set.

Line:

if num - 1 not in num_set:

💡 We will count the consecutive sequence starting at 1.

traverse

Count consecutive numbers starting at 1

Check if 2 (1 + 1) is in the set, then 3, then 4, counting consecutive numbers.

💡 Counting consecutive numbers finds the length of the sequence starting at 1.

Line:

while current_num + 1 in num_set:

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

update

Update max_len after sequence starting at 1

Update max_len to 4, the length of the longest sequence found.

💡 max_len now reflects the longest consecutive sequence length in the input.

Line:

max_len = max(max_len, length)

💡 max_len is updated to 4, the final answer.

compare

Check if 3 is a sequence start

Check if 2 (3 - 1) is in the set to determine if 3 is the start of a sequence.

💡 3 is not a sequence start if 2 is in the set.

Line:

if num - 1 not in num_set:

💡 Skipping 3 avoids redundant counting.

compare

Check if 2 is a sequence start

Check if 1 (2 - 1) is in the set to determine if 2 is the start of a sequence.

💡 2 is not a sequence start if 1 is in the set.

Line:

if num - 1 not in num_set:

💡 Skipping 2 avoids redundant counting.

def longestConsecutive(nums):
    num_set = set(nums)  # STEP 1: Insert all numbers into set
    max_len = 0
    for num in num_set:  # Iterate over each number
        if num - 1 not in num_set:  # STEP 2,5,6,9,12,13: Check if num is sequence start
            current_num = num
            length = 1
            while current_num + 1 in num_set:  # STEP 3,7,10: Count consecutive numbers
                current_num += 1
                length += 1
            max_len = max(max_len, length)  # STEP 4,8,11: Update max_len
    return max_len

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

📊

Longest Consecutive Sequence - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how hash sets enable O(1) lookups and how the algorithm efficiently finds consecutive sequences without sorting.

insert

100→true

4→true

200→true

1→true

3→true

2→true

Result: 0

lookup

Lookup: 99

100→true

4→true

200→true

1→true

3→true

2→true

Result: 0

lookup

Lookup: 101

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

update

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

lookup

Lookup: 3→ true

100→true

4→true

200→true

1→true

3→truelookup

2→true

Result: 1

lookup

Lookup: 199

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

lookup

Lookup: 201

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

update

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

lookup

Lookup: 0

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

lookup

Lookup: 5

100→true

4→true

200→true

1→true

3→true

2→true

Result: 1

update

100→true

4→true

200→true

1→true

3→true

2→true

Result: 4

lookup

Lookup: 2→ true

100→true

4→true

200→true

1→true

3→true

2→truelookup

Result: 4

lookup

Lookup: 1→ true

100→true

4→true

200→true

1→truelookup

3→true

2→true

Result: 4

Key Takeaways

✓ Using a hash set allows O(1) membership checks, enabling the algorithm to find consecutive sequences without sorting.

This insight is hard to see from code alone because the efficiency gain from hash sets is implicit.

✓ Detecting sequence starts by checking if num-1 is absent prevents redundant counting of sequences.

Visually seeing which numbers are skipped clarifies why this check is crucial.

✓ Counting consecutive numbers from each start and updating max_len tracks the longest sequence efficiently.

Watching the incremental counting and max_len updates reveals the algorithm's core logic.

Practice

1. Consider the following code snippet for finding the longest contiguous subarray with equal 0s and 1s. What is the value of max_length returned for input [0, 1, 0]?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

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

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

2. Given the following code snippet, what is the returned value when the input string is "abc"?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace iterations for input "abc"

   Right=0: 'a', distinct_count=1, window=[0,0], max_length=1 Right=1: 'b', distinct_count=2, window=[0,1], max_length=2 Right=2: 'c', distinct_count=3 > 2 triggers while loop: Shrink from left: freq['a']--, distinct_count=2, left=1 Window=[1,2], max_length=max(2,2)=2 But max_length updated after while loop: max_length=max(2,2)=2 Actually, max_length is updated each iteration, so max_length=2 after right=1, then after right=2 window is [1,2] length=2

2. Step 2: Check final max_length

   Max length found is 2, but wait, initial max_length was 0, updated to 1, then 2, then 2 again. But the substring "bc" length=2, so final answer is 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest substring with at most 2 distinct chars in "abc" is "ab" or "bc" length 2 [OK]

Hint: Check window size after shrinking when distinct > 2 [OK]

Common Mistakes:

• Returning length as right - left instead of right - left + 1
• Not updating distinct_count correctly
• Off-by-one errors in window size

3. The following code attempts to count the number of subarrays with bounded maximum using the optimal approach, but it contains a subtle bug:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            # Bug: missing reset of length here
            pass
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

What is the bug in this code?

medium

A. The variable 'count' is not reset inside the loop, causing overcounting.

B. The function countAtMost should use max instead of length to track subarray size.

C. The 'length' variable is not reset to zero when encountering a number greater than bound.

D. The subtraction in numSubarrayBoundedMax should be reversed to avoid negative results.

Solution

1. Step 1: Understand the role of 'length'

   'length' tracks the length of the current valid subarray segment where elements ≤ bound.

2. Step 2: Identify the bug

   When an element > bound is encountered, 'length' must reset to 0 to avoid counting invalid subarrays. The code misses this reset, causing overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting 'length' on invalid elements is essential [OK]

Hint: Reset 'length' to zero on elements > bound [OK]

Common Mistakes:

• Forgetting to reset length
• Incorrect subtraction order
• Misusing count variable

4. The following code attempts to implement summaryRanges but has a subtle bug. Which line contains the bug?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

medium

A. Line 7: The inner while loop condition misses the last element in some cases.

B. Line 4: Not checking if input list is empty causes crash on empty input.

C. Line 11: Updating start to end + 1 might skip elements if end is not updated correctly.

D. Line 9: Always appending 'start->end' even when start == end causes incorrect output for single elements.

Solution

1. Step 1: Identify output format issue

   When start == end, the code appends 'num->num' instead of just 'num', which is incorrect per problem spec.

2. Step 2: Confirm other lines are correct

   Inner loop condition and start update are correct; empty input handling is not shown but not the subtle bug here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single element ranges must be output as single numbers, not ranges [OK]

Hint: Single element ranges output as 'num', not 'num->num' [OK]

Common Mistakes:

• Appending 'start->end' even when start == end
• Off-by-one in inner loop
• Skipping last range due to loop condition

5. Suppose the problem is modified so that elements can be reused multiple times in the subsequence (i.e., indices can be repeated). Which modification to the DP approach correctly handles this variant?

hard

A. Use a recursive memoized solution that tries all possible next elements including the current one

B. Keep the same DP but allow j to equal i in the inner loop to reuse elements

C. Modify DP to track counts per difference but reset dp[i][diff] to 1 each time to allow reuse

D. Use a graph-based BFS to explore sequences allowing repeated nodes

Solution

1. Step 1: Understand reuse means indices can repeat

   Standard DP assumes strictly increasing indices; allowing reuse breaks this assumption.

2. Step 2: Recognize recursive memoization can explore all sequences with repeated elements

   Recursive approach with memoization can try all next elements including current, correctly handling reuse.

3. Step 3: Evaluate other options

   Allowing j == i breaks DP indexing logic; resetting dp[i][diff] loses subsequence length info; BFS is inefficient and complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recursive memoization handles repeated indices correctly [OK]

Hint: Reuse requires recursion with memoization, not standard DP indexing [OK]

Common Mistakes:

• Allowing j == i in DP loops breaks monotonic index assumption
• Resetting dp values loses subsequence length info
• Trying BFS which is inefficient