101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming with Hash Map - Complex approach
  2. Optimized Dynamic Programming - Complex approach
  3. Brute Force Approach - Complex approach

Approach 1: Dynamic Programming with Hash Map

The key insight for solving this problem is to use dynamic programming with a hash map. Since a Fibonacci sequence is uniquely determined by its first two elements, we can try all possible pairs of elements as the starting point and then check if we can extend the sequence.

Let's define a 2D DP table where dp[i][j] represents the length of the longest Fibonacci subsequence ending with arr[i] and arr[j]. We'll also use a hash map to quickly check if a specific value exists in the array.

Algorithm:

  1. Create a hash map to store the indices of elements in the array for quick lookup.
  2. Initialize a 2D DP table where dp[i][j] represents the length of the longest Fibonacci subsequence ending with arr[i] and arr[j].
  3. For each pair of indices (i, j) where i < j:
  4. a. Compute the previous element in the Fibonacci sequence: prev = arr[j] - arr[i].
  5. b. If prev exists in the array and prev < arr[i], let k be the index of prev.
  6. c. Update dp[i][j] = dp[k][i] + 1 if dp[k][i] exists, otherwise dp[i][j] = 3 (starting a new sequence).
  7. Return the maximum value in the DP table, or 0 if no Fibonacci subsequence of length at least 3 is found.

Time Complexity:

O(n²)

Where n is the length of the array. We need to consider all pairs of elements, which takes O(n²) time.

Space Complexity:

O(n²)

We need a 2D DP table of size n×n to store the lengths of Fibonacci subsequences.

Approach 2: Optimized Dynamic Programming

We can optimize the previous approach by using a different representation for the DP table. Instead of using indices, we can use the actual values of the elements as keys in a hash map.

Let's define dp[i][j] as the length of the longest Fibonacci subsequence ending with values i and j. This allows us to directly look up the length of a subsequence ending with specific values.

Algorithm:

  1. Create a hash map to store the indices of elements in the array for quick lookup.
  2. Initialize a hash map dp where dp[i][j] represents the length of the longest Fibonacci subsequence ending with values i and j.
  3. For each pair of indices (i, j) where i < j:
  4. a. Compute the previous element in the Fibonacci sequence: prev = arr[j] - arr[i].
  5. b. If prev exists in the array and prev < arr[i], update dp[arr[i]][arr[j]] = dp[prev][arr[i]] + 1 if dp[prev][arr[i]] exists, otherwise dp[arr[i]][arr[j]] = 3.
  6. Return the maximum value in the dp hash map, or 0 if no Fibonacci subsequence of length at least 3 is found.

Time Complexity:

O(n²)

Where n is the length of the array. We still need to consider all pairs of elements, which takes O(n²) time.

Space Complexity:

O(n²)

We need a hash map to store the lengths of Fibonacci subsequences, which can have up to O(n²) entries.

Approach 3: Brute Force Approach

A simpler but less efficient approach is to try all possible pairs of elements as the starting point of a Fibonacci sequence, and then check how far we can extend the sequence.

For each pair of elements (arr[i], arr[j]) where i < j, we'll try to find the next element in the sequence (arr[i] + arr[j]) and continue until we can't find the next element.

Algorithm:

  1. Create a hash set to store all elements in the array for quick lookup.
  2. Initialize maxLength = 0 to keep track of the longest Fibonacci subsequence found.
  3. For each pair of indices (i, j) where i < j:
  4. a. Initialize a = arr[i], b = arr[j], and length = 2.
  5. b. While (a + b) exists in the hash set:
  6. i. Update a = b, b = a + b, and length++.
  7. c. Update maxLength = max(maxLength, length) if length >= 3.
  8. Return maxLength, or 0 if no Fibonacci subsequence of length at least 3 is found.

Time Complexity:

O(n² log M)

Where n is the length of the array and M is the maximum value in the array. For each pair of elements (O(n²)), we might need to check up to O(log M) next elements in the sequence.

Space Complexity:

O(n)

We need a hash set to store all elements in the array, which takes O(n) space.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function lenLongestFibSubseq(arr):
    n = length of arr
 
    // Create a hash map for quick lookup
    index = empty hash map
    for i from 0 to n-1:
        index[arr[i]] = i
 
    // Initialize DP table
    dp = 2D array of size n×n, initialized with 0s
 
    maxLength = 0
 
    for j from 0 to n-1:
        for i from 0 to j-1:
            // Compute the previous element in the Fibonacci sequence
            prev = arr[j] - arr[i]
 
            // Check if prev exists and is smaller than arr[i]
            if prev < arr[i] and prev in index:
                k = index[prev]
 
                // Update DP table
                if dp[k][i] > 0:
                    dp[i][j] = dp[k][i] + 1
                else:
                    dp[i][j] = 3
 
                // Update maxLength
                maxLength = max(maxLength, dp[i][j])
 
    return maxLength
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone