873. Length of Longest Fibonacci Subsequence

Problem Description

The problem provides us with a sequence of positive integers that is strictly increasing - meaning each number is greater than the previous one. We are asked to find the length of the longest subsequence that is Fibonacci-like within this sequence. A subsequence is considered Fibonacci-like if it satisfies two conditions: It must have at least three numbers, and each number in the subsequence (after the second) must be the sum of the two preceding numbers. To clarify with an example, if our sequence is [1, 2, 3, 4, 5, 6, 7, 8], a Fibonacci-like subsequence could be [1, 2, 3, 5, 8]. If no such subsequence exists, the result should be 0.

Intuition

The solution uses the concept of dynamic programming to build up a table of solutions to subproblems, which in this case, are the lengths of the longest Fibonacci-like subsequences ending at different positions in the original sequence.

First, we create a mapping of each number in the sequence to its index to speed up the search for a number's existence within the sequence.

Since we need at least three numbers to form a Fibonacci-like sequence, the default length for any pair of starting numbers is 2 (which is not a valid Fibonacci-like subsequence by itself, but is the basis for building longer ones).

The key intuition is that if arr[k] + arr[j] == arr[i] and k < j < i, then the value at dp[j][i] (the length of the subsequence ending with arr[j] and arr[i]) can be updated to dp[k][j] + 1 (which extends the subsequence that ends with arr[k] and arr[j] by adding arr[i]).

We iterate through each pair of numbers, updating the dynamic programming table dp whenever we find two numbers that add up to a third one in the sequence. The answer is the maximum value in the table dp that represents the length of the longest Fibonacci-like subsequence we have found.

At each step, we are effectively looking backwards from a potential ending number i to see if we can form a Fibonacci-like sequence by finding two previous numbers j and k that add up to arr[i]. If we find such a pair, we know we can extend the subsequence that ended at arr[j] to now end at arr[i] and hence update our dp table accordingly.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution approach takes advantage of a dynamic programming paradigm and hash mapping. We use these tools to systematically build a solution that finds the longest Fibonacci-like subsequence within an array of strictly increasing positive integers. The following steps outline how the code implements this solution:

1. Hash Map Construction: We first construct a hash map (mp) to store each array value (v) and its respective index (i). This greatly optimizes our solution as it allows us to check whether a number exists in the array in constant time.

   1mp = {v: i for i, v in enumerate(arr)}

2. Dynamic Programming Table Initialization: We create a 2D table (dp) where dp[j][i] will hold the maximum length of a Fibonacci-like subsequence which ends with the elements arr[j] and arr[i]. Initially, we set all pairs (j, i) in dp to 2, which is the minimum length of any subsequence consisting of two elements.

   1dp = [[0] * n for _ in range(n)]
   2for i in range(n):
   3    for j in range(i):
   4        dp[j][i] = 2

3. Updating the DP Table: We then use two nested loops to iterate through the array to find and extend existing Fibonacci-like subsequences. For each pair of indices (j, i), we calculate the potential preceding number d by subtracting arr[j] from arr[i].

   1for i in range(n):
   2    for j in range(i):
   3        d = arr[i] - arr[j]

   We then check if this number d exists in the array (and thus in the hash map). If it does and the index of d (k) is less than j, we are in a position to extend the subsequence that previously ended with arr[k] and arr[j]. The length of the new subsequence will be dp[k][j] + 1.

   1if d in mp and (k := mp[d]) < j:
   2    dp[j][i] = max(dp[j][i], dp[k][j] + 1)

4. Finding the Answer: While updating the dp table, we keep track of the maximum length found so far (ans). Whenever we update an entry in the dp table, we compare it with the current maximum length and update ans if necessary.

   1ans = max(ans, dp[j][i])

5. Returning the Result: After iterating over all pairs and updating the dp table, ans contains the length of the longest Fibonacci-like subsequence. If no such subsequence exists longer than two elements, ans will be 0. Therefore, we return ans as the result.

   1return ans

It's interesting to note that the dynamic programming table is not fully utilized. Most of its default-initialization values remain unchanged, especially near the diagonal where i and j are close. The only entries that receive meaningful updates reflect valid subsequences of length greater than two. The efficient use of the hash map allows for quick validation of potential Fibonacci-like sequences, which is central to the dynamic programming update step.

Example Walkthrough

Let's walk through an example to illustrate the solution approach using a small sequence of positive integers: [1, 3, 7, 11, 12, 14, 18].

First, we initialize the hash map mp to map each number to its index in the array.

1mp = {1: 0, 3: 1, 7: 2, 11: 3, 12: 4, 14: 5, 18: 6}

Next, we initialize the dynamic programming table dp. Since the array length n is 7, dp is a 7x7 2D array where all pairs (j, i) are initially set to a subsequence length of 2.

Now, we start iterating over the pairs of indices (j, i). We're looking for whether the difference d = arr[i] - arr[j] exists in the array and corresponds to an index k such that k < j.

When i = 3 and j = 2, arr[i] = 11, arr[j] = 7, so d = 11 - 7 = 4. There is no 4 in the array, so we move on.

Next significant update happens when i = 4 and j = 1. Here arr[i] = 12 and arr[j] = 3, so d = 12 - 3 = 9. The number 9 does not exist in the array either. Again, we proceed forward.

When i = 6 and j = 5, arr[i] = 18 and arr[j] = 14, so d = 18 - 14 = 4. Since 4 is not present in our array, no update in dp occurs.

However, the first update occurs when i = 5 and j = 1, then arr[i] = 14, arr[j] = 3, and hence d = 14 - 3 = 11. We see that 11 is in the array at index 3. Therefore, k = 3 and k < j. We update dp[j][i] = dp[k][j] + 1 = dp[3][1] + 1 = 2 + 1 = 3.

Now dp looks like this (a snippet of relevant parts):

1dp[1][5] = 3   # This tells us there's a subsequence ending at arr[1] (3) and arr[5] (14) with length 3.

Given this dp update, our current maximum ans becomes 3.

By the end of the iteration, since no other updates result in a longer subsequence, the longest Fibonacci-like subsequence we have is [3, 11, 14]. Hence, the answer ans is 3. If there were no updates that result in a value greater than 2, ans would remain 0, indicating no valid Fibonacci-like subsequences exist beyond two elements.

Finally, we return ans, which is 3 in this case.

Solution Implementation

Time and Space Complexity

The given code is designed to find the length of the longest Fibonacci-like subsequence in a given array arr. We analyze both the time complexity and the space complexity of the code.

Time Complexity:

Initially, the given code creates a hashmap (mp) from each element to its index with a time complexity of O(n), where n is the length of the array arr.

The main part of the algorithm consists of nested loops. The outer loop runs n times, and for each iteration, the inner loop runs at most n times, yielding n^2 iterations for the nested loops.

Inside the inner loop, the code performs constant-time operations such as dictionary look-up (to check if d exists in mp), assignments, and arithmetic operations. The look-up in mp takes O(1) on average. Therefore, the inner block within the inner loop also executes in constant time.

Considering these nested loops as the dominant factor, the time complexity is O(n^2).

Space Complexity:

For space complexity, the code uses:

• A hashmap mp with at most n entries, thus O(n) space.
• A 2D array dp of size n * n, accounting for O(n^2) space.

Therefore, the space complexity is dominated by the 2D array dp, making the overall space complexity of the code O(n^2).

In conclusion, the code has a time complexity of O(n^2) and a space complexity of O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.