The "Length of Longest Fibonacci Subsequence" problem is to compute the length of the longest Fibonacci sequence that is a subsequence in an array. Subsequence is a sequence that can be made from another sequence by cutting some of the elements and keeping the original order of remaining elements. The subsequence should also follow the property of being a Fibonacci series.

Fibonacci sequence is a series of numbers in which each number (Fibonacci number) is the sum of two numbers that came before it and they usually start from 0 and 1. That is, the sequence starts as follows: This series, Fibonacci sequence starts from 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

Example 1:

Input

A[] = {1, 2, 3, 4, 5, 6, 7, 8}

Output

Explanation

The longest fibonacci subsequence is {1, 2, 3, 5, 8}

Example 2:

Input

A[] = {1, 3, 5, 7, 8, 9, 11}

Output

Explanation

The longest fibonacci subsequence is {3, 5, 8} or {1, 7, 8}

Approach 1: Using HashSet

The "length of the longest Fibonacci subsequence" problem can be efficiently solved using a HashSet-based approach. In this approach, we leverage the HashSet data structure to store the elements of the input array, allowing for constant-time lookup of elements. The algorithm iterates through all pairs of numbers in the array and attempts to extend each pair into a Fibonacci subsequence by continuously adding the next number in the sequence until it is no longer present in the HashSet.

Algorithm

Step 1: Initialize a HashSet to store elements of the input array for efficient lookup operations.

Step 2: Iterate through all pairs of numbers (a, b) in the input array using nested loops. The outer loop iterates from the first element to the second last element of the array.

Step 3: The inner loop iterates from the next element after the current outer loop element to the last element of the array.

Step 4: Attempt Fibonacci Subsequence Extension: For each pair of numbers (a, b), consider them as the first two numbers of a potential Fibonacci subsequence.

Step 5: Start a loop to extend the subsequence by continuously adding the next Fibonacci number (a + b).

Step 6: Within the loop, check if the next Fibonacci number (a + b) exists in the HashSet. If it exists, update a and b and increment the length of the subsequence. Continue this process until the next Fibonacci number is not present in the HashSet.

Step 7: Maintain a variable to track the maximum length of the Fibonacci subsequence found so far. Update this variable whenever a longer subsequence is found.

Step 8: After iterating through all pairs of numbers and attempting to extend each subsequence, return the maximum length of the Fibonacci subsequence found.

Filename: LongestFibonacciSubsequence.java

import java.util.*;

public class LongestFibonacciSubsequence {

    public static int lenLongestFibSubseq(int[] A) {

        // Initialize a HashSet to store elements of the array

        Set<Integer> set = new HashSet<>();

        for (int num : A) {

            set.add(num);

        }

        int maxLength = 0;

        // Iterate through all pairs of numbers (a, b) in the array

        for (int i = 0; i < A.length - 1; i++) {

            for (int j = i + 1; j < A.length; j++) {

                int a = A[i], b = A[j], len = 2;

                // Attempt to extend the Fibonacci subsequence

                while (set.contains(a + b)) {

                    int temp = a + b;

                    a = b;

                    b = temp;

                    len++;

                }

                // Update the maximum length if a longer subsequence is found

                maxLength = Math.max(maxLength, len);

            }

        }

        // Return the maximum length of the Fibonacci subsequence

        return maxLength > 2 ? maxLength : 0;

    }

    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 7, 8, 9, 11};

        // Calculate the length of the longest Fibonacci subsequence

        int longestFibSubseqLength = lenLongestFibSubseq(arr);

        System.out.println("Length of the longest Fibonacci subsequence: " + longestFibSubseqLength);

    }

}

Output:

Length of the longest Fibonacci subsequence: 3

Time Complexity

The algorithm iterates through all pairs of numbers in the input array using nested loops. It results in a time complexity of O(n^2), where n is the size of the input array. Within the nested loops, the extension of potential Fibonacci subsequences involves constant-time operations, such as checking set membership and updating variables.

Space Complexity

The space complexity of the algorithm is primarily determined by the HashSet used to store the elements of the input array. Since each element of the array is stored in the HashSet, the space complexity is O(n), where n is the size of the input array.

