algoadvance

Leetcode 873. Length of Longest Fibonacci Subsequence

Problem Statement

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

A Fibonacci-like sequence is a sequence X such that:

• X[i] + X[i+1] = X[i+2] for all i + 2 < len(X).

For example, [1, 3, 7, 11, 12, 14, 18] can form the Fibonacci-like sequence [1, 11, 12, 23].

Example

• Input: arr = [1,2,3,4,5,6,7,8]
• Output: 5
• Explanation: The longest Fibonacci-like subsequence is [1,2,3,5,8].

Clarifying Questions

• Can the array contain duplicate elements?
  • No, the array is strictly increasing.
• What is the expected size of the input array?
  • The array size can be up to 1000.

Strategy

To find the length of the longest Fibonacci-like subsequence, we will use dynamic programming along with hashing:

1. Create a map that maps each element to its index for quick lookup.
2. Use a 2D DP array where dp[i][j] represents the length of the Fibonacci-like subsequence that ends with arr[i] and arr[j].
3. Iterate through pairs of indices (i, j) and for each pair, use the map to find if there exists a previous element arr[k] such that arr[k] + arr[i] = arr[j].
4. Update the DP table accordingly.
5. Keep track of the maximum length found during the process.

Code

import java.util.HashMap;
import java.util.Map;

public class LengthOfLongestFibonacciSubsequence {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(arr[i], i);
        }

        int[][] dp = new int[n][n];
        int maxLen = 0;

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int k = indexMap.getOrDefault(arr[j] - arr[i], -1);
                if (k >= 0 && k < i) {
                    dp[i][j] = dp[k][i] + 1;
                    maxLen = Math.max(maxLen, dp[i][j] + 2);
                }
            }
        }

        return maxLen > 2 ? maxLen : 0;
    }

    public static void main(String[] args) {
        LengthOfLongestFibonacciSubsequence solver = new LengthOfLongestFibonacciSubsequence();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(solver.lenLongestFibSubseq(arr)); // Output: 5
    }
}

Time Complexity

• The time complexity is (O(n^2)) where (n) is the number of elements in the input array arr. The nested loops are over pairs of indices, and each lookup in the map is (O(1)) on average.
• The space complexity is (O(n^2)) for the DP array, and (O(n)) for the map.

This approach efficiently finds the length of the longest Fibonacci-like subsequence in polynomial time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?