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).
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; }}Video 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.