Approach 2: Dynamic Programming

The dynamic programming approach using a HashMap for solving the "length of the longest Fibonacci subsequence" problem involves breaking down the problem into smaller subproblems and utilizing memorization to store the solutions to these subproblems in a HashMap. In this approach, we optimize the computation by avoiding redundant calculations and significantly improves the time complexity of the solution.

Algorithm

Step 1: Initialize a HashMap called map to store the solutions to subproblems. The key of the HashMap will be a pair of two integers (a, b) representing the last two elements of a potential Fibonacci subsequence, and the value will be the length of that subsequence.

Step 2: Initialize a variable maxLength to keep track of the length of the longest Fibonacci subsequence encountered.

Step 3: Iterate through each pair of numbers (A[i], A[j]) in the input array, where j > i. Check for Fibonacci Property: Check if the pair (A[i], A[j]) forms a valid extension of a Fibonacci subsequence.

Step 4: To form a Fibonacci subsequence, A[j] - A[i] should be present in the HashMap as one of the keys, and its value should be less than i.

Step 5: Update HashMap and maxLength: If (A[i], A[j]) forms a valid Fibonacci subsequence, update the HashMap entry for (A[i], A[j]) by adding 1 to the length obtained from (A[j] - A[i]).

Step 6: Update maxLength if the length of the current Fibonacci subsequence is greater than maxLength.

Step 7: After processing all pairs of numbers in the array, return maxLength, which represents the length of the longest Fibonacci subsequence.

Filename: LongestFibonacciSubsequence.java

import java.util.*;

public class LongestFibonacciSubsequence {

    public static int lenLongestFibSubseq(int[] A) {

        int n = A.length;

        Map<Integer, Integer> indexMap = new HashMap<>();

        int maxLength = 0;

        // Initialize the HashMap with the indices of elements in the array

        for (int i = 0; i < n; i++) {

            indexMap.put(A[i], i);

        }

        // Initialize the dynamic programming HashMap

        Map<Integer, Integer> dp = new HashMap<>();

        // Iterate through each pair of numbers (A[i], A[j]) in the array

        for (int j = 1; j < n; j++) {

            for (int i = 0; i < j; i++) {

                int a = A[i];

                int b = A[j];

                int len = dp.getOrDefault(a * n + b, 2); // Initialize with 2

                // Check if a potential Fibonacci subsequence can be extended

                if (indexMap.containsKey(a + b)) {

                    int k = indexMap.get(a + b);

                    dp.put(b * n + (a + b), len + 1);

                    maxLength = Math.max(maxLength, len + 1);

                }

            }

        }

        // Return the maximum length of the Fibonacci subsequence found

        return maxLength > 2 ? maxLength : 0;

    }

    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 7, 8, 9, 11};

        int longestFibSubseqLength = lenLongestFibSubseq(arr);

        System.out.println("Length of the longest Fibonacci subsequence: " + longestFibSubseqLength);

    }

}

Output:

Length of the longest Fibonacci subsequence: 3

Time Complexity

The time complexity of the dynamic programming approach with a HashMap is O(n^2), where n is the size of the input array. The complexity arises from the nested iteration over all pairs of elements in the array, and for each pair, performing constant-time operations for HashMap lookup and insertion.

Space Complexity

The space complexity of the algorithm is also O(n^2). It is because we use a HashMap to store solutions to subproblems, and the space required for the HashMap scales with the number of unique pairs of elements in the array. Additionally, other constant-space variables used for indices and lengths do not significantly affect the overall space complexity.

Approach 3: Using Linked List

Using a linked list as a cache for solving the "Length of the Longest Fibonacci Subsequence" problem involves leveraging the structure of a linked list to efficiently store and update elements of the input array while searching for Fibonacci subsequences. In this approach, we will optimize the memory usage and have advantage for fast insertion and lookup operations, resulting in improved algorithmic efficiency.

Algorithm

Step 1: Initialize a linked list named cache to serve as a cache for storing elements of the input array. Initialize a pointer named tail to keep track of the tail node of the linked list.

Step 2: Map Initialization: Initialize a HashMap named map to store the elements of the input array for fast lookup. Iterate through the input array A, and for each element num, add an entry to the HashMap with key num and value true.

Step 3: Initialize Maximum Length: Initialize a variable named maxLength to 0. This variable will be used to keep track of the length of the longest Fibonacci subsequence encountered.

Step 4: Iterate Through Pairs: Iterate through each pair of numbers (A[i], A[j]) in the input array, where i < j. Use nested loops for this purpose, with the outer loop iterating over the range [1, A.length) and the inner loop iterating over the range [0, i).

Step 5: Check for Fibonacci Property: For each pair (A[i], A[j]), initialize two variables a and b to store the current pair. Initialize a variable length to 2, representing the length of the current Fibonacci subsequence formed by A[i] and A[j].

Step 6: While the sum a + b is present in the HashMap map: Update a and b for the next iteration of the loop. Increment length to reflect the extended Fibonacci subsequence.

Step 7: Update the sum a + b in the cache (linked list) by appending b to the end of the linked list. Update the tail pointer tail to point to the newly added node in the linked list.

Step 8: Update Maximum Length: If the length of the current Fibonacci subsequence (length) is greater than maxLength, update maxLength to length.

Step 9: After processing all pairs of numbers in the array, return maxLength, which represents the length of the longest Fibonacci subsequence encountered.

Filename: LongestFibonacciSubsequence.java

import java.util.*;

public class LongestFibonacciSubsequence {

    static class ListNode {

        int val;

        ListNode next;

        ListNode(int val) {

            this.val = val;

            this.next = null;

        }

    }

    public static int lenLongestFibSubseq(int[] A) {

        // Initialize a linked list as a cache

        ListNode cache = new ListNode(-1);

        ListNode tail = cache;

        // Map to store elements of the input array for fast lookup

        Map<Integer, Boolean> map = new HashMap<>();

        for (int num : A) {

            map.put(num, true);

        }

        int maxLength = 0;

        // Iterate through each pair of numbers (A[i], A[j]) in the input array

        for (int j = 1; j < A.length; j++) {

            for (int i = 0; i < j; i++) {

                int a = A[i], b = A[j];

                int length = 2; // Length of current Fibonacci subsequence

                // Check if (A[i] + A[j]) is present in the cache (linked list)

                while (map.containsKey(a + b)) {

                    // Update a and b for the next iteration

                    int temp = a + b;

                    a = b;

                    b = temp;

                    length++;

                }

                // If the length of the current Fibonacci subsequence is greater than maxLength,

                // update maxLength accordingly

                if (length > maxLength) {

                    maxLength = length;

                }

            }

        }

        // Return the length of the longest Fibonacci subsequence found

        return maxLength >= 3 ? maxLength : 0;

    }

    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 7, 8, 9, 11};

        // Calculate the length of the longest Fibonacci subsequence

        int longestFibSubseqLength = lenLongestFibSubseq(arr);

        System.out.println("Length of the longest Fibonacci subsequence: " + longestFibSubseqLength);

    }

}

Output:

Length of the longest Fibonacci subsequence: 3

Time Complexity

The time complexity of this approach is O(n^2), where n is the size of the input array A. The complexity arises from the nested iteration over all pairs of elements in the array, and for each pair, performing a constant-time check for the presence of the sum in the HashMap.

Space Complexity

The space complexity of this approach is O(n) due to the space required for the HashMap map and the linked list cache. Additionally, other constant-space variables used for indices and lengths do not significantly affect the overall space complexity.

Conclusion

In conclusion, the problem of finding the length of the longest Fibonacci subsequence in Java offers various efficient approaches leveraging different data structures and algorithmic techniques. Overall, the HashSet and Dynamic Programming approaches strike a balance between time and space efficiency, making them preferable for most practical scenarios.

← Prev Next →

Length of the Longest Fibonacci Subsequence in Java

Approach 1: Using HashSet

Algorithm

Approach 2: Dynamic Programming

Algorithm

Approach 3: Using Linked List

Algorithm

Conclusion