#873

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Length of Longest Fibonacci Subsequence

Find the length of the longest Fibonacci-like subsequence from a strictly increasing array of integers.

Problem Statement

Given a strictly increasing array of positive integers, your task is to determine the length of the longest subsequence that follows a Fibonacci-like pattern. A Fibonacci-like sequence is defined as a sequence where each element (from the third onward) is the sum of the two preceding elements.

For example, for the array [1,2,3,4,5,6,7,8], the longest Fibonacci-like subsequence is [1, 2, 3, 5, 8], and its length is 5. You should return the length of the longest Fibonacci-like subsequence, or 0 if no such subsequence exists.

Examples

Example 1

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

Output: 5

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

The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 109

Solution Approach

Dynamic Programming with Hash Table

Use dynamic programming with a hash table to store the lengths of subsequences that end at each pair of elements in the array. For each pair, check if their sum exists earlier in the array, which can extend the subsequence.

Iterate Through All Pairs

Iterate through all pairs of elements in the array. For each pair, check if there exists a valid Fibonacci-like subsequence formed by them, and update the subsequence length accordingly.

Optimize Using Hash Lookup

Optimize the solution by using a hash table to quickly check if a number exists in the array. This allows for faster lookup and reduces the time complexity of finding valid subsequences.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n^2)

The time complexity of this solution is O(n^2) due to the nested iterations over the array pairs. The space complexity is also O(n^2) because we store the lengths of subsequences in a hash table, which requires additional memory for each pair of elements.

What Interviewers Usually Probe

Can the candidate leverage dynamic programming efficiently for this problem?
Does the candidate recognize the importance of using a hash table for faster lookup?
Can the candidate explain the Fibonacci-like structure and how it applies to subsequences?

Common Pitfalls or Variants

Common pitfalls

Not considering all pairs of elements, which can miss valid subsequences.
Misunderstanding the Fibonacci-like condition, leading to incorrect subsequences.
Not optimizing the lookup with a hash table, which increases time complexity unnecessarily.

Follow-up variants

Variation with unsorted arrays: Can the approach be adjusted to handle non-strictly increasing arrays?
Variation with larger inputs: How would the algorithm scale if the array length increased significantly beyond 1000?
Variation with multiple valid subsequences: How to handle cases where there are multiple Fibonacci-like subsequences with the same length?

FAQ

What is a Fibonacci-like subsequence?

A Fibonacci-like subsequence is a sequence where each element (from the third onward) is the sum of the two preceding elements.

How can I optimize my solution for larger arrays?

Use dynamic programming with hash tables to speed up lookup times and avoid unnecessary computations for larger arrays.

Can this problem be solved without dynamic programming?

While a brute-force approach is possible, dynamic programming is the most efficient method for solving this problem in a reasonable time frame.

Why is a hash table used in this problem?

A hash table is used to quickly check if the sum of two elements exists in the array, optimizing the solution's time complexity.

What is the time complexity of this problem?

The time complexity is O(n^2), where n is the length of the array, due to the nested iteration over pairs of elements.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the length of the longest Fibonacci-like subsequence, with $\textit{arr}[i]$ as the last element and $\textit{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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        f = [[0] * n for _ in range(n)]
        d = {x: i for i, x in enumerate(arr)}
        for i in range(n):
            for j in range(i):
                f[i][j] = 2
        ans = 0
        for i in range(2, n):
            for j in range(1, i):
                t = arr[i] - arr[j]
                if t in d and (k := d[t]) < j:
                    f[i][j] = max(f[i][j], f[j][k] + 1)
                    ans = max(ans, f[i][j])
        return ans

Continue Practicing

#823 binary trees with factors #792 number of matching subsequences #996 number of squareful arrays