Watch 8 video solutions for Longest Fibonacci Subarray, a medium level problem involving Array. This walkthrough by Sanyam IIT Guwahati has 387 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |