Length of Longest Fibonacci Subsequence

Problem

A sequence x1, x2, ..., xn is Fibonacci-like if:

n >= 3
xi + xi+1 == xi+2 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 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].

Examples

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].

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Using Greedy approach

To solve the problem of finding the longest Fibonacci-like subsequence, we begin by revisiting the defining property of a Fibonacci sequence:

Every number is the sum of the two preceding numbers.

This means that if we know the first two numbers of a Fibonacci-like sequence, the rest of the sequence is uniquely determined. For example:

Starting with 2 and 3, the sequence would proceed as 5, 8, 13, ..., and so on.

This leads to the first key insight:

If we identify the first two numbers of a subsequence, we can determine the rest by repeatedly checking for the next required number.

Code

Java

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Set<Integer> numSet = new HashSet<>(); // To store all array elements for O(1) lookups
        for (int num : arr) {
            numSet.add(num);
        }

        int maxLen = 0; // To track the maximum length

        // Iterate through all pairs (i, j) where i is the "first" and j is the "second"
        for (int i = 0; i < n; i++) { // First number
            for (int j = i + 1; j < n; j++) { // Second number
                int first = arr[i];
                int second = arr[j];
                int currLen = 2; // Start the subsequence with length 2
				
				int third = first + second; // Calculate the next number in the sequence
                // Extend the sequence greedily
                while (numSet.contains(third)) {                    
                    first = second; // Move second to first
                    second = third; // Move third to second
                    currLen++; // Increment the sequence length
                    
                    third = first + second;
                }

                // Update the maximum length
                maxLen = Math.max(maxLen, currLen);
            }
        }

        // If maxLen is less than 3, no valid Fibonacci-like subsequence exists
        return maxLen >= 3 ? maxLen : 0;
    }
}

Python

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        num_set = set(arr)  # Use a set for O(1) lookups
        max_len = 0  # To track the maximum length

        # Iterate through all pairs (i, j) where i is the "first" and j is the "second"
        for i in range(n):  # First number
            for j in range(i + 1, n):  # Second number
                first = arr[i]
                second = arr[j]
                curr_len = 2  # Start the subsequence with length 2
                
                third = first + second  # Calculate the next number in the sequence
                # Extend the sequence greedily
                while third in num_set:
                    first, second = second, third  # Shift the sequence
                    curr_len += 1  # Increment the sequence length
                    third = first + second  # Calculate the next number
                
                # Update the maximum length
                max_len = max(max_len, curr_len)

        # If max_len is less than 3, no valid Fibonacci-like subsequence exists
        return max_len if max_len >= 3 else 0

Complexity

Time: O(n^2 log M), where n is the length of the array and M is the maximum element in the array.
- The two loops to select pairs (arr[j], arr[i]) iterate over all unique pairs. This takes O(n²) time.
- Inside the loop, we attempt to build a Fibonacci-like sequence starting from the chosen pair. Fibonacci numbers grow exponentially, so the number of iterations of this loop is bounded by ( \log M ), where (M) is the largest element in the array.
Space: O(n)

Method 2 - Using DP

The problem asks us to find the longest Fibonacci-like subsequence in an array. The greedy approach works well but involves repeatedly recalculating the same information, such as whether a number exists and extending the sequence from scratch for every pair of starting numbers.

To make this process more efficient, we can use dynamic programming (DP) to:

Reuse previously computed results: Instead of extending sequences greedily, we can keep track of the lengths of Fibonacci-like subsequences ending at specific indices in a 2D table.
Break the problem into subproblems: For any pair of indices (j, i) ((j < i)), we can calculate the length of the Fibonacci-like subsequence ending at arr[j] and arr[i] by finding the previous number arr[k] = arr[i] - arr[j] (if it exists and satisfies (k < j)).

So, the key idea is:

Every Fibonacci-like subsequence of length $\geq 3$ can be determined uniquely by its last two numbers.
- Hence, we define dp[j][i] as the length of the longest Fibonacci-like subsequence ending at indices j and i in the array.

Approach

Initialisation:
- Create a dp table of size (n \times n), where each entry is initialised to 2 (indicating the minimum length for a pair).
- Use a map to store the index of every number in the array for efficient lookups.
Recurrence Relation:
- For each pair of indices (j, i) ((j < i)), calculate the possible third-to-last number: arr[k] = arr[i] - arr[j]
- If arr[k] exists in the array and its index k is less than j, update the DP table: dp[j][i] = dp[k][j] + 1
- Otherwise, leave dp[j][i] as 2.
Track the Maximum Length:
- For each valid pair (j, i), update a variable max_len with the maximum value of dp[j][i].
Iteration:
- Use two nested loops:
  - Outer loop with i (current endpoint of the sequence).
  - Inner loop with j (second-to-last number).
- For each pair, compute the third-to-last number and update the DP table using the recurrence relation.
Final Output:
- Return max_len if it is greater than or equal to 3. Otherwise, return 0 (indicating no valid Fibonacci-like subsequence exists).

Code

Java

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n]; // To store the Fibonacci-like subsequence lengths
        Map<Integer, Integer> indexMap = new HashMap<>(); // To map values to their indices
        int maxLen = 0; // To track the maximum length

        // Populate the map with elements and their indices
        for (int i = 0; i < n; i++) {
            indexMap.put(arr[i], i);
        }

        // Iterate backward through the array
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                int first = arr[i];
                int second = arr[j];
                int currLen = 2; // Start the subsequence with length 2
				
				int third = first + second; // Calculate the next number in the sequence
                
                if (indexMap.containsKey(third)) { // Check if `third` exists in the map
                    int k = indexMap.get(third); // Retrieve the index of `third`
                    // Extend the Fibonacci-like subsequence
                    currLen = dp[j][k] + 1;
                    maxLen = Math.max(maxLen, currLen); // Update the maximum length
                }
                 dp[i][j] = currLen;
            }
        }

        // Return the maximum length found or 0 if no valid sequence exists
        return maxLen >= 3 ? maxLen : 0;
    }
}

Python

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[2] * n for _ in range(n)]  # DP table initialized with length 2
        index_map = {num: idx for idx, num in enumerate(arr)}  # Number to index mapping
        max_len = 0  # To keep track of the maximum sequence length

        # Iterate backward through the array
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i, -1):
                # Compute the next number in the Fibonacci-like sequence
                third = arr[i] + arr[j]  # arr[i] and arr[j] are first and second
                if third in index_map:  # Check if `third` exists in the map
                    k = index_map[third]  # Get the index of `third`
                    # Extend sequence length
                    dp[i][j] = dp[j][k] + 1
                    max_len = max(max_len, dp[i][j])  # Update max sequence length
                else:
                    dp[i][j] = 2  # Initialise with the default pair length

        # Return the longest sequence length if valid, otherwise 0
        return max_len if max_len >= 3 else 0

Complexity

Time: O(n^2). The two nested loops iterate over all pairs ((i, j)), contributing (O(n^2)).
Checking or retrieving third from the map takes (O(1)).
Space: O(n^2) for storing O(n^2) space DP table and O(n) space for map.

Problem

Examples

Solution

Video explanation

Method 1 - Using Greedy approach

Code

Java

Python

Complexity

Method 2 - Using DP

Approach

Code

Java

Python

Complexity

Comments