LeetCode 873: Length of Longest Fibonacci Subsequence

Problem Restatement

We are given a strictly increasing array arr of positive integers.

We need to return the length of the longest Fibonacci-like subsequence.

A sequence is Fibonacci-like if:

1. Its length is at least 3.
2. For every valid position:

x[i] + x[i + 1] == x[i + 2]

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

If no Fibonacci-like subsequence exists, return 0.

Input and Output

Function shape:

class Solution:
    def lenLongestFibSubseq(self, arr: list[int]) -> int:
        ...

Examples

Example 1:

arr = [1, 2, 3, 4, 5, 6, 7, 8]

One longest Fibonacci-like subsequence is:

[1, 2, 3, 5, 8]

It has length:

5

So the answer is:

5

Example 2:

arr = [1, 3, 7, 11, 12, 14, 18]

Some Fibonacci-like subsequences are:

[1, 11, 12]
[3, 11, 14]
[7, 11, 18]

The longest length is 3.

So the answer is:

3

First Thought: Try Every Starting Pair

Once we choose the first two numbers of a Fibonacci-like sequence, the rest is determined.

For example, if the first two numbers are:

1, 2

then the next values must be:

3, 5, 8, 13, ...

So one direct method is:

1. Try every pair (arr[i], arr[j]).
2. Keep adding the next required value.
3. Use a set to check whether that value exists.
4. Track the longest length.

This works, but trying every pair and extending greedily can still do repeated work.

A dynamic programming solution records the best length for each ending pair.

Key Insight

A Fibonacci-like sequence is determined by its last two values.

Suppose a sequence ends with:

arr[j], arr[k]

Then the previous value must be:

arr[k] - arr[j]

So if there is an index i such that:

arr[i] + arr[j] == arr[k]

then we can extend the sequence ending with (arr[i], arr[j]) by adding arr[k].

Define:

dp[j][k]

as the length of the longest Fibonacci-like subsequence ending with:

arr[j], arr[k]

Then:

dp[j][k] = dp[i][j] + 1

when:

arr[i] = arr[k] - arr[j]

and:

i < j

We use a hash map from value to index to find i quickly.

Algorithm

Create a dictionary:

index = {value: position}

Initialize a 2D DP table with 2, because any pair can be the start of a possible Fibonacci-like sequence:

dp = [[2] * n for _ in range(n)]

Then iterate over all pairs (j, k) with j < k.

For each pair:

1. Compute:

prev = arr[k] - arr[j]

2. Check whether prev exists in the array.
3. Its index must be less than j.
4. If valid, update:

dp[j][k] = dp[i][j] + 1

5. Update the answer.

At the end, return the answer if it is at least 3. Otherwise return 0.

Correctness

For every pair (j, k), dp[j][k] represents the longest Fibonacci-like subsequence ending with arr[j] and arr[k].

The base length is 2, because any two numbers can be treated as a candidate pair before a third number is added.

If a valid previous value exists, then any Fibonacci-like subsequence ending with arr[i] and arr[j] can be extended by arr[k], because:

arr[i] + arr[j] == arr[k]

So dp[i][j] + 1 is a valid length for a sequence ending at (j, k).

Because arr is strictly increasing, the value-to-index map gives at most one possible previous index. The condition i < j preserves subsequence order.

The algorithm considers every possible ending pair (j, k), so every Fibonacci-like subsequence is considered at the moment its last two elements are processed.

Therefore, the maximum value found is the length of the longest Fibonacci-like subsequence. If the maximum never reaches 3, no valid Fibonacci-like subsequence exists, so returning 0 is correct.

Complexity

Let:

n = len(arr)

The hash map gives O(1) expected lookup time.

Implementation

class Solution:
    def lenLongestFibSubseq(self, arr: list[int]) -> int:
        n = len(arr)
        index = {value: i for i, value in enumerate(arr)}

        dp = [[2] * n for _ in range(n)]
        answer = 0

        for k in range(n):
            for j in range(k):
                prev = arr[k] - arr[j]

                if prev >= arr[j]:
                    continue

                if prev not in index:
                    continue

                i = index[prev]
                dp[j][k] = dp[i][j] + 1
                answer = max(answer, dp[j][k])

        return answer if answer >= 3 else 0

Code Explanation

We first build the index map:

index = {value: i for i, value in enumerate(arr)}

This lets us quickly find whether a needed previous value exists.

The DP table starts with length 2 for every pair:

dp = [[2] * n for _ in range(n)]

Then we choose the last index k and the second-last index j:

for k in range(n):
    for j in range(k):

The previous value must be:

prev = arr[k] - arr[j]

Since the array is strictly increasing and we need i < j, the previous value must be smaller than arr[j]:

if prev >= arr[j]:
    continue

If prev does not appear in the array:

if prev not in index:
    continue

then no valid previous element exists.

Otherwise, we extend the sequence:

i = index[prev]
dp[j][k] = dp[i][j] + 1

and update the best answer:

answer = max(answer, dp[j][k])

Finally:

return answer if answer >= 3 else 0

returns 0 when no Fibonacci-like subsequence exists.

Testing

def test_len_longest_fib_subseq():
    s = Solution()

    assert s.lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]) == 5

    assert s.lenLongestFibSubseq([1, 3, 7, 11, 12, 14, 18]) == 3

    assert s.lenLongestFibSubseq([1, 4, 10, 20]) == 0

    assert s.lenLongestFibSubseq([1, 2, 3]) == 3

    assert s.lenLongestFibSubseq([2, 4, 6, 10, 16, 26]) == 6

    print("all tests passed")

test_len_longest_fib_subseq()

Test meaning: