A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3xi + xi+1 == xi+2 for all i + 2 <= nGiven 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 <= 10001 <= arr[i] < arr[i + 1] <= 109Problem 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.
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.
Python
JavaScript
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| 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). |
| Approach 2: Dynamic Programming | Time Complexity: O(n^2), where n is the length of the array, since every pair is compared. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers with HashSet | O(n^2 log M) | O(n) | When you want a straightforward simulation of Fibonacci growth with constant-time value lookups |
| Dynamic Programming with Index Map | O(n^2) | O(n^2) | Best general solution; preferred in interviews for building subsequences efficiently |
Length of Longest Fibonacci Subsequence - Leetcode 873 - Python • NeetCodeIO • 13,108 views views
Watch 9 more video solutions →Practice Length of Longest Fibonacci Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor