You are given an array of positive integers nums.
A Fibonacci array is a contiguous sequence whose third and subsequent terms each equal the sum of the two preceding terms.
Return the length of the longest Fibonacci subarray in nums.
Note: Subarrays of length 1 or 2 are always Fibonacci.
Example 1:
Input: nums = [1,1,1,1,2,3,5,1]
Output: 5
Explanation:
The longest Fibonacci subarray is nums[2..6] = [1, 1, 2, 3, 5].
[1, 1, 2, 3, 5] is Fibonacci because 1 + 1 = 2, 1 + 2 = 3, and 2 + 3 = 5.
Example 2:
Input: nums = [5,2,7,9,16]
Output: 5
Explanation:
The longest Fibonacci subarray is nums[0..4] = [5, 2, 7, 9, 16].
[5, 2, 7, 9, 16] is Fibonacci because 5 + 2 = 7, 2 + 7 = 9, and 7 + 9 = 16.
Example 3:
Input: nums = [1000000000,1000000000,1000000000]
Output: 2
Explanation:
The longest Fibonacci subarray is nums[1..2] = [1000000000, 1000000000].
[1000000000, 1000000000] is Fibonacci because its length is 2.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: Given an integer array, find the length of the longest contiguous subarray that forms a Fibonacci-like sequence. For every index i ≥ 2, the condition arr[i] = arr[i-1] + arr[i-2] must hold. The goal is to scan the array and detect the longest segment satisfying this property.
Approach 1: Brute Force Expansion (O(n²) time, O(1) space)
Start every possible Fibonacci subarray using two consecutive elements (i, i+1). From that starting pair, keep extending forward while the Fibonacci condition holds: check if arr[k] == arr[k-1] + arr[k-2]. Stop as soon as the condition breaks and record the length of that segment. Repeat this process for all starting indices in the array. The idea is simple and mirrors how you would manually verify Fibonacci patterns. The downside is that many subarrays are rechecked repeatedly, which pushes the time complexity to O(n²) in the worst case while using O(1) extra space.
Approach 2: Dynamic Programming / Linear Scan (O(n) time, O(1) space)
A more efficient approach observes that the Fibonacci condition only depends on the previous two elements. While iterating once through the array, maintain a variable representing the current Fibonacci subarray length. For each index i ≥ 2, check whether arr[i] == arr[i-1] + arr[i-2]. If the condition holds, extend the current length by one. Otherwise, reset the length to 2 because any two consecutive elements can start a new Fibonacci candidate. Track the maximum length seen during the scan.
This works because the state of the problem only depends on the previous two values, which makes it a compact form of dynamic programming. Instead of storing a full DP table, you reuse the running length as the state transition result. Each element is processed once, resulting in O(n) time with constant extra memory.
Recommended for interviews: Interviewers expect the linear scan dynamic programming insight. The brute force approach shows you understand the Fibonacci condition and how subarrays grow, but the optimal solution demonstrates the ability to reduce repeated work and recognize that only the previous two elements influence the state.
We can use a variable f to record the length of the longest Fibonacci subarray ending at the current element. Initially, f=2, indicating that any two elements can form a Fibonacci subarray.
Then we traverse the array starting from index 2. For each element nums[i], if it equals the sum of the previous two elements, i.e., nums[i] = nums[i-1] + nums[i-2], it means the current element can be appended to the previous Fibonacci subarray, so we increment f by 1. Otherwise, it means the current element cannot be appended to the previous Fibonacci subarray, so we reset f to 2. During the traversal, we continuously update the answer ans = max(ans, f).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(n²) | O(1) | Useful for understanding the Fibonacci condition and verifying small inputs |
| Dynamic Programming / Linear Scan | O(n) | O(1) | Best for interviews and production code when scanning large arrays |
Longest Fibonacci Subarray | LeetCode 3708 | Biweekly Contest 167 • Sanyam IIT Guwahati • 387 views views
Watch 7 more video solutions →Practice Longest Fibonacci Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor