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. You are given an array of integers and need to determine if any value appears at least twice. Which approach guarantees the most efficient detection of duplicates in terms of time complexity?

easy

A. Sort the array and then scan once to check if any adjacent elements are equal.

B. Use a hash set to track seen elements and check membership while iterating once.

C. Use nested loops to compare every pair of elements for equality.

D. Use dynamic programming to build a table of duplicate occurrences.

Solution

1. Step 1: Understand the problem requirements

   The problem requires detecting duplicates efficiently in an array.

2. Step 2: Compare approaches based on time complexity

   Sorting then scanning is O(n log n), nested loops is O(n²), and dynamic programming is unnecessary here. Using a hash set allows O(n) time with O(n) space by checking membership during one pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set membership check is O(1) average, enabling linear time detection [OK]

Hint: Hash set membership check enables linear time detection [OK]

Common Mistakes:

• Confusing sorting approach as optimal
• Thinking nested loops are efficient enough
• Misapplying DP to a membership problem

2. 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

3. The following code attempts to find the longest contiguous subarray with equal number of 0s and 1s. Which line contains a subtle bug that can cause incorrect results on some inputs?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

medium

A. Line 3: Not initializing seen with {0: -1}

B. Line 6: Incorrect prefix_sum update logic

C. Line 8: Using max instead of min for max_length update

D. Line 10: Returning max_length instead of prefix_sum

Solution

1. Step 1: Check initialization of seen map

   Seen should start with {0: -1} to handle subarrays starting at index 0.

2. Step 2: Consequence of missing initialization

   Without {0: -1}, subarrays starting at index 0 with equal 0s and 1s are missed, causing incorrect max_length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing initial entry causes missed subarrays at start [OK]

Hint: Always initialize seen with sum 0 at index -1 [OK]

Common Mistakes:

• Forgetting initial seen entry
• Incorrect prefix sum update
• Wrong max_length update logic

4. The following code attempts to implement the remove operation for the Insert Delete GetRandom data structure. Identify the line that contains a subtle bug causing incorrect behavior.

def remove(self, val: int) -> bool:
    if val not in self.pos:
        return False
    idx = self.pos[val]
    last_element = self.nums[-1]
    self.nums[idx] = last_element
    # BUG: Missing update of last_element's position in pos
    self.nums.pop()
    del self.pos[val]
    return True

medium

A. Missing line: updating self.pos[last_element] = idx after swap

B. Line: last_element = self.nums[-1]

C. Line: self.nums[idx] = last_element

D. Line: idx = self.pos[val]

Solution

1. Step 1: Understand swap-delete logic

   After swapping last element into idx, the hash map must update last_element's index.

2. Step 2: Identify missing update

   The code does not update self.pos[last_element] = idx, so pos points to old index, causing inconsistency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without updating pos, getRandom or remove may fail [OK]

Hint: Always update hash map after swapping elements [OK]

Common Mistakes:

• Forgetting to update hash map after swap
• Assuming pop removes mapping automatically
• Updating wrong indices in hash map

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n with u unique elements?

medium

A. O(n + u) since building frequency map and buckets takes linear time

B. O(n log n) due to sorting the frequency map keys

C. O(u * log u) because sorting unique elements is required

D. O(n) because frequency counting and bucket filling are linear in n

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires iterating over n elements -> O(n)

2. Step 2: Analyze bucket filling and result collection

   Filling buckets and collecting top k elements is O(n) since total frequencies sum to n, plus O(u) for iterating unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complexity is O(n + u), which is linear since u ≤ n [OK]

Hint: Frequency counting + bucket filling is linear [OK]

Common Mistakes:

• Assuming sorting unique keys is needed
• Confusing n with u in complexity
• Ignoring that bucket iteration is linear in total elements