Length of Longest Fibonacci Subsequence solution and explanation
Google
9 more videos on this problem
Length of Longest Fibonacci Subsequence - Leetcode 873 - PythonNeetCodeIO · 24:28 · 13K views
Length of Longest Fibonacci Subsequence | Recursion Memo | Bottom Up |Leetcode 873| codestorywithMIKcodestorywithMIK · 48:26 · 11K views
leetcode 873 Length of Longest Fibonacci SubsequenceCodebix · 16:24 · 8K views
Length of Longest Fibonacci Subsequence | Leetcode 873Techdose · 34:36 · 3K views
873. Length of Longest Fibonacci Subsequence | DP & Two Pointers | 2 ApproachesAryan Mittal · 19:18 · 3K views
873. Length of Longest Fibonacci Subsequence | leetcode daily challenge | dsa | faang | shashcodeShashCode · 15:36 · 2K views
873. Length of Longest Fibonacci Subsequence (Leetcode Medium)Programming Live with Larry · 8:45 · 2K views
Length of Longest Fibonacci Subsequence (Leetcode 873)Algorithms Casts · 36:52 · 1K views
🚀Length of Longest Fibonacci Subsequence | LeetCode 873 | Java | DP & Two Pointers | DSA for FAANGRAHUL VIJAYAN · 13:06 · 681 views
Live Coding Leetcode 873: Length of Longest Fibonacci SubsequenceCS Live Coding · 41:47 · 596 views
The problem
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
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.
def lenLongestFibSubseq(arr):
s = set(arr)
max_len = 0
n = len(arr)
for i in range(n-1):
for j in range(i+1, n):
x, y = arr[i], arr[j]
length = 2
while x + y in s:
x, y = y, x + y
length += 1
max_len = max(max_len, length)
return max_len if max_len >= 3 else 0function lenLongestFibSubseq(arr) {
const s = new Set(arr);
let maxLen = 0;
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let x = arr[i], y = arr[j];
let length = 2;
while (s.has(x + y)) {
const temp = x + y;
x = y;
y = temp;
length++;
}
maxLen = Math.max(maxLen, length);
}
}
return maxLen >= 3 ? maxLen : 0;
}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.
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: 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.
import java.util.HashMap;
public class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
HashMap<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < n; i++) {
index.put(arr[i], i);
}
HashMap<String, Integer> dp = new HashMap<>();
int maxLen = 0;
for (int k = 0; k < n; k++) {
for (int j = 0; j < k; j++) {
int i = index.getOrDefault(arr[k] - arr[j], -1);
if (i >= 0 && i < j) {
int cand = dp.getOrDefault(i + "," + j, 2) + 1;
dp.put(j + "," + k, cand);
maxLen = Math.max(maxLen, cand);
}
}
}
return maxLen >= 3 ? maxLen : 0;
}
}using System;
using System.Collections.Generic;
public class Solution {
public int LenLongestFibSubseq(int[] arr) {
int n = arr.Length;
var index = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
index[arr[i]] = i;
}
var dp = new Dictionary<(int, int), int>();
int maxLen = 0;
for (int k = 0; k < n; k++) {
for (int j = 0; j < k; j++) {
if (index.TryGetValue(arr[k] - arr[j], out int i) && i < j) {
var cand = dp.TryGetValue((i, j), out int val) ? val : 2;
cand++;
dp[(j, k)] = cand;
maxLen = Math.Max(maxLen, cand);
}
}
}
return maxLen >= 3 ? maxLen : 0;
}
}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.
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.
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
int f[n][n];
memset(f, 0, sizeof(f));
unordered_map<int, int> d;
for (int i = 0; i < n; ++i) {
d[arr[i]] = i;
for (int j = 0; j < i; ++j) {
f[i][j] = 2;
}
}
int ans = 0;
for (int i = 2; i < n; ++i) {
for (int j = 1; j < i; ++j) {
int t = arr[i] - arr[j];
auto it = d.find(t);
if (it != d.end() && it->second < j) {
int k = it->second;
f[i][j] = max(f[i][j], f[j][k] + 1);
ans = max(ans, f[i][j]);
}
}
}
return ans;
}
};function lenLongestFibSubseq(arr: number[]): number {
const n = arr.length;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
const d: Map<number, number> = new Map();
for (let i = 0; i < n; ++i) {
d.set(arr[i], i);
for (let j = 0; j < i; ++j) {
f[i][j] = 2;
}
}
let ans = 0;
for (let i = 2; i < n; ++i) {
for (let j = 1; j < i; ++j) {
const t = arr[i] - arr[j];
const k = d.get(t);
if (k !== undefined && k < j) {
f[i][j] = Math.max(f[i][j], f[j][k] + 1);
ans = Math.max(ans, f[i][j]);
}
}
}
return ans;
}func lenLongestFibSubseq(arr []int) (ans int) {
n := len(arr)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
d := make(map[int]int)
for i, x := range arr {
d[x] = i
for j := 0; j < i; j++ {
f[i][j] = 2
}
}
for i := 2; i < n; i++ {
for j := 1; j < i; j++ {
t := arr[i] - arr[j]
if k, ok := d[t]; ok && k < j {
f[i][j] = max(f[i][j], f[j][k]+1)
ans = max(ans, f[i][j])
}
}
}
return
}use std::collections::HashMap;
impl Solution {
pub fn len_longest_fib_subseq(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut f = vec![vec![0; n]; n];
let mut d = HashMap::new();
for i in 0..n {
d.insert(arr[i], i);
for j in 0..i {
f[i][j] = 2;
}
}
let mut ans = 0;
for i in 2..n {
for j in 1..i {
let t = arr[i] - arr[j];
if let Some(&k) = d.get(&t) {
if k < j {
f[i][j] = f[i][j].max(f[j][k] + 1);
ans = ans.max(f[i][j]);
}
}
}
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.