Skip to main content
Talentd

Length of Longest Fibonacci Subsequence - Solution & Explanation

MediumArrayHash TableDynamic Programming16 min readAsked at: Amazon, Microsoft, Goldman Sachs +4
Practice this problem

Problem Statement

A sequence x1, x2, ..., xn is Fibonacci-like if:

  • n >= 3
  • xi + xi+1 == xi+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] <= 109

Approach Overview

Problem Overview: You are given a strictly increasing integer array. The task is to find the length of the longest subsequence that forms a Fibonacci-like sequence where a + b = c for consecutive elements. The subsequence does not need to be contiguous, but the order must remain the same.

Approach 1: Two Pointers with HashSet (O(n^2 log M) time, O(n) space)

This approach treats every pair (arr[i], arr[j]) as the potential start of a Fibonacci-like sequence. Store all numbers in a hash set for constant-time membership checks. For each pair, repeatedly compute the next value next = a + b and check if it exists in the set. If it does, extend the sequence by shifting the two pointers forward (a = b, b = next) and continue. The key insight is that Fibonacci sequences are uniquely determined by their first two values, so enumerating pairs guarantees coverage. Time complexity is roughly O(n^2 log M) where M is the maximum value (sequence length grows logarithmically), and space complexity is O(n) for the hash set. This approach is intuitive and works well when you want a direct simulation of the Fibonacci growth using fast lookups from a hash table.

Approach 2: Dynamic Programming with Index Map (O(n^2) time, O(n^2) space)

The optimal strategy uses dynamic programming combined with a value-to-index map. Create a map from array value to its index so you can quickly locate potential previous numbers. Define dp[j][i] as the length of the Fibonacci-like subsequence ending with arr[j] and arr[i]. For each pair (j, i), compute the required previous value prev = arr[i] - arr[j]. If prev exists and its index k is less than j, then extend the sequence: dp[j][i] = dp[k][j] + 1. Otherwise initialize the pair length as 2. Track the global maximum while iterating through all pairs. This method systematically builds longer sequences from shorter ones and avoids repeated recomputation. Time complexity is O(n^2) and space complexity is also O(n^2) for the DP table.

Recommended for interviews: The dynamic programming approach is typically what interviewers expect. It demonstrates strong understanding of subsequence state transitions and efficient use of a array index map. The HashSet simulation approach is easier to reason about and often used as an initial idea, but the DP solution scales better and shows deeper algorithmic thinking.

Approach 1: Approach 1: Two Pointers with HashSet

This approach leverages a two-pointer mechanism combined with a HashSet to efficiently find Fibonacci-like sequences. Given the strictly increasing nature of the array, we can use a set for quick lookup to determine if the sum of two numbers exists in the array, thus confirming a Fibonacci-like sequence.

The function initializes a set s containing all elements of the array for constant-time lookups. It iterates through each pair of elements (arr[i], arr[j]) using two loops, treating them as the first two elements of a potential Fibonacci subsequence. While the sum of the last two elements exists in the set, it increases the subsequence length. If a valid Fibonacci-like sequence of length at least 3 is found, it updates max_len.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^2 * logM), where n is the length of the array and M is the maximum value in the array (for set operations).
Space Complexity: O(n) due to the HashSet used for lookups.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

In this approach, dynamic programming is used to maintain a table where dp[i][j] denotes the length of the Fibonacci-like subsequence ending with arr[i] and arr[j]. Whenever a valid predecessor pair (arr[k], arr[i]) is found such that arr[k] + arr[i] = arr[j], the table is updated, calculating a maximal subsequence length.

This Java solution is based on dynamic programming with a HashMap to efficiently explore and track subsequences. It first constructs a map to identify indices by value in constant time. For each pair (j, k), if a valid predecessor exists, the dp table is updated, storing the sequence length.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n^2), where n is the length of the array, since every pair is compared.
Space Complexity: O(n^2), as a map stores the length for each pair.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the length of the longest Fibonacci-like subsequence, with arr[i] as the last element and arr[j] as the second to last element. Initially, for any i \in [0, n) and j \in [0, i), we have f[i][j] = 2. All other elements are 0.

We use a hash table d to record the indices of each element in the array arr.

Then, we can enumerate arr[i] and arr[j], where i \in [2, n) and j \in [1, i). Suppose the currently enumerated elements are arr[i] and arr[j], we can obtain arr[i] - arr[j], denoted as t. If t is in the array arr, and the index k of t satisfies k < j, then we can get a Fibonacci-like subsequence with arr[j] and arr[i] as the last two elements, and its length is f[i][j] = max(f[i][j], f[j][k] + 1). We can continuously update the value of f[i][j] in this way, and then update the answer.

After the enumeration ends, return the answer.

The time complexity is O(n^2), and the space complexity is O(n^2), where n is the length of the array arr.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Two Pointers with HashSet

Time Complexity: O(n^2 * logM), where n is the length of the array and M is the maximum value in the array (for set operations).
Space Complexity: O(n) due to the HashSet used for lookups.

Approach 2: Dynamic Programming

Time Complexity: O(n^2), where n is the length of the array, since every pair is compared.
Space Complexity: O(n^2), as a map stores the length for each pair.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointers with HashSetO(n^2 log M)O(n)When you want a straightforward simulation of Fibonacci growth with constant-time value lookups
Dynamic Programming with Index MapO(n^2)O(n^2)Best general solution; preferred in interviews for building subsequences efficiently

Video Solution

Length of Longest Fibonacci Subsequence - Leetcode 873 - Python • NeetCodeIO • 13,380 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Length of Longest Fibonacci Subsequence easy or hard?
Length of Longest Fibonacci Subsequence is rated Medium on LeetCode with an acceptance rate around 57%. The challenge comes from recognizing the DP relationship between three elements and efficiently finding the previous value using a hash map.
Length of Longest Fibonacci Subsequence Python/Java solution
Python and Java implementations typically use a hash map for value-to-index lookup and a 2D DP table to store sequence lengths. The algorithm iterates over pairs of indices and updates dp[j][i] = dp[k][j] + 1 when a valid previous value exists. This achieves O(n^2) time complexity.
How to solve Length of Longest Fibonacci Subsequence in O(n)?
An O(n) solution is not possible for this problem because the algorithm must examine pairs of elements to determine valid Fibonacci-like progressions. The best known approach is O(n^2) using dynamic programming and a hash map to locate the required previous element efficiently.
What is the best approach for Length of Longest Fibonacci Subsequence?
Dynamic programming with a value-to-index hash map is the most efficient and commonly expected solution. It computes subsequence lengths using a DP table where dp[j][i] represents the Fibonacci-like sequence ending at indices j and i. This approach runs in O(n^2) time with O(n^2) space.
Is Length of Longest Fibonacci Subsequence asked at Google/Amazon/Meta?
Fibonacci-style subsequence and dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of subsequences, hash maps, and DP state transitions, which are common interview themes.
What data structure is used in Length of Longest Fibonacci Subsequence?
The main data structures are arrays for storing DP states and a hash map that maps each number to its index. The HashSet approach also uses a set to quickly check whether the next Fibonacci value exists in the array.
What is the time complexity of Length of Longest Fibonacci Subsequence?
The optimal dynamic programming solution runs in O(n^2) time because it evaluates every pair of indices in the array. Space complexity is O(n^2) for the DP table. A simpler HashSet simulation approach also exists and runs in roughly O(n^2 log M) time with O(n) space.

Ready to solve this problem?

Practice Length of Longest Fibonacci Subsequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Fibonacci Number