Watch 10 video solutions for Length of Longest Fibonacci Subsequence, a medium level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by NeetCodeIO has 13,108 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |