Longest Consecutive Sequence

You’re interested in finding the length of the longest consecutive sequence of integers in an array, and the algorithm should run in O(n) time complexity. Here’s an approach that fulfills these requirements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set(nums)
        longest_sequence = 0

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_sequence = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_sequence += 1

                longest_sequence = max(longest_sequence, current_sequence)

        return longest_sequence

Explanation

1. Create a Set: Convert the input list into a set, which provides O(1) lookup time.

2. Iterate Through Numbers: Iterate through the set of numbers. For each number, if its preceding number (num - 1) is not in the set, we begin to explore the sequence from this number.

3. Find Consecutive Numbers: Start from the current number and repeatedly check whether the next number (current_num + 1) is in the set. Keep track of the length of the sequence in current_sequence.

4. Update Maximum Length: If the current sequence length is greater than the existing longest sequence length, update it.

Key Takeaway

By using a set for efficient lookups and a clever iteration strategy that skips over numbers already counted in a sequence, this algorithm achieves the desired O(n) time complexity. It successfully identifies the length of the longest consecutive sequence of integers in the given array.

Identifying Problem Isomorphism

“Longest Consecutive Sequence” has similarities with the problem “Maximum Length of Pair Chain”.

In the “Longest Consecutive Sequence” problem, you’re given an unsorted array of integers and the task is to find the longest consecutive elements sequence.

In the “Maximum Length of Pair Chain”, you are given n pairs where each pair in the form of (a, b) could be chained together to form a chain. You need to find the maximum number of pairs you can chain together, where ‘b’ of one pair is less than ‘a’ of the next pair.

The isomorphism is the concept of finding sequences or chains. Both problems involve finding a sequence, but the condition on which elements can be part of the sequence is different. In “Longest Consecutive Sequence”, it’s about numbers being consecutive, while in “Maximum Length of Pair Chain”, it’s about one number being less than the next.

“Longest Consecutive Sequence” is simpler since it doesn’t require managing pairs of numbers. In “Maximum Length of Pair Chain”, handling pairs and their relationships adds complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums)

        for n in num_set:
            if (n-1) not in num_set:
                length = 1
                while (n+length) in num_set:
                    length += 1
                longest = max(longest, length)

        return longest

Problem Classification

Language Agnostic Coding Drills

Here are the main concepts and skills involved in understanding this code, from most basic to more advanced, with corresponding practice activities:

1. Basic understanding of Python syntax

Drill: Write a simple Python program to print “Hello, World!”.

2. Understanding variables and assignment

Drill: Declare variables of different types (string, integer, float, boolean) and print their values.

3. Understanding functions

Drill: Define a function that takes two arguments and returns their sum.

4. Using built-in functions

Drill: Use Python built-in functions like print(), len(), max(), etc.

5. Understanding Python lists

Drill: Create a list, add elements, access elements by their index, and use a list in a loop.

6. Understanding of Python sets

Drill: Create a set, add elements, and check for the presence of elements.

7. Understanding if statements

Drill: Write a function that takes an integer and prints whether it’s positive, negative, or zero using if-elif-else statements.

8. Understanding for loops

Drill: Write a function that iterates over a list and prints each element.

9. Understanding while loops

Drill: Write a function that counts down from a given number to zero using a while loop.

10. Understanding function calls and returns

Drill: Write two functions, where the first calls the second with a parameter and then prints the result.

11. Basic understanding of classes and methods

Drill: Define a class with one method and instantiate an object of this class.

12. Understanding the concept of “not in” for sets

Drill: Create a set of integers and write a function that checks whether a given number is not in the set.

13. Understanding of increment operation

Drill: Write a function that adds 1 to a number until it reaches a given limit.

Once these concepts are understood and the corresponding drills are mastered, understanding the provided code should be straightforward.

Targeted Drills in Python

1. Basic understanding of Python syntax

Drill: Write a simple Python program to print “Hello, World!”.

1

print("Hello, World!")

2. Understanding variables and assignment

Drill: Declare variables of different types (string, integer, float, boolean) and print their values.

1
2
3
4
5

a = "Hello"
b = 123
c = 3.14
d = True
print(a, b, c, d)

3. Understanding functions

Drill: Define a function that takes two arguments and returns their sum.

1
2

def add(a, b):
    return a + b

4. Using built-in functions

Drill: Use Python built-in functions like print(), len(), max(), etc.

1
2
3

nums = [1, 2, 3, 4, 5]
print(len(nums))
print(max(nums))

5. Understanding Python lists

Drill: Create a list, add elements, access elements by their index, and use a list in a loop.

1
2
3
4
5

nums = [1, 2, 3, 4, 5]
nums.append(6)
print(nums[0])
for num in nums:
    print(num)

6. Understanding of Python sets

Drill: Create a set, add elements, and check for the presence of elements.

1
2
3

num_set = {1, 2, 3, 4, 5}
num_set.add(6)
print(1 in num_set)

7. Understanding if statements

Drill: Write a function that takes an integer and prints whether it’s positive, negative, or zero using if-elif-else statements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def check_num(n):
    if n > 0:
        print("Positive")
    elif n < 0:
        print("Negative")
    else:
        print("Zero")

check_num(5)
check_num(-3)
check_num(0)

8. Understanding for loops

Drill: Write a function that iterates over a list and prints each element.

1
2
3
4
5

def print_elements(nums):
    for num in nums:
        print(num)

print_elements([1, 2, 3, 4, 5])

9. Understanding while loops

Drill: Write a function that counts down from a given number to zero using a while loop.

1
2
3
4
5
6

def count_down(n):
    while n >= 0:
        print(n)
        n -= 1

count_down(5)

10. Understanding function calls and returns

Drill: Write two functions, where the first calls the second with a parameter and then prints the result.

1
2
3
4
5
6
7
8

def square(n):
    return n ** 2

def print_square(n):
    result = square(n)
    print(result)

print_square(5)

11. Basic understanding of classes and methods

Drill: Define a class with one method and instantiate an object of this class.

1
2
3
4
5
6

class Greeter:
    def greet(self, name):
        print("Hello, " + name)

g = Greeter()
g.greet("World")

12. Understanding the concept of “not in” for sets

Drill: Create a set of integers and write a function that checks whether a given number is not in the set.

1
2
3
4
5
6
7
8

def check_num(num_set, n):
    if n not in num_set:
        print(f"{n} is not in the set")

num_set =

 {1, 2, 3, 4, 5}
check_num(num_set, 6)

13. Understanding of increment operation

Drill: Write a function that adds 1 to a number until it reaches a given limit.

1
2
3
4
5
6

def increment_to_limit(n, limit):
    while n < limit:
        print(n)
        n += 1

increment_to_limit(1, 5)