Jobs

Interviews

Discussions

Length of Longest Fibonacci Subsequence

Medium

Asked by:

18 views

Topics:

ArraysDynamic ProgrammingGraphs

A sequence x₁, x₂, ..., x_n is Fibonacci-like if:

n >= 3
x_i + x_i+1 == x_i+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints:

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10⁹

Try coding it in LeetCode

Length of Longest Fibonacci Subsequence

Medium

Asked by:

18 views

Topics:

ArraysDynamic ProgrammingGraphs

A sequence x₁, x₂, ..., x_n is Fibonacci-like if:

n >= 3
x_i + x_i+1 == x_i+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints:

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Are there any duplicate numbers in the input array, and if so, how should they be handled?
If no Fibonacci subsequence exists, what should the function return?
Is the input array guaranteed to be sorted?
Can the input array be empty or null?

Brute Force Solution

Approach

The brute force approach to finding the longest Fibonacci-like sequence involves checking every possible pair of starting numbers. For each pair, we'll see if we can build a longer sequence following the Fibonacci rule and then find the length of the longest one.

Here's how the algorithm would work step-by-step:

Pick the first two numbers from the given list. These will be the start of a potential Fibonacci-like sequence.
Check if the sum of the first two numbers exists later in the list.
If the sum exists, add it to the sequence and repeat the process by summing the last two numbers in the new, longer sequence.
Continue adding numbers to the sequence as long as their sum exists in the list.
If the sum doesn't exist, this particular Fibonacci-like sequence ends.
Keep track of the length of this sequence.
Repeat this process, starting with every possible pair of numbers from the beginning.
Once you've tried all possible starting pairs, compare the lengths of all the Fibonacci-like sequences you've found.
Return the length of the longest sequence found. If all sequences have fewer than 3 elements, return 0 (as per problem definition).

Code Implementation

def length_of_longest_fibonacci_subsequence(numbers):
    longest_sequence_length = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Consider each pair as a potential start to a fibonacci sequence

            first_number = numbers[first_index]
            second_number = numbers[second_index]
            current_sequence = [first_number, second_number]

            while True:
                next_number = first_number + second_number

                if next_number in numbers:
                    current_sequence.append(next_number)
                    first_number = second_number
                    second_number = next_number
                else:
                    # Break if next number does not exist

                    break

            # Update longest sequence only if it is a valid fibonacci sequence
            if len(current_sequence) > 2:
                longest_sequence_length = max(longest_sequence_length, len(current_sequence))

    if longest_sequence_length >= 3:
        return longest_sequence_length
    else:
        return 0

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible pairs of starting numbers in the input array of size n. This requires a nested loop, resulting in O(n^2) iterations. For each pair, it attempts to extend the Fibonacci-like sequence, potentially searching for the next number in the sequence within the array. In the worst case, this search can take O(n) time. Therefore, the overall time complexity is O(n^2 * n), which simplifies to O(n^3).

Space Complexity

O(1) – The provided brute force approach primarily uses variables to store the first two numbers of the sequence, the sum, and the current length of the Fibonacci-like sequence. No auxiliary data structures like arrays or hash maps that scale with the input size N (the length of the input list) are employed. Therefore, the extra space used by this algorithm remains constant, regardless of the input list's size.

Optimal Solution

Approach

The goal is to find the longest possible sequence of numbers within a given set where each number is the sum of the previous two. To avoid checking every possible sequence, we can cleverly remember which numbers exist in the set to speed up the process.

Here's how the algorithm would work step-by-step:

First, let's record which numbers are present in our set to quickly check for their existence later.
Start by picking any two numbers from the set as the beginning of a potential Fibonacci-like sequence.
Calculate what the next number in the sequence should be by adding the two numbers we picked.
Check if that calculated number actually exists in our set using the recorded information.
If it does exist, add it to our sequence and repeat the calculation step using the last two numbers in the sequence.
If it doesn't exist, stop building that sequence and note its length.
Repeat this process starting with every possible pair of numbers from the set, remembering to keep track of the longest sequence we find.
Finally, return the length of the longest Fibonacci-like sequence discovered.

Code Implementation

def length_of_longest_fibonacci_subsequence(numbers):
    number_set = set(numbers)
    maximum_length = 0

    # Iterate through all possible starting pairs
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            first_number = numbers[i]
            second_number = numbers[j]
            current_length = 2

            # Build the Fibonacci-like sequence
            while True:
                next_number = first_number + second_number

                # Check if the next number exists in the set
                if next_number in number_set:
                    first_number = second_number
                    second_number = next_number
                    current_length += 1

                    # Update the maximum length
                    maximum_length = max(maximum_length, current_length)
                else:
                    break

    # Fibonacci subsequences must have at least 3 elements
    if maximum_length >= 3:
        return maximum_length
    else:
        return 0

Big(O) Analysis

Time Complexity

O(n^2 * log m) – The algorithm iterates through all possible pairs of numbers in the input array of size n, resulting in O(n^2) iterations. For each pair, it extends the Fibonacci-like sequence as long as the next number exists in the set. Checking for the existence of a number in the set (represented by the largest value m in the input, not the length n) takes O(log m) time on average, assuming the numbers are stored in a hash set or similar data structure with logarithmic lookup. Therefore, the overall time complexity is O(n^2 * log m).

Space Complexity

O(N) – The primary contributor to auxiliary space is the set used to record the presence of numbers, which takes O(N) space, where N is the number of elements in the input array. While other variables are used, their space usage is constant. The nested loops iterate through possible starting pairs, but they do not allocate significant memory. Therefore, the dominant factor is the space used by the set.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or has fewer than 3 elements, as a Fibonacci subsequence requires at least three numbers.
Array with only two elements	Return 0 because a Fibonacci subsequence requires at least three elements.
Array with identical values (e.g., [2, 2, 2, 2])	The algorithm should not enter an infinite loop; the expected result is 0 as there's no valid Fibonacci subsequence of length >=3.
Integer overflow when summing elements	Use a data type that can accommodate larger sums (e.g., long) or check for potential overflow before performing the addition.
Large input array (performance)	Use a hash set (or dictionary) for quick lookups of whether a number exists in the array, to optimize time complexity.
Array with negative numbers or zero	The problem statement may not specify that the integers are positive; handle cases where numbers can be zero or negative by ensuring the lookup map can handle them.
No Fibonacci subsequence exists	The algorithm should correctly identify that no Fibonacci subsequence exists and return 0.
Array containing duplicate numbers that could form multiple fibonacci subsequences starting from the same pair	Hashmap approach will overwrite duplicate index values, preventing multiple additions to the same sequence for equivalent values.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Are there any duplicate numbers in the input array, and if so, how should they be handled?
If no Fibonacci subsequence exists, what should the function return?
Is the input array guaranteed to be sorted?
Can the input array be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick the first two numbers from the given list. These will be the start of a potential Fibonacci-like sequence.
Check if the sum of the first two numbers exists later in the list.
If the sum exists, add it to the sequence and repeat the process by summing the last two numbers in the new, longer sequence.
Continue adding numbers to the sequence as long as their sum exists in the list.
If the sum doesn't exist, this particular Fibonacci-like sequence ends.
Keep track of the length of this sequence.
Repeat this process, starting with every possible pair of numbers from the beginning.
Once you've tried all possible starting pairs, compare the lengths of all the Fibonacci-like sequences you've found.
Return the length of the longest sequence found. If all sequences have fewer than 3 elements, return 0 (as per problem definition).

Code Implementation

def length_of_longest_fibonacci_subsequence(numbers):
    longest_sequence_length = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Consider each pair as a potential start to a fibonacci sequence

            first_number = numbers[first_index]
            second_number = numbers[second_index]
            current_sequence = [first_number, second_number]

            while True:
                next_number = first_number + second_number

                if next_number in numbers:
                    current_sequence.append(next_number)
                    first_number = second_number
                    second_number = next_number
                else:
                    # Break if next number does not exist

                    break

            # Update longest sequence only if it is a valid fibonacci sequence
            if len(current_sequence) > 2:
                longest_sequence_length = max(longest_sequence_length, len(current_sequence))

    if longest_sequence_length >= 3:
        return longest_sequence_length
    else:
        return 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, let's record which numbers are present in our set to quickly check for their existence later.
Start by picking any two numbers from the set as the beginning of a potential Fibonacci-like sequence.
Calculate what the next number in the sequence should be by adding the two numbers we picked.
Check if that calculated number actually exists in our set using the recorded information.
If it does exist, add it to our sequence and repeat the calculation step using the last two numbers in the sequence.
If it doesn't exist, stop building that sequence and note its length.
Repeat this process starting with every possible pair of numbers from the set, remembering to keep track of the longest sequence we find.
Finally, return the length of the longest Fibonacci-like sequence discovered.

Code Implementation

def length_of_longest_fibonacci_subsequence(numbers):
    number_set = set(numbers)
    maximum_length = 0

    # Iterate through all possible starting pairs
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            first_number = numbers[i]
            second_number = numbers[j]
            current_length = 2

            # Build the Fibonacci-like sequence
            while True:
                next_number = first_number + second_number

                # Check if the next number exists in the set
                if next_number in number_set:
                    first_number = second_number
                    second_number = next_number
                    current_length += 1

                    # Update the maximum length
                    maximum_length = max(maximum_length, current_length)
                else:
                    break

    # Fibonacci subsequences must have at least 3 elements
    if maximum_length >= 3:
        return maximum_length
    else:
        return 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or has fewer than 3 elements, as a Fibonacci subsequence requires at least three numbers.
Array with only two elements	Return 0 because a Fibonacci subsequence requires at least three elements.
Array with identical values (e.g., [2, 2, 2, 2])	The algorithm should not enter an infinite loop; the expected result is 0 as there's no valid Fibonacci subsequence of length >=3.
Integer overflow when summing elements	Use a data type that can accommodate larger sums (e.g., long) or check for potential overflow before performing the addition.
Large input array (performance)	Use a hash set (or dictionary) for quick lookups of whether a number exists in the array, to optimize time complexity.
Array with negative numbers or zero	The problem statement may not specify that the integers are positive; handle cases where numbers can be zero or negative by ensuring the lookup map can handle them.
No Fibonacci subsequence exists	The algorithm should correctly identify that no Fibonacci subsequence exists and return 0.
Array containing duplicate numbers that could form multiple fibonacci subsequences starting from the same pair	Hashmap approach will overwrite duplicate index values, preventing multiple additions to the same sequence for equivalent values.