# Solving Leetcode Interviews in Seconds with AI: Length of Longest Fibonacci Subsequence


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "873" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> A sequence x1, x2, ..., xn is Fibonacci-like if:  n >= 3 xi + xi+1 == xi+2 for all i + 2 <= n  Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0. A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].   Example 1:  Input: arr = [1,2,3,4,5,6,7,8] Output: 5 Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8]. Example 2:  Input: arr = [1,3,7,11,12,14,18] Output: 3 Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].   Constraints:  3 <= arr.length <= 1000 1 <= arr[i] < arr[i + 1] <= 109  

	# Explanation
	Here's the breakdown of the solution:

*   **Iterate through pairs:** Iterate through all possible pairs of numbers in the input array `arr` as potential starting values for a Fibonacci-like subsequence.
*   **Extend the subsequence:** For each pair, attempt to extend the subsequence by checking if the sum of the last two elements exists later in the array.
*   **Track the maximum length:** Keep track of the maximum length of any Fibonacci-like subsequence found so far.

*   **Runtime & Storage Complexity:** O(n^2 * log(n)) time complexity and O(n) space complexity. The n^2 comes from the nested loops, and the log(n) comes from the binary search. The O(n) space complexity is for the set.

	
	# Code
	```python
	def lenLongestFibSubseq(arr):
    """
    Finds the length of the longest Fibonacci-like subsequence of arr.

    Args:
        arr: A strictly increasing array of positive integers.

    Returns:
        The length of the longest Fibonacci-like subsequence of arr.
    """
    n = len(arr)
    index_map = {num: i for i, num in enumerate(arr)}
    max_len = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = arr[i]
            b = arr[j]
            length = 2
            while a + b in index_map:
                next_val = a + b
                a = b
                b = next_val
                length += 1
            max_len = max(max_len, length)

    return max_len if max_len >= 3 else 0
	```