Skip to main content
Talentd

Longest Fibonacci Subarray - Solution & Explanation

MediumArray8 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ExpansionO(n²)O(1)Useful for understanding the Fibonacci condition and verifying small inputs
Dynamic Programming / Linear ScanO(n)O(1)Best for interviews and production code when scanning large arrays

Video Solution

Longest Fibonacci Subarray | LeetCode 3708 | Biweekly Contest 167 • Sanyam IIT Guwahati • 392 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Longest Fibonacci Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays