Solution to LeetCode 873 - Length of Longest Fibonacci Subsequence

Problem 873

Abstract / Summary

Find the length of the longest subsequence of a given list that forms a Fibonacci sequence.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0873.py

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        result = 0
        lookup = set(arr)

        seen   = set() # basic cache: if (a, b) where already visited, then a longer chain exists

        # start with every possible pair a, b (where a < b)
        for i, a in enumerate(arr):
            for b in arr[i + 1 : ]:
                length = 2

                # keep going while one + two exists
                one = a
                two = b
                while one + two in lookup and ( one, two ) not in seen:
                    seen.add(( one, two ))
                    length  += 1
                    result   = max(result, length)
                    # prepare next step
                    one, two = two, one + two

        return result

Difficulty

This problem is ranked as

easy medium hard

and has an acceptance rate of about 57% (300k+ submissions).

Typical patterns to solve this problem:

Array
Dynamic Programming
Hash Table

I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the length of the longest Fibonacci-like subsequence that can be formed from a given list of integers. It iterates over every ordered pair of distinct elements, attempts to extend a potential sequence by repeatedly checking whether the sum of the last two numbers exists in the original array, and records the maximum length found. A cache of already-processed pairs prevents redundant work, and a hash-set enables constant-time membership tests.

Key Steps

Preparing auxiliary data structures

The algorithm begins by creating a hash-set containing all values from the input array. This set is used for fast existence checks while extending a candidate sequence.

lookup = set(arr)

A second set, seen, stores ordered pairs that have already been examined. By remembering which (a, b) pairs have been processed, the algorithm avoids re-evaluating the same continuation path later in the execution.

seen = set()

Enumerating starting pairs

The outer loops select every possible ordered pair (a, b) where a precedes b in the array. The index of a is obtained from enumerate, and the slice arr[i + 1 :] yields all subsequent elements for b.

for i, a in enumerate(arr):
    for b in arr[i + 1:]:
        length = 2

The variable length is initialized to 2 because any pair of numbers constitutes the minimal Fibonacci-like sequence.

Extending a candidate sequence

Inside the nested loops, a while loop attempts to grow the current sequence. It checks two conditions: the sum of the last two numbers must be present in lookup, and the ordered pair (one, two) must not have been seen before. When both hold, the pair is added to seen, the length counter is incremented, and the global maximum result is updated.

one = a
two = b
while one + two in lookup and (one, two) not in seen:
    seen.add((one, two))
    length += 1
    result = max(result, length)
    one, two = two, one + two

The assignment one, two = two, one + two advances the pair to the next two numbers in the prospective Fibonacci chain.

Returning the final answer

After all pairs have been examined, the function returns the largest length discovered. If no Fibonacci-like subsequence longer than two elements exists, result remains 0.

return result

Edge Cases Handled

When the input array contains fewer than three elements, the nested loops still execute but the inner while condition never becomes true, leaving result at its initial value of 0. This correctly reflects the absence of any valid Fibonacci-like subsequence.

If the array includes duplicate values, the lookup set automatically collapses them, ensuring that membership checks are based on distinct numbers only. The algorithm’s pair enumeration respects the original ordering, so duplicate entries are still considered as separate starting points when they appear at different indices.

When a potential sequence reaches a pair that has already been recorded in seen, the while loop terminates early. This prevents infinite loops in cases where the same pair could otherwise be revisited indefinitely, such as when the array contains a repeating pattern that would otherwise cause the extension logic to cycle.

If the sum of the last two numbers is not present in lookup, the while loop stops, correctly terminating the current candidate sequence. This situation occurs frequently for random or sparse input arrays and is handled without error.

Performance Optimizations

The use of a hash-set for lookup provides constant-time checks for the existence of the next Fibonacci number, which is crucial for keeping the inner loop efficient. By storing previously processed ordered pairs in the seen set, the algorithm eliminates repeated work for the same starting pair, reducing the total number of iterations required to explore all possible sequences. The early exit from the while loop when a pair is found in seen further curtails unnecessary computation, especially in inputs where many overlapping subsequences share common prefixes. These design choices collectively ensure that the algorithm scales well with the size of the input array.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there is a big collection box filled with number cards lined up in order from smallest to biggest. The goal is to find a secret sequence of numbers hiding inside that box. A secret sequence works like a family where each new number is made by adding the two numbers that came right before it. For example, if you have two and three, the next number must be five because two plus three makes five. If you have three and five, the next one must be eight because three plus five makes eight.

The computer starts by picking any two cards from the box to see if they can begin a secret chain. It keeps a little list of all the numbers in the box so it can check very quickly if the next required number is inside. After picking the first two numbers, the computer calculates what the third number should be. If that third number is hiding in the box, the chain grows longer. The computer keeps adding these numbers together to make new ones and checking if they also live in the box.

Every time it finds a new number for the chain, it records that the chain is getting longer. If it finds a long chain, it remembers how many cards are in it. It does this for every pair of cards it can possibly pick. When it is finished looking at every combination, it knows the length of the longest secret chain found during the whole hunt.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

n = 27 | median = 7 | μ = 6.48 | σ = 1.40

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

factorial: up to 10 elements
exponential: up to 20 elements
polynomial: a few thousand elements
loglinear: up to 100,000 elements
linear: a few million elements
logarithmic: a billion elements
constant: practically unlimited

generated automatically

Videos

These are a few popular YouTube videos for this problem:

NeetCodeIO 25 mins

Length of Longest Fibonacci Subsequence - Leetcode 873 - Python

codestorywithMIK 49 mins

Length of Longest Fibonacci Subsequence | Recursion Memo | Bottom Up |Leetcode 873| codestorywithMIK

ShashCode 16 mins

873. Length of Longest Fibonacci Subsequence | leetcode daily challenge | dsa | faang | shashcode

Algorithms Casts 37 mins

Length of Longest Fibonacci Subsequence (Leetcode 873)

Programming Live with Larry 15 mins

Daily Leetcode #1794: Feb 27, 2025 - 873. Length of Longest Fibonacci Subsequence

Code Harmony 31 mins

LeetCode 873. Length of Longest Fibonacci Subsequence | Dynamic Programming | Adobe

Tim Huang 7 mins