Length of Longest Fibonacci Subsequence - Practice Coding Problems

Length of Longest Fibonacci Subsequence - Problem

A sequence x₁, x₂, ..., xₙ is Fibonacci-like if:

n >= 3
xᵢ + xᵢ₊₁ == xᵢ₊₂ for all i + 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 by deleting any number of elements (including none) without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Input & Output

Example 1 — Basic Fibonacci Sequence

$ Input: arr = [1,2,3,4,5,6,7,8]

› Output: 5

💡 Note: The longest Fibonacci-like subsequence is [1,2,3,5,8] with length 5. We have: 1+2=3, 2+3=5, 3+5=8.

Example 2 — No Valid Sequence

$ Input: arr = [1,3,7,11,12,14,18]

› Output: 3

💡 Note: The longest Fibonacci-like subsequence is [1,11,12] where 1+11=12, giving length 3.

Example 3 — Multiple Short Sequences

$ Input: arr = [2,4,7,8,9,10,14,15,18,23,32,50]

› Output: 5

💡 Note: One valid sequence is [2,8,10,18,28] but 28 is not in array. Actually [4,8,12] is not possible. The answer is [2,8,10,18,28] but since 28 doesn't exist, we get [8,10,18] length 3, but there might be [9,14,23] length 3, or [2,7,9] length 3. Let me recalculate: [2,7,9] gives 2+7=9 ✓, but then 7+9=16 which is not in array. Actually [4,9,13] is not in array. Let me find: [8,9,17] - 17 not in array. [9,14,23] gives 9+14=23 ✓, so length 3. But we need length 5. Looking at [2,8,10,18] - we have 2+8=10 ✓, 8+10=18 ✓, 10+18=28 but 28 not in array. So this gives length 4. Let me check [4,9,14] - 4+9=13, not in array. Actually the longest might be [2,8,10,18,28] but since 28 is missing, we get [2,8,10,18] with length 4, or potentially [4,10,14] with 4+10=14 ✓, giving length 3. The result should be 5 for some sequence like [2,8,10,18,28] if all elements were present.

Constraints

3 ≤ arr.length ≤ 1000
1 ≤ arr[i] < arr[i + 1] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Strictly increasing array of positive integers

Find Fibonacci Subsequences

Look for subsequences where each element equals sum of previous two

Return Maximum Length

Return length of longest sequence found, or 0 if none exist

Key Takeaway

🎯 Key Insight: Any two consecutive elements in a Fibonacci sequence uniquely determine all following elements, so we can use DP with pairs as states.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use dynamic programming where each pair of consecutive elements in a Fibonacci sequence determines all subsequent elements. The optimal 2D DP approach achieves O(n²) time by storing sequence lengths ending at each pair and using hash map lookup. Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (2D)	O(n²)	O(n²)	Use DP with pairs as states to avoid recomputing sequences
Hash Map Optimization	O(n²)	O(n)	Use hash map for O(1) lookup instead of linear search
Brute Force - Try All Triplets	O(n³)	O(1)	Check every possible starting pair and extend as far as possible

Dynamic Programming (2D) — Algorithm Steps

Initialize dp[i][j] = 2 for all valid pairs
For each pair (i,j), find previous pair (k,i) where arr[k] + arr[i] = arr[j]
Update dp[i][j] = dp[k][i] + 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

dp[i][j] = 2 for all pairs

Find Previous

For each pair (i,j), find (k,i) that extends it

Update Length

dp[i][j] = dp[k][i] + 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 10007

typedef struct {
    int value;
    int index;
    int used;
} HashEntry;

HashEntry hashTable[HASH_SIZE];

int hash(int key) {
    return abs(key) % HASH_SIZE;
}

void insertHash(int value, int index) {
    int h = hash(value);
    while (hashTable[h].used && hashTable[h].value != value) {
        h = (h + 1) % HASH_SIZE;
    }
    hashTable[h].value = value;
    hashTable[h].index = index;
    hashTable[h].used = 1;
}

int findHash(int value) {
    int h = hash(value);
    while (hashTable[h].used) {
        if (hashTable[h].value == value) {
            return hashTable[h].index;
        }
        h = (h + 1) % HASH_SIZE;
    }
    return -1;
}

int solution(int* arr, int n) {
    if (n < 3) return 0;
    
    // Initialize hash table
    memset(hashTable, 0, sizeof(hashTable));
    
    // Create hash map: value -> index
    for (int i = 0; i < n; i++) {
        insertHash(arr[i], i);
    }
    
    // dp[i][j] = length of Fibonacci sequence ending at indices i and j
    int dp[1000][1000];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 2;
        }
    }
    
    int maxLength = 0;
    
    for (int j = 2; j < n; j++) {
        for (int i = 1; i < j; i++) {
            // Looking for k such that arr[k] + arr[i] = arr[j]
            int target = arr[j] - arr[i];
            int k = findHash(target);
            if (k != -1 && k < i) {  // Valid sequence: k < i < j
                dp[i][j] = dp[k][i] + 1;
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                }
            }
        }
    }
    
    return maxLength >= 3 ? maxLength : 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int arr[1000];
    int n = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && n < 1000) {
            arr[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(arr, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops through all pairs O(n²), with hash lookup O(1) for each pair

⚠ Quadratic Growth

Space Complexity

O(n²)

2D DP table of size n×n plus hash map of size n

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (2D) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler