algoadvance

Leetcode 873. Length of Longest Fibonacci Subsequence

Problem Statement

Given an integer array arr, return the length of the longest Fib-like subsequence of arr. If one does not exist, return 0.

A sequence X1, X2, ..., Xn is a Fib-like sequence if:

A subsequence is derived from another sequence arr by deleting some or none elements without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Clarifying Questions

  1. Input Constraints:
    • What is the range of input length?
    • What are the values of the integers in arr?
  2. Output Requirements:
    • Should the output be the length of the longest subsequence, or the subsequence itself?
  3. Duplicates:
    • How should duplicates be handled? Should we consider only distinct subsequences, or do duplicates affect the result?

Strategy

To solve this problem:

  1. Use a hash table (or set) to quickly check the existence of previous elements.
  2. Utilize dynamic programming (DP) to build potential sequences.

Steps

  1. Initialization:
    • Create a set to store all elements of the array for quick look-up.
    • Define a DP dictionary, where dp[i, j] represents the length of the Fibonacci-like subsequence ending with elements arr[i] and arr[j].
  2. Iteration:
    • Loop through each pair of indices (i, j) and check if there exists an earlier index k such that arr[k] + arr[i] == arr[j]. If it exists, update the DP state.
  3. Result Calculation:
    • The length of the longest valid subsequence is found by taking the maximum value in the DP table, ensuring it is at least 3, or return 0 otherwise.

Time Complexity

Code

#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;

int lenLongestFibSubseq(vector<int>& arr) {
    unordered_set<int> S(arr.begin(), arr.end());
    unordered_map<int, int> dp;
    int n = arr.size();
    int maxLen = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = arr[i];
            int b = arr[j];
            int len = 2;
            while (S.find(a + b) != S.end()) {
                int c = a + b;
                a = b;
                b = c;
                ++len;
            }
            maxLen = max(maxLen, len);
        }
    }
    // We need at least three elements to form a sequence
    return maxLen >= 3 ? maxLen : 0;
}

This implementation uses a nested loop to iterate through index pairs and a while-loop to extend the potential Fibonacci subsequence. It ensures to keep track of the longest sequence found and checks if it meets the minimum required length of 3.

Feel free to ask any further questions or specific clarifications!

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