Problem Description

A sequence x₁, x₂, ..., xₙ is called Fibonacci-like if it satisfies two conditions:

• The sequence has at least 3 elements (n >= 3)
• Each element is the sum of the two preceding elements: xᵢ + xᵢ₊₁ = xᵢ₊₂ for all valid indices

Given a strictly increasing array arr of positive integers, you need to find the length of the longest Fibonacci-like subsequence that can be formed from arr. If no such subsequence exists, return 0.

A subsequence is formed by deleting any number of elements (including none) from the original array while maintaining the relative order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

The key challenge is to identify which elements from the strictly increasing array can form a valid Fibonacci-like pattern when selected as a subsequence. Since the array is strictly increasing, you need to carefully choose elements that satisfy the Fibonacci property where each element equals the sum of the two preceding ones.

For example, if arr = [1, 2, 3, 4, 5, 6, 7, 8], one possible Fibonacci-like subsequence is [1, 2, 3, 5, 8] with length 5, where:

• 1 + 2 = 3
• 2 + 3 = 5
• 3 + 5 = 8

Intuition

To find the longest Fibonacci-like subsequence, we need to think about what defines such a sequence. Any Fibonacci-like sequence is uniquely determined by its first two elements - once we fix the first two numbers, the rest of the sequence follows automatically by the addition rule.

This observation leads us to consider using dynamic programming where we track sequences by their last two elements. Why the last two? Because in a Fibonacci sequence, knowing the last two elements tells us what the next element must be (their sum), and we can build sequences forward.

Let's define f[i][j] as the length of the longest Fibonacci-like subsequence ending with arr[j] as the second-to-last element and arr[i] as the last element. Initially, any two elements can form a sequence of length 2, so we start with f[i][j] = 2 for all valid pairs.

Now, for extending a sequence: if we have arr[j] and arr[i] as the last two elements, the element before arr[j] in the sequence must be arr[i] - arr[j]. Let's call this value t. If t exists in our array at some index k where k < j (to maintain the subsequence property), then we've found a longer Fibonacci-like sequence. The sequence ending at positions k, j can be extended to positions j, i, giving us length f[j][k] + 1.

Using a hash table to store the indices of array elements allows us to quickly check if t = arr[i] - arr[j] exists in the array and find its position. This way, we can efficiently build up longer sequences by checking if we can extend existing ones.

The key insight is that we're not trying to build sequences from scratch each time - we're extending existing sequences by one element whenever possible, and the dynamic programming table helps us keep track of the best lengths achieved so far.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with a 2D array to track the longest Fibonacci-like subsequences. Here's the step-by-step implementation:

1. Initialize the DP table and hash map:

• Create a 2D array f[i][j] where f[i][j] represents the length of the longest Fibonacci-like subsequence ending with arr[j] and arr[i]
• Build a hash map d that maps each value in arr to its index for O(1) lookup: d = {x: i for i, x in enumerate(arr)}
• Initialize all f[i][j] where j < i to 2, since any two elements form a valid sequence of length 2

2. Fill the DP table: For each position i from 2 to n-1:

• For each position j from 1 to i-1:
  • Calculate t = arr[i] - arr[j], which would be the element needed before arr[j] to form a Fibonacci sequence
  • Check if t exists in our hash map d
  • If t exists and its index k = d[t] satisfies k < j (to maintain subsequence order):
    • Update f[i][j] = max(f[i][j], f[j][k] + 1)
    • This extends the sequence ending at (k, j) to now end at (j, i)
    • Update the global answer: ans = max(ans, f[i][j])

3. Return the result:

• If no Fibonacci-like subsequence of length ≥ 3 is found, ans remains 0
• Otherwise, return the maximum length found

Time Complexity: O(n²) where n is the length of the array, as we iterate through all pairs (i, j)

Space Complexity: O(n²) for the DP table, plus O(n) for the hash map

The key optimization here is using the hash map for O(1) lookup of whether a required previous element exists, rather than searching through the array each time. The dynamic programming approach ensures we build upon previously computed subsequences efficiently, avoiding redundant calculations.

Example Walkthrough

Let's walk through the solution with arr = [1, 3, 4, 7, 8, 11].

Step 1: Initialize

• Create hash map: d = {1:0, 3:1, 4:2, 7:3, 8:4, 11:5}
• Create DP table f[i][j] (initially all 2 for valid pairs where j < i):

    j=0  j=1  j=2  j=3  j=4
i=1  2    -    -    -    -
i=2  2    2    -    -    -
i=3  2    2    2    -    -
i=4  2    2    2    2    -
i=5  2    2    2    2    2

Step 2: Process each position

When i=2 (arr[2]=4):

• j=1 (arr[1]=3): t = 4-3 = 1, exists at k=0, k<j ✓
  • f[2][1] = f[1][0] + 1 = 2 + 1 = 3
  • Found sequence: [1,3,4] with length 3

When i=3 (arr[3]=7):

• j=1 (arr[1]=3): t = 7-3 = 4, exists at k=2, but k≥j ✗
• j=2 (arr[2]=4): t = 7-4 = 3, exists at k=1, k<j ✓
  • f[3][2] = f[2][1] + 1 = 3 + 1 = 4
  • Extended sequence: [1,3,4,7] with length 4

When i=4 (arr[4]=8):

• j=1 (arr[1]=3): t = 8-3 = 5, doesn't exist ✗
• j=2 (arr[2]=4): t = 8-4 = 4, exists at k=2, but k≥j ✗
• j=3 (arr[3]=7): t = 8-7 = 1, exists at k=0, k<j ✓
  • f[4][3] = f[3][0] + 1 = 2 + 1 = 3
  • Found sequence: [1,7,8] with length 3

When i=5 (arr[5]=11):

• j=1 (arr[1]=3): t = 11-3 = 8, exists at k=4, but k≥j ✗
• j=2 (arr[2]=4): t = 11-4 = 7, exists at k=3, but k≥j ✗
• j=3 (arr[3]=7): t = 11-7 = 4, exists at k=2, k<j ✓
  • f[5][3] = f[3][2] + 1 = 4 + 1 = 5
  • Extended sequence: [1,3,4,7,11] with length 5
• j=4 (arr[4]=8): t = 11-8 = 3, exists at k=1, k<j ✓
  • f[5][4] = f[4][1] + 1 = 2 + 1 = 3
  • Found sequence: [3,8,11] with length 3

Step 3: Return result The maximum length found is 5, corresponding to the subsequence [1,3,4,7,11]:

• 1 + 3 = 4 ✓
• 3 + 4 = 7 ✓
• 4 + 7 = 11 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the length of the array arr. This is because the code uses two nested loops - the outer loop iterates from index 2 to n-1, and the inner loop iterates from index 1 to i-1. Although there's an additional dictionary lookup operation t in d and accessing d[t] inside the nested loops, these are O(1) operations for dictionary lookups. Therefore, the overall time complexity remains O(n²).

The space complexity is O(n²), where n is the length of the array arr. This is due to the 2D array f which has dimensions n × n, requiring O(n²) space. Additionally, there's a dictionary d that stores the mapping of array values to their indices, which takes O(n) space. Since O(n²) + O(n) = O(n²), the overall space complexity is O(n²).

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

Common Pitfalls

1. Incorrect DP State Definition

A common mistake is defining dp[i][j] to represent a sequence ending at indices i and j where i < j. This creates confusion because you're looking backward in the sequence, but the indices suggest forward progression.

Problem Example:

# Incorrect: dp[i][j] where i < j
dp = [[0] * n for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        dp[i][j] = 2  # Wrong initialization pattern

Solution: Always maintain dp[i][j] where j < i, representing a sequence ending with arr[j] followed by arr[i]. This makes the logic clearer:

# Correct: dp[i][j] where j < i
for i in range(n):
    for j in range(i):
        dp[i][j] = 2

2. Forgetting to Check Index Ordering

When looking for the third element in the Fibonacci sequence, developers often forget to verify that the required element appears before the current pair in the original array.

Problem Example:

# Missing index check
required_value = arr[i] - arr[j]
if required_value in value_to_index:  # Only checking existence
    k = value_to_index[required_value]
    dp[i][j] = dp[j][k] + 1  # May access invalid indices

Solution: Always verify that k < j < i to maintain subsequence order:

if required_value in value_to_index:
    k = value_to_index[required_value]
    if k < j:  # Essential check
        dp[i][j] = max(dp[i][j], dp[j][k] + 1)

3. Returning Wrong Value for No Valid Sequence

The problem requires returning 0 when no Fibonacci-like subsequence of length ≥ 3 exists, but some implementations return 2 (the default pair length).

Problem Example:

max_length = 2  # Wrong initial value
for i in range(2, n):
    for j in range(1, i):
        # ... update logic
return max_length  # Returns 2 even when no valid sequence exists

Solution: Initialize max_length to 0 and only update it when finding sequences of length ≥ 3:

max_length = 0  # Correct initialization
for i in range(2, n):
    for j in range(1, i):
        # ... calculate required_value
        if required_value in value_to_index and k < j:
            dp[i][j] = dp[j][k] + 1
            max_length = max(max_length, dp[i][j])  # Only update for valid sequences

4. Edge Case: Array Too Small

Not handling arrays with fewer than 3 elements gracefully.

Problem Example:

def lenLongestFibSubseq(self, arr: List[int]) -> int:
    n = len(arr)
    # Directly proceeding without checking n
    dp = [[0] * n for _ in range(n)]
    # May cause issues with range(2, n) when n < 3

Solution: Add an early return for small arrays:

def lenLongestFibSubseq(self, arr: List[int]) -> int:
    n = len(arr)
    if n < 3:
        return 0  # No Fibonacci-like sequence possible
    # ... rest of the implementation