LeetCode 873 - Length of Longest Fibonacci Subsequence

The problem asks us to find the length of the longest subsequence in a strictly increasing array that forms a Fibonacci-like sequence. A Fibonacci-like sequence follows the rule: for every valid index in the sequence, and the sequence must contain at least three numbers.

leetcodemediumarrayhash-tabledynamic-programming

LeetCode Problem 873

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the length of the longest subsequence in a strictly increasing array that forms a Fibonacci-like sequence.

A Fibonacci-like sequence follows the rule:

$x_i + x_{i+1} = x_{i+2}$

for every valid index in the sequence, and the sequence must contain at least three numbers.

Unlike the classic Fibonacci sequence, the sequence here does not have to start with 1, 1. Any starting pair is valid as long as every subsequent number is the sum of the previous two numbers.

The input is a strictly increasing array of positive integers. Because the array is strictly increasing, every value appears at most once, which becomes extremely important for efficient lookup strategies. We are allowed to delete elements while preserving order, which means we are looking for a subsequence rather than a contiguous subarray.

The output is the length of the longest valid Fibonacci-like subsequence. If no such subsequence of length at least 3 exists, we return 0.

The constraints tell us a lot about the expected solution:

  • arr.length <= 1000
  • values can be as large as 10^9

An O(n^3) solution may be borderline or too slow in practice for n = 1000, especially in Python. This strongly suggests that we need a dynamic programming solution around O(n^2).

Several edge cases are important:

  • The array may contain no Fibonacci-like subsequence at all.
  • Multiple subsequences may exist, but we only need the maximum length.
  • Large integer values prevent us from using approaches based on array indexing by value.
  • Since the array is strictly increasing, if arr[k] >= arr[j], then arr[i] = arr[k] - arr[j] cannot appear before j. This observation becomes useful for pruning invalid states.

Approaches

Brute Force Approach

The brute-force idea is to try every possible pair of starting elements and greedily extend the Fibonacci-like sequence.

For every pair (arr[i], arr[j]), we repeatedly check whether their sum exists in the array. If it does, we extend the sequence and continue. To make lookup efficient, we can store all array values in a hash set.

For example:

  • start with (1, 2)
  • next expected value is 3
  • then (2, 3) produces 5
  • then (3, 5) produces 8

This correctly generates valid Fibonacci-like subsequences.

The issue is that we try every pair of starting points, which gives O(n^2) starting combinations. Each sequence extension can take up to O(n) steps in the worst case, producing an overall complexity of O(n^3).

Although this may pass in optimized languages, it is not ideal for the given constraints.

Optimal Dynamic Programming Approach

The key observation is that a Fibonacci-like sequence is completely determined by its last two elements.

Suppose we know a sequence ending with:

..., a, b

Then the next number must be:

a + b

This naturally suggests dynamic programming on pairs of indices.

We define:

dp[j][k]

as the length of the longest Fibonacci-like subsequence ending at indices j and k.

To extend a sequence ending in (i, j) into (j, k), we need:

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

Rearranging:

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

Since the array is strictly increasing, we can use a hash map from value to index to instantly locate arr[i].

This reduces the problem to checking all ordered pairs (j, k) in O(1) time each, producing an overall O(n^2) solution.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n) Try every starting pair and greedily extend sequences
Optimal O(n²) O(n²) Dynamic programming on index pairs with hash map lookup

Algorithm Walkthrough

  1. Create a hash map from array value to its index.

This allows constant-time lookup for determining whether a required predecessor exists. Since the array is strictly increasing and contains unique values, each value maps to exactly one index. 2. Initialize a dynamic programming table.

We use:

dp[j][k]

to represent the length of the longest Fibonacci-like subsequence ending with arr[j] and arr[k].

Every pair initially has length 2, because any two numbers can form the start of a potential sequence. 3. Iterate through every pair (j, k) where j < k.

We treat arr[k] as the current ending element and attempt to find a valid predecessor. 4. Compute the required previous value.

For a Fibonacci-like relation:

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

Rearranging gives:

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

We calculate this value and check whether it exists in the hash map. 5. Ensure index ordering is valid.

Even if the value exists, we must verify:

i < j

because subsequences must preserve array order. 6. Extend the previous sequence.

If a valid i exists:

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

This means we extend the sequence ending at (i, j) by appending arr[k]. 7. Track the global maximum.

Every time we update a DP state, we update the maximum sequence length found so far. 8. Return the answer.

If the maximum length is still less than 3, return 0. Otherwise return the maximum.

Why it works

The dynamic programming state captures the exact information needed to extend a Fibonacci-like subsequence: its final two elements. Every valid extension depends only on those two values. Because we process all pairs (j, k) and correctly identify their predecessor i, every possible Fibonacci-like subsequence is considered exactly once. The recurrence relation guarantees that longer sequences are built from already-correct shorter sequences.

Python Solution

from typing import List

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)

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

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

        longest = 0

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

                if previous_value in value_to_index:
                    i = value_to_index[previous_value]

                    if i < j:
                        dp[j][k] = dp[i][j] + 1
                        longest = max(longest, dp[j][k])

        return longest if longest >= 3 else 0

The implementation begins by constructing a hash map called value_to_index. This allows constant-time lookup of any array value's position.

The dp table is initialized with 2 because any pair of numbers forms a trivial subsequence of length two. We only increase this value when a valid Fibonacci extension exists.

The nested loops iterate over every ordered pair (j, k). For each pair, we compute the required predecessor value using:

arr[k] - arr[j]

If this predecessor exists and appears before index j, we extend the existing subsequence:

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

The variable longest tracks the maximum sequence length discovered during processing.

Finally, we return 0 if no Fibonacci-like subsequence of length at least three exists.

Go Solution

func lenLongestFibSubseq(arr []int) int {
	n := len(arr)

	valueToIndex := make(map[int]int)

	for i, value := range arr {
		valueToIndex[value] = i
	}

	dp := make([][]int, n)

	for i := range dp {
		dp[i] = make([]int, n)

		for j := range dp[i] {
			dp[i][j] = 2
		}
	}

	longest := 0

	for k := 0; k < n; k++ {
		for j := 0; j < k; j++ {
			previousValue := arr[k] - arr[j]

			i, exists := valueToIndex[previousValue]

			if exists && i < j {
				dp[j][k] = dp[i][j] + 1

				if dp[j][k] > longest {
					longest = dp[j][k]
				}
			}
		}
	}

	if longest >= 3 {
		return longest
	}

	return 0
}

The Go implementation closely mirrors the Python version. A map[int]int is used instead of a Python dictionary for value lookup.

The DP table is represented as a two-dimensional slice initialized with 2.

Go does not have Python's built-in max function for integers, so we manually compare and update longest.

Integer overflow is not an issue because the largest possible value is 10^9, which easily fits inside Go's int type on LeetCode environments.

Worked Examples

Example 1

Input:

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

Initial hash map:

Value Index
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7

Important DP updates:

j k arr[j] arr[k] Needed Previous i New Length
1 2 2 3 1 0 3
2 4 3 5 2 1 4
4 7 5 8 3 2 5

The sequence formed is:

[1, 2, 3, 5, 8]

Final answer:

5

Example 2

Input:

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

Important DP updates:

j k arr[j] arr[k] Needed Previous i Length
3 4 11 12 1 0 3
3 5 11 14 3 1 3
3 6 11 18 7 2 3

No longer sequence can be formed.

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every pair (j, k) is processed once
Space O(n²) The DP table stores results for all index pairs

The algorithm uses two nested loops over the array, producing O(n²) states. Each state performs only constant-time work because the predecessor lookup uses a hash map. The DP table requires O(n²) memory since we store information for every pair of indices.

Test Cases

from typing import List

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)

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

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

        longest = 0

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

                if previous_value in value_to_index:
                    i = value_to_index[previous_value]

                    if i < j:
                        dp[j][k] = dp[i][j] + 1
                        longest = max(longest, dp[j][k])

        return longest if longest >= 3 else 0

solution = Solution()

assert solution.lenLongestFibSubseq([1,2,3,4,5,6,7,8]) == 5
# Standard Fibonacci-like sequence

assert solution.lenLongestFibSubseq([1,3,7,11,12,14,18]) == 3
# Multiple valid length-3 subsequences

assert solution.lenLongestFibSubseq([1,4,10,22]) == 0
# No Fibonacci-like subsequence exists

assert solution.lenLongestFibSubseq([1,2,3]) == 3
# Smallest valid Fibonacci-like sequence

assert solution.lenLongestFibSubseq([1,2,4,8,16]) == 0
# Powers of two cannot form Fibonacci relations

assert solution.lenLongestFibSubseq([2,4,5,6,7,8,11,13,19]) == 5
# Longer subsequence exists in middle of array

assert solution.lenLongestFibSubseq([1,3,4,7,11,18,29]) == 7
# Entire array forms Fibonacci-like sequence

assert solution.lenLongestFibSubseq([1,5,6,11,17,28]) == 6
# Consecutive Fibonacci growth through full array

assert solution.lenLongestFibSubseq([1,10,100,1000]) == 0
# Large gaps prevent valid sequence
Test Why
[1,2,3,4,5,6,7,8] Standard example with long sequence
[1,3,7,11,12,14,18] Multiple small valid subsequences
[1,4,10,22] No valid Fibonacci-like subsequence
[1,2,3] Minimum valid input size
[1,2,4,8,16] Increasing numbers without additive relationships
[2,4,5,6,7,8,11,13,19] Sequence formed from non-adjacent elements
[1,3,4,7,11,18,29] Entire array forms valid sequence
[1,5,6,11,17,28] Tests continuous extension logic
[1,10,100,1000] Large value gaps

Edge Cases

One important edge case occurs when no Fibonacci-like subsequence exists at all. For example:

[1,4,10,22]

A buggy implementation might incorrectly return 2, because every pair initially has DP length 2. However, the problem requires sequences of length at least 3. The implementation handles this by returning 0 whenever the maximum discovered length is less than 3.

Another important edge case is the minimum valid array size:

[1,2,3]

This is the smallest possible Fibonacci-like subsequence. Some implementations accidentally require additional extensions before updating the answer. Our solution correctly identifies the sequence immediately because every valid extension updates the DP table to length 3.

A third critical edge case involves valid values appearing after the current index. Suppose:

arr = [1,3,5,8]

When processing (3,5), the needed predecessor is 2, which does not exist. In other situations, the predecessor value may exist but appear after j, which would violate subsequence ordering. The condition:

if i < j:

ensures we only form subsequences that preserve the original array order.

Another subtle edge case involves large integer values close to 10^9. Since we never build arrays indexed by value, and only use hash maps and arithmetic subtraction, the implementation remains efficient and avoids memory issues even for very large numbers.