Length of Longest Fibonacci Subsequence
MedPrompt
A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3xi + xi+1 == xi+2for alli + 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 <= 10001 <= arr[i] < arr[i + 1] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of elements from the array to see if they can be the first two elements of a Fibonacci-like subsequence. For each starting pair, we then greedily extend the subsequence as long as possible.
Algorithm
- Get the length of the array,
n. Ifn < 3, return 0. - Create a
HashSetcallednumSetand add all elements fromarrto it for O(1) average time lookups. - Initialize a variable
maxLengthto 0. - Iterate through the array with an outer loop for index
ifrom 0 ton-1. - Iterate with an inner loop for index
jfromi+1ton-1. - Inside the inner loop, let
a = arr[i]andb = arr[j]. InitializecurrentLength = 2. - Start a
whileloop to extend the sequence. The condition isnumSet.contains(a + b). - Inside the
whileloop:- Calculate
next = a + b. - Increment
currentLength. - Update
atobandbtonextfor the next iteration.
- Calculate
- After the
whileloop, ifcurrentLength > 2, updatemaxLength = max(maxLength, currentLength). - After the loops complete, return
maxLength.
Walkthrough
The core idea is that a Fibonacci-like sequence is determined by its first two elements. If we pick arr[i] and arr[j] as the first two terms, the third term must be arr[i] + arr[j], the fourth must be arr[j] + (arr[i] + arr[j]), and so on.
To efficiently check if the next required number exists in the input array, we first store all elements of arr into a HashSet. This provides average O(1) time complexity for lookups.
We then iterate through all possible pairs (arr[i], arr[j]) with i < j. For each pair, we start a potential Fibonacci-like subsequence of length 2.
We then repeatedly calculate the next expected term and check if it's in our hash set. If it is, we increment our current subsequence length and continue with the next two terms.
We keep track of the maximum length found across all starting pairs. If the longest sequence found has a length less than 3, we return 0 as per the problem description.
import java.util.HashSet;import java.util.Set; class Solution { public int lenLongestFibSubseq(int[] arr) { int n = arr.length; if (n < 3) { return 0; } Set<Integer> numSet = new HashSet<>(); for (int x : arr) { numSet.add(x); } int maxLength = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int a = arr[i]; int b = arr[j]; int currentLength = 2; while (numSet.contains(a + b)) { int next = a + b; a = b; b = next; currentLength++; } if (currentLength > 2) { maxLength = Math.max(maxLength, currentLength); } } } return maxLength; }}Complexity
Time
O(N^2 * log(M)), where N is the number of elements in `arr` and M is the maximum value in `arr`. The O(N^2) comes from the nested loops to pick pairs. The `log(M)` factor comes from the `while` loop, as the values in a Fibonacci-like sequence grow exponentially, so the number of terms until they exceed M is proportional to `log(M)`.
Space
O(N) to store the elements in the `HashSet`.
Trade-offs
Pros
Relatively simple to understand and implement.
Space efficient compared to the DP approach.
Cons
The time complexity is worse than the dynamic programming approach, which can be significant for larger N.
It re-computes the length of the same sub-problems multiple times. For example, the length of the sequence ending in (3, 5) might be calculated when starting with (1, 2) and also when starting with (2, 3).
This approach uses dynamic programming to avoid re-computation. We build a 2D DP table to store the lengths of Fibonacci-like subsequences ending at specific pairs of elements.
Algorithm
- Get the length of the array,
n. Ifn < 3, return 0. - Create a
HashMapindexMapto store each number and its index inarr. - Initialize a 2D array
dp[n][n]to store the lengths. - Initialize a variable
maxLengthto 0. - Iterate
kfrom 1 ton-1. - Iterate
jfrom 0 tok-1. - Calculate
target = arr[k] - arr[j]. - Check if
targetexists inindexMapand iftargetis less thanarr[j]. The second condition ensures that the indexioftargetwill be less thanjbecause the array is strictly increasing. - If the condition is met:
- Get the index
i = indexMap.get(target). - Set
dp[j][k] = dp[i][j] + 1.
- Get the index
- Else:
- Set
dp[j][k] = 2.
- Set
- Update
maxLength = max(maxLength, dp[j][k]). - After the loops, if
maxLengthis greater than 2, returnmaxLength. Otherwise, return 0.
Walkthrough
Let dp[j][k] be the length of the longest Fibonacci-like subsequence that ends with arr[j] and arr[k], where j < k.
The base case for any pair (arr[j], arr[k]) is a length of 2.
To compute dp[j][k], we need to find the previous element in the sequence. Let this element be arr[i]. The relationship must be arr[i] + arr[j] = arr[k]. This means arr[i] = arr[k] - arr[j].
We can find arr[i] efficiently if we first store the array's values and their indices in a HashMap.
If we find an index i such that arr[i] = arr[k] - arr[j] and i < j, it means we can extend the subsequence ending at (arr[i], arr[j]). The new length will be dp[i][j] + 1.
So, the transition is: dp[j][k] = dp[i][j] + 1. If no such i exists, dp[j][k] represents a sequence of just two elements, so its length is 2.
We iterate through all possible ending pairs (arr[j], arr[k]) and fill the dp table. The maximum value found in the dp table will be our answer. If the maximum length is 2, it means no Fibonacci-like subsequence of length 3 or more exists, so we return 0.
import java.util.HashMap;import java.util.Map; class Solution { public int lenLongestFibSubseq(int[] arr) { int n = arr.length; if (n < 3) { return 0; } Map<Integer, Integer> indexMap = new HashMap<>(); for (int i = 0; i < n; i++) { indexMap.put(arr[i], i); } int[][] dp = new int[n][n]; int maxLength = 0; for (int k = 1; k < n; k++) { for (int j = 0; j < k; j++) { int target = arr[k] - arr[j]; // We need target < arr[j] because arr is strictly increasing. // If target >= arr[j], then its index i would be >= j. if (target < arr[j] && indexMap.containsKey(target)) { int i = indexMap.get(target); // The length of sequence ending at j, k is one more than // the length of sequence ending at i, j. dp[j][k] = dp[i][j] + 1; } else { // This is the base case, a sequence of length 2. dp[j][k] = 2; } maxLength = Math.max(maxLength, dp[j][k]); } } return maxLength > 2 ? maxLength : 0; }}Complexity
Time
O(N^2). The nested loops iterate through approximately N^2/2 pairs of `(j, k)`. The operations inside the loop (map lookup, arithmetic) are O(1) on average.
Space
O(N^2). We use an O(N^2) DP table to store the intermediate results and an O(N) map for value-to-index lookups. The dominant factor is the DP table.
Trade-offs
Pros
More time-efficient than the brute-force approach.
Avoids redundant calculations by storing results in the DP table.
Cons
Requires O(N^2) space, which could be an issue for very large N (though N <= 1000 is acceptable in this problem).
Solutions
Solution
class Solution {public int lenLongestFibSubseq(int[] arr) { int n = arr.length; Map<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < n; ++i) { mp.put(arr[i], i); } int[][] dp = new int[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { dp[j][i] = 2; } } int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int d = arr[i] - arr[j]; if (mp.containsKey(d)) { int k = mp.get(d); if (k < j) { dp[j][i] = Math.max(dp[j][i], dp[k][j] + 1); ans = Math.max(ans, dp[j][i]); } } } } return ans; }}/** * @param {number[]} arr * @return {number} */ var lenLongestFibSubseq = function (arr) { const mp = new Map(); const n = arr.length; const dp = new Array(n).fill(0).map(() => new Array(n).fill(0)); for (let i = 0; i < n; ++i) { mp.set(arr[i], i); for (let j = 0; j < i; ++j) { dp[j][i] = 2; } } let ans = 0; for (let i = 0; i < n; ++i) { for (let j = 0; j < i; ++j) { const d = arr[i] - arr[j]; if (mp.has(d)) { const k = mp.get(d); if (k < j) { dp[j][i] = Math.max(dp[j][i], dp[k][j] + 1); ans = Math.max(ans, dp[j][i]); } } } } return ans; };class Solution {public: int lenLongestFibSubseq(vector<int> &arr) { unordered_map<int, int> mp; int n = arr.size(); for (int i = 0; i < n; ++i) mp[arr[i]] = i; vector<vector<int>> dp(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) dp[j][i] = 2; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int d = arr[i] - arr[j]; if (mp.count(d)) { int k = mp[d]; if (k < j) { dp[j][i] = max(dp[j][i], dp[k][j] + 1); ans = max(ans, dp[j][i]); } } } } return ans; }};class Solution: def lenLongestFibSubseq(self, arr: List[int]) -> int: mp = {v: i for i, v in enumerate(arr)} n = len(arr) dp = [[0] * n for _ in range(n)] for i in range(n): for j in range(i): dp[j][i] = 2 ans = 0 for i in range(n): for j in range(i): d = arr[i] - arr[j] if d in mp and (k: = mp[d]) < j: dp[j][i] = max(dp[j][i], dp[k][j] + 1) ans = max(ans, dp[j][i]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.