How do you solve Length of Longest Fibonacci Subsequence?

Construct a value-to-index map to allow constant-time lookup of any number's index. Initialize a DP table where dp[i][j] represents the length of the longest Fibonacci-like subsequence ending with arr[i] and arr[j], with all entries starting at 2 since any pair forms a subsequence of length two. For each pair (i, j), compute prev = arr[j] - arr[i]. If prev exists in the array at index k < i, then extend the subsequence by setting dp[i][j] = dp[k][i] + 1 and update the maximum length found.

What pattern does Length of Longest Fibonacci Subsequence use?

The Pattern: Dynamic Programming (Pair-State Tracking) The Heuristic: When a sequence's validity depends on the previous two elements, represent the state using a pair of indices. Store the best sequence ending with each pair and extend it by locating the element that must precede the pair using a hash map.

Length of Longest Fibonacci Subsequence

Q: What is the time complexity of Length of Longest Fibonacci Subsequence?

O(n^2). The algorithm iterates over all pairs (i, j) in the array, which is O(n^2). Each lookup in the hash map is O(1), so total time is O(n^2).

Q: What pattern does Length of Longest Fibonacci Subsequence use?

The Pattern: Dynamic Programming (Pair-State Tracking) The Heuristic: When a sequence's validity depends on the previous two elements, represent the state using a pair of indices. Store the best sequence ending with each pair and extend it by locating the element that must precede the pair using a hash map.

Problem

Given a strictly increasing array arr of positive integers, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

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

Example

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

Output: 5

The longest Fibonacci-like subsequence is [1,2,3,5,8]. The algorithm first maps each value to its index for constant-time lookup. It then tracks subsequences using dp[i][j], which represents the length of a Fibonacci-like sequence ending with arr[i] and arr[j]. For each pair (i, j), it determines whether a previous number arr[k] exists such that arr[k] + arr[i] = arr[j]. If so, the subsequence ending at (k, i) can be extended to include arr[j], increasing its length.

Approach

Straightforward Solution

A brute-force approach would try all subsequences and check if they are Fibonacci-like, which is exponential and infeasible for large arrays.

Core Observation

A Fibonacci-like sequence is determined by its last two elements. If arr[i] and arr[j] are the final two numbers of such a sequence, then the previous number must satisfy arr[k] + arr[i] = arr[j]. Rearranging gives arr[k] = arr[j] - arr[i]. This observation allows the algorithm to determine whether a pair (i, j) can extend an existing Fibonacci-like subsequence.

Path to Optimal

Preview

Since a Fibonacci-like sequence depends on its last two values, the algorithm tracks subsequences by their final pair of indices. Let dp[i][j] represent the length of the longest Fibonacci-like subsequence ending with arr[i] followed by arr[j]…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Construct a value-to-index map to allow constant-time lookup of any number's index…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

The algorithm iterates over all pairs (i, j) in the array, which is O(n^2). Each lookup in the hash map is O(1), so total time is O(n^2).

Space

O(n^2)

The DP table stores lengths for all pairs (i, j), requiring O(n^2) auxiliary space. The hash map requires O(n) space for value-to-index mapping.

Solution

Python

1class Solution:
2    def lenLongestFibSubseq(self, arr):
3        n = len(arr)
4
5        value_to_index = {}
6        for i in range(n):
7            value_to_index[arr[i]] = i
8
9        dp = [[2] * n for _ in range(n)]
10
11        longest = 0
12
13        for j in range(n):
14            for i in range(j):
15
16                prev = arr[j] - arr[i]
17
18                if prev in value_to_index:
19                    k = value_to_index[prev]
20
21                    if k < i:
22                        dp[i][j] = dp[k][i] + 1
23                        longest = max(longest, dp[i][j])
24
25        return longest if longest >= 3 else 0

Step-by-Step Solution

1

Build Value-to-Index Map for O(1) Lookup

3n = len(arr)
5value_to_index = {}
6for i in range(n):
7    value_to_index[arr[i]] = i

Objective

To create a hash map that maps each array value to its index for constant-time lookups.

Key Insight

The DP recurrence requires quickly finding if a value exists in the array and its index. A hash map enables O(1) lookups, which is critical to avoid an O(n^3) brute-force search for the previous element in the Fibonacci-like sequence.

Interview Quick-Check

Core Logic

Mapping values to indices allows the algorithm to find the potential previous element in O(1) time, enabling efficient DP updates.

Common Pitfalls & Bugs

Not building this map leads to O(n) searches for each pair, resulting in O(n^3) time complexity.

2

Initialize DP Table with Base Lengths

To set up a 2D DP array where each entry dp[i][j] starts at 2, representing the minimal length of a Fibonacci-like subsequence with two elements.

3

Iterate Over Pairs and Extend Fibonacci Subsequences

To update the DP table by checking for a valid previous element that extends the Fibonacci-like subsequence ending at (i, j).

4

Return the Length of the Longest Valid Subsequence

To return the maximum length found if it is at least 3, otherwise return 0 indicating no valid Fibonacci-like subsequence.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 22 Critical

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

Extend the subsequence ending at (k, i) to include arr[j].

This dynamic programming transition extends an existing Fibonacci-like subsequence. If arr[k], arr[i] already form the end of a valid sequence, adding arr[j] increases its length by one while preserving the Fibonacci relation.

Line 9 Critical

dp = [[2] * n for _ in range(n)]

Initialize the DP table where dp[i][j] stores the length of a subsequence ending with arr[i] and arr[j].

Each DP state represents a subsequence ending with arr[i] and arr[j]. Any pair of elements forms a subsequence of length two, so initializing every state to 2 establishes the base length before any Fibonacci extension occurs.

Line 16 Critical

prev = arr[j] - arr[i]

Compute the value that would precede arr[i] in a Fibonacci-like relation.

For arr[i] and arr[j] to be consecutive elements of a Fibonacci-like sequence, a previous value must satisfy prev + arr[i] = arr[j]. Rearranging yields prev = arr[j] - arr[i], identifying the value required to extend the sequence.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why must the index k of the previous element be less than i when extending the subsequence?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Length of Longest Fibonacci Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Length of Longest Fibonacci Subsequence drill

or drill a free problem

1	`class Solution:`
2	`def lenLongestFibSubseq(self, arr):`
3	`n = len(arr)`
4
5	`value_to_index = {}`
6	`for i in range(n):`
7	`value_to_index[arr[i]] = i`
8
9	`dp = [[2] * n for _ in range(n)]`
10
11	`longest = 0`
12
13	`for j in range(n):`
14	`for i in range(j):`
15
16	`prev = arr[j] - arr[i]`
17
18	`if prev in value_to_index:`
19	`k = value_to_index[prev]`
20
21	`if k < i:`
22	`dp[i][j] = dp[k][i] + 1`
23	`longest = max(longest, dp[i][j])`
24
25	`return longest if longest >= 3 else 0`

3	`n = len(arr)`
5	`value_to_index = {}`
6	`for i in range(n):`
7	`value_to_index[arr[i]] = i`