Longest Fibonacci Subarray solution and explanation
6 more videos on this problem
Longest Fibonacci Subarray | LeetCode 3708 | Biweekly Contest 167Sanyam IIT Guwahati · 8:54 · 392 views
Leetcode 3708 | Longest Fibonacci Subarray Biweekly Contest 167 Q2Samrat Bhardwaj · 13:28 · 134 views
leetcode 3708 A simple Dynamic Programming Example in Leetcode - Longest Fibonacci SubarrayCode-Yao · 5:26 · 112 views
🧠 Longest Fibonacci Subarray Explained | LeetCode 3708 | Java Solution (Biweekly Contest)Proof2Code · 7:20 · 102 views
BiWeekly Contest 167 Longest Fibonacci SubarrayR Sai Siddhu · 5:36 · 51 views
LeetCode 3708 – Longest Fibonacci Subarray | Biweekly Contest 167Karan · 12:54 · 25 views
LeetCode Weekly #2 | Longest Fibonacci Subarray | #3708Hamd Waseem · 3:18 · 17 views
The problem
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] <= 109
Approach overview
Problem 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.
Solution
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).
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
ans = f = 2
for i in range(2, n):
if nums[i] == nums[i - 1] + nums[i - 2]:
f = f + 1
ans = max(ans, f)
else:
f = 2
return ansclass Solution {
public int longestSubarray(int[] nums) {
int f = 2;
int ans = f;
for (int i = 2; i < nums.length; ++i) {
if (nums[i] == nums[i - 1] + nums[i - 2]) {
++f;
ans = Math.max(ans, f);
} else {
f = 2;
}
}
return ans;
}
}class Solution {
public:
int longestSubarray(vector<int>& nums) {
int f = 2;
int ans = f;
for (int i = 2; i < nums.size(); ++i) {
if (nums[i] == nums[i - 1] + nums[i - 2]) {
++f;
ans = max(ans, f);
} else {
f = 2;
}
}
return ans;
}
};function longestSubarray(nums: number[]): number {
let f = 2;
let ans = f;
for (let i = 2; i < nums.length; ++i) {
if (nums[i] === nums[i - 1] + nums[i - 2]) {
ans = Math.max(ans, ++f);
} else {
f = 2;
}
}
return ans;
}func longestSubarray(nums []int) int {
f := 2
ans := f
for i := 2; i < len(nums); i++ {
if nums[i] == nums[i-1]+nums[i-2] {
f++
ans = max(ans, f)
} else {
f = 2
}
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Longest Fibonacci Subarray easy or hard?
Longest Fibonacci Subarray is generally considered a medium-level array and dynamic programming problem. The logic is straightforward once you recognize the Fibonacci relationship, but identifying the linear scan optimization requires pattern recognition.
Longest Fibonacci Subarray Python/Java solution
The typical Python or Java implementation performs a single loop from index 2 to n-1. For each element, check if nums[i] == nums[i-1] + nums[i-2], update the current length, and maintain the maximum length variable. This implementation follows the O(n) dynamic programming approach.
How to solve Longest Fibonacci Subarray in O(n)?
Traverse the array starting from index 2 and maintain a running length of the current Fibonacci-like segment. If arr[i] equals arr[i-1] + arr[i-2], increase the length; otherwise reset it to 2. Track the maximum length seen during the traversal. This single pass yields O(n) time complexity with constant space.
What is the best approach for Longest Fibonacci Subarray?
The optimal approach uses a dynamic programming style linear scan. While iterating through the array, check whether arr[i] equals arr[i-1] + arr[i-2]. If the condition holds, extend the current Fibonacci subarray length; otherwise reset the length. This runs in O(n) time and O(1) space.
Is Longest Fibonacci Subarray asked at Google/Amazon/Meta?
Fibonacci-pattern array problems appear in interviews at companies like Amazon, Google, and Meta as variations of sequence detection or dynamic programming. Interviewers often test whether candidates can recognize the dependency on previous elements and optimize the solution to linear time.
What data structure is used in Longest Fibonacci Subarray?
The core structure is a simple array traversal combined with a dynamic programming state represented by a running length variable. No additional data structures such as hash maps or sets are required for the optimal solution.
What is the time complexity of Longest Fibonacci Subarray?
The optimal solution runs in O(n) time because the array is scanned once while verifying the Fibonacci condition for each index. The brute force expansion approach can take O(n²) time since it attempts to extend Fibonacci subarrays from every starting pair.