Length of Longest Fibonacci Subsequence: Hash Set + DP

Given a strictly increasing array of positive integers, find the length of the longest subsequence that is Fibonacci-like. A sequence is Fibonacci-like if it has at least three elements and every consecutive triple satisfies arr[i] + arr[j] = arr[k].

This is LeetCode 873: Length of Longest Fibonacci Subsequence. It blends hash set lookups with a dynamic programming twist, and it is a great problem for building intuition about two-element DP states.

Why this problem matters

Most DP problems define their state around a single index: "the best answer ending at position i." Fibonacci subsequence problems are different. You need to know the last two elements of the chain to decide what comes next, because the next value is their sum. That makes the state two-dimensional: dp[j][k] represents the length of the longest Fibonacci-like subsequence that ends with arr[j] followed by arr[k].

This "two-element state" pattern shows up whenever the transition depends on a pair of previous values, not just one. Once you internalize it here, you will recognize it in problems involving arithmetic subsequences, geometric progressions, and other sequence-matching tasks.

The approach

1. Build a value-to-index map. Store every element in a hash map (or set) so you can check in O(1) whether a needed value exists in the array, and where it sits.

2. Enumerate all pairs (j, k) where j < k. For each pair, compute target = arr[k] - arr[j]. If target exists in the array at an index i < j, then there is a Fibonacci triple arr[i], arr[j], arr[k].

3. Use DP to extend chains. When you find a valid triple, set dp[(j, k)] = dp[(i, j)] + 1. If no prior chain ends at (i, j), the chain length starts at 3 (the minimum for a Fibonacci-like sequence).

4. Track the global maximum. After processing all pairs, the answer is the longest chain found. If no chain reaches length 3, return 0.

The solution

def len_longest_fib_subseq(arr):
    index = {x: i for i, x in enumerate(arr)}
    dp = {}
    best = 0
    n = len(arr)

    for k in range(n):
        for j in range(k):
            target = arr[k] - arr[j]
            if target < arr[j] and target in index:
                i = index[target]
                dp[(j, k)] = dp.get((i, j), 2) + 1
                best = max(best, dp[(j, k)])

    return best if best >= 3 else 0

Visual walkthrough

Here is the algorithm running on arr = [1, 2, 3, 4, 5, 6, 7, 8]. For each pair, we check whether the difference exists earlier in the array, and if so, we extend the chain.

Complexity analysis

Time: We iterate over all O(n^2) pairs (j, k). For each pair, the hash map lookup and DP update are both O(1). So total work is O(n^2).

Space: The dp dictionary can hold at most O(n^2) entries (one per pair). The index map uses O(n) space. Overall: O(n^2).

Building blocks

This problem is built on two reusable patterns.

The first is hash set membership testing. Instead of scanning the array to check if a value exists, you precompute a set or map in O(n) and answer lookups in O(1). This is the same foundation behind Two Sum, where you check whether target - num exists in the map. Here, you check whether arr[k] - arr[j] exists. The idea is identical: precompute, then probe.

The second is two-element DP state. Standard subsequence problems like Longest Increasing Subsequence track dp[i], the best answer ending at index i. This problem requires dp[j][k], the best answer ending at the pair (arr[j], arr[k]). You need both values because the Fibonacci rule depends on the sum of the last two elements. Whenever a recurrence references two prior positions instead of one, you need a two-dimensional state.

Edge cases to watch for

• No valid subsequence: If no three elements satisfy the Fibonacci property, return 0 (not 2). The problem requires length 3 or more.
• Minimum array size: With fewer than 3 elements, no Fibonacci-like subsequence can exist. Return 0.
• All elements form one long chain: For example, [1, 1, 2, 3, 5, 8, 13]. Wait, the array must be strictly increasing, so duplicate values cannot appear. With [1, 2, 3, 5, 8, 13], the entire array is the answer.
• Large values with no matches: The array can have values up to 10^9. Hash map lookups handle this fine, but be aware that arr[k] - arr[j] must be strictly less than arr[j] to be a valid predecessor.
• Multiple chains of equal length: The problem asks only for the length, not the actual subsequence. You do not need to reconstruct the chain.

From understanding to recall

You have just walked through the full solution for finding the longest Fibonacci-like subsequence. The core insight is that Fibonacci chains need a two-element state because the next value depends on the sum of the last two. Combined with a hash map for O(1) existence checks, this gives you an O(n^2) solution.

Understanding this right now is not the same as being able to write it from scratch in an interview. The two-element DP state, the hash map precomputation, and the chain-extension logic all need to become automatic. Spaced repetition is the most efficient way to get there. Revisit this problem at increasing intervals, write the solution from memory each time, and the pattern will stick.

The hash-set-plus-DP combination is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually beats random grinding every time.

Related posts

• Longest Increasing Subsequence - Classic single-index DP on subsequences, the simpler cousin of this problem
• Two Sum - The foundational hash map complement lookup pattern used here for existence checks
• Longest Common Subsequence - Another two-dimensional DP on sequences, with a different recurrence structure