Length of Longest Fibonacci Subsequence

Medium
1477.

Length of Longest Fibonacci Subsequence

Length of Longest Fibonacci Subsequence is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Bloomberg interviews.

A sequence x1, x2, ..., xk is Fibonacci-like when k >= 3 and every term from the third on is the sum of the two before it: x(i) + x(i+1) == x(i+2).

arr is strictly increasing. Return the length of the longest Fibonacci-like subsequence of arr (keep elements in their original order, deleting any others), or 0 if there is none.

Example 1

Input
arr = [1,2,3,4,5,6,7,8]
Output
5
Explanation
`[1,2,3,5,8]`.

Example 2

Input
arr = [1,3,7,11,12,14,18]
Output
3
Explanation
For example `[1,11,12]` or `[7,11,18]`.

Example 3

Input
arr = [2,4,7]
Output
0

Constraints

  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Length of Longest Fibonacci Subsequence — Problem & Solution

Length of Longest Fibonacci Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Length of Longest Fibonacci Subsequence is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Bloomberg interviews.

Problem statement

A sequence x1, x2, ..., xk is Fibonacci-like when k >= 3 and every term from the third on is the sum of the two before it: x(i) + x(i+1) == x(i+2).

arr is strictly increasing. Return the length of the longest Fibonacci-like subsequence of arr (keep elements in their original order, deleting any others), or 0 if there is none.

Example 1

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: `[1,2,3,5,8]`.

Example 2

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: For example `[1,11,12]` or `[7,11,18]`.

Example 3

Input: arr = [2,4,7]
Output: 0

Constraints

  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9

Hints for Length of Longest Fibonacci Subsequence

  1. Hint 1

    A Fibonacci-like sequence is fixed once you know its first two terms — or its last two.

  2. Hint 2

    Let dp[j][k] be the longest such sequence ending with arr[j], arr[k] (j < k).

  3. Hint 3

    The term before arr[j] must be arr[k] - arr[j]; if it exists at index i < j (look it up in a hash map), then dp[j][k] = dp[i][j] + 1.

How to solve Length of Longest Fibonacci Subsequence

Index states by the last two elements. Because arr is strictly increasing, the element preceding the pair (arr[j], arr[k]) is forced to be arr[k] - arr[j], and it must be smaller than arr[j].

Approach

  1. Map every value to its index.
  2. For every pair j < k, let p = arr[k] - arr[j]. If p < arr[j] and p is in the map at index i, set dp[j][k] = dp[i][j] + 1, where a missing dp[i][j] counts as 2.
  3. Track the largest dp value produced; it is at least 3 whenever any extension happened.
  4. Return that maximum, or 0 if no pair was ever extended.

Why it works

Every Fibonacci-like subsequence ending in (arr[j], arr[k]) has a unique predecessor term, so the longest one ending in that pair is one longer than the longest ending in (arr[i], arr[j]). Requiring p < arr[j] keeps the indices in order (the array is increasing), so the subsequence order is respected.

Complexity

  • Time — O(n²)
  • Space — O(n²)

Pitfalls

  • Return 0, not 2, when no three elements form a Fibonacci-like triple.
  • Without the p < arr[j] check you could use an element that comes after arr[j].
  • Values reach 10^9 — compute the difference arr[k] - arr[j], never the sum of two values in 32-bit arithmetic.

Reference solution

Python

from typing import List

def lenLongestFibSubseq(arr: List[int]) -> int:
    n = len(arr)
    pos = {v: i for i, v in enumerate(arr)}
    dp = [[2] * n for _ in range(n)]
    best = 0
    for k in range(n):
        for j in range(k):
            p = arr[k] - arr[j]
            if p < arr[j] and p in pos:
                i = pos[p]
                dp[j][k] = dp[i][j] + 1
                if dp[j][k] > best:
                    best = dp[j][k]
    return best

Java

public static int lenLongestFibSubseq(int[] arr) {
    int n = arr.length;
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < n; i++) pos.put(arr[i], i);
    int[][] dp = new int[n][n];
    int best = 0;
    for (int k = 0; k < n; k++) {
        for (int j = 0; j < k; j++) {
            dp[j][k] = 2;
            int p = arr[k] - arr[j];
            if (p < arr[j]) {
                Integer i = pos.get(p);
                if (i != null) {
                    dp[j][k] = dp[i][j] + 1;
                    if (dp[j][k] > best) best = dp[j][k];
                }
            }
        }
    }
    return best;
}

C++

int lenLongestFibSubseq(vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> pos;
    for (int i = 0; i < n; i++) pos[arr[i]] = i;
    vector<vector<int>> dp(n, vector<int>(n, 2));
    int best = 0;
    for (int k = 0; k < n; k++) {
        for (int j = 0; j < k; j++) {
            int p = arr[k] - arr[j];
            if (p < arr[j]) {
                auto it = pos.find(p);
                if (it != pos.end()) {
                    dp[j][k] = dp[it->second][j] + 1;
                    best = max(best, dp[j][k]);
                }
            }
        }
    }
    return best;
}

JavaScript

var lenLongestFibSubseq = function(arr) {
    var n = arr.length;
    var pos = new Map();
    for (var i = 0; i < n; i++) pos.set(arr[i], i);
    var dp = [];
    for (i = 0; i < n; i++) dp.push(new Array(n).fill(2));
    var best = 0;
    for (var k = 0; k < n; k++) {
        for (var j = 0; j < k; j++) {
            var p = arr[k] - arr[j];
            if (p < arr[j] && pos.has(p)) {
                dp[j][k] = dp[pos.get(p)][j] + 1;
                if (dp[j][k] > best) best = dp[j][k];
            }
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets