LeetCode Problem 3708

Difficulty: 🟡 Medium
Topics: Array

Solution

LeetCode 3708 - Longest Fibonacci Subarray

Problem Understanding

The problem gives us an array nums consisting of positive integers and asks us to find the length of the longest contiguous subarray that satisfies the Fibonacci property.

A subarray is a contiguous segment of the original array. For a sequence to be considered Fibonacci, every element from the third position onward must equal the sum of the previous two elements.

For example:

• [1, 1, 2, 3, 5] is Fibonacci because:

• 1 + 1 = 2

• 1 + 2 = 3

• 2 + 3 = 5

• [5, 2, 7, 9, 16] is also Fibonacci because:

• 5 + 2 = 7

• 2 + 7 = 9

• 7 + 9 = 16

An important detail is that subarrays of length 1 or 2 are always considered Fibonacci. This means that even if no three consecutive elements satisfy the Fibonacci condition, the answer will always be at least 2.

The input size can be as large as:

• 3 <= nums.length <= 100000
• 1 <= nums[i] <= 10^9

The array can contain up to one hundred thousand elements, which immediately tells us that quadratic or cubic solutions will be far too slow. We need a linear time solution.

Several edge cases are worth noting:

• Arrays where no three consecutive elements satisfy the Fibonacci property.
• Arrays that are entirely Fibonacci.
• Arrays containing repeated values.
• Arrays containing very large numbers near 10^9.
• Arrays where the longest Fibonacci subarray appears in the middle rather than at the beginning.

Because the Fibonacci condition only involves neighboring elements, we should look for a way to process the array in a single pass.

Approaches

Brute Force

A straightforward approach is to examine every possible subarray.

For each starting index, we extend the subarray one element at a time and check whether every position from the third onward satisfies:

nums[k] == nums[k - 1] + nums[k - 2]

If the condition fails, the current subarray is no longer Fibonacci.

This approach is correct because it explicitly verifies every candidate subarray. However, there are O(n²) subarrays, and validating them can require additional work. In the worst case, the complexity becomes O(n³).

With n = 100000, this is completely impractical.

Key Insight

The Fibonacci condition is local.

To determine whether a Fibonacci run can continue at position i, we only need to check:

nums[i] == nums[i - 1] + nums[i - 2]

If the condition holds, then any Fibonacci subarray ending at i - 1 can be extended by one element.

If the condition fails, the longest Fibonacci subarray ending at i becomes length 2, consisting of the pair:

[nums[i - 1], nums[i]]

This observation allows us to maintain the length of the current Fibonacci run while scanning the array once from left to right.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every subarray and validates each one
Optimal	O(n)	O(1)	Single pass, track current Fibonacci run length

Algorithm Walkthrough

1. Initialize current_length = 2.

Any pair of consecutive elements forms a Fibonacci subarray of length two, so this is the smallest valid length we need to track. 2. Initialize best_length = 2.

Since the array length is at least three, the answer can never be smaller than two. 3. Iterate through the array starting from index 2.

At each position i, check whether:

nums[i] == nums[i - 1] + nums[i - 2]

4. If the condition holds, extend the current Fibonacci run.

Increment:

current_length += 1

Update:

best_length = max(best_length, current_length)

5. If the condition fails, the current run cannot continue.

Reset:

current_length = 2

The pair (nums[i - 1], nums[i]) forms a new Fibonacci subarray of length two. 6. Continue until the end of the array. 7. Return best_length.

Why it works

At every index i, current_length represents the length of the longest Fibonacci subarray ending at position i.

If nums[i] = nums[i - 1] + nums[i - 2], then the Fibonacci property remains valid and the existing run can be extended by one element.

If the equality does not hold, no Fibonacci subarray of length at least three can end at i, so the longest valid subarray ending there is simply the pair (nums[i - 1], nums[i]), which has length two.

Because every position is processed exactly once and we always maintain the correct length of the Fibonacci run ending at the current index, the maximum value observed is the length of the longest Fibonacci subarray in the entire array.

Python Solution

from typing import List

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        current_length = 2
        best_length = 2

        for i in range(2, len(nums)):
            if nums[i] == nums[i - 1] + nums[i - 2]:
                current_length += 1
                best_length = max(best_length, current_length)
            else:
                current_length = 2

        return best_length

The implementation directly follows the algorithm.

The variables current_length and best_length store the length of the current Fibonacci run and the overall maximum found so far.

The loop begins at index 2 because the Fibonacci condition requires two previous elements.

Whenever the current value equals the sum of the previous two values, the run extends by one. Otherwise, the run is broken and must restart with length two.

Since only two integer variables are maintained, the space usage remains constant.

Go Solution

func longestSubarray(nums []int) int {
	currentLength := 2
	bestLength := 2

	for i := 2; i < len(nums); i++ {
		if nums[i] == nums[i-1]+nums[i-2] {
			currentLength++
			if currentLength > bestLength {
				bestLength = currentLength
			}
		} else {
			currentLength = 2
		}
	}

	return bestLength
}

The Go implementation mirrors the Python solution almost exactly.

One consideration is integer overflow. The maximum value in the array is 10^9, so the sum of two adjacent values is at most 2 * 10^9, which still fits comfortably within Go's signed 32 bit integer range. Since Go's int is typically 64 bit on LeetCode platforms, overflow is not a concern.

No additional slices or maps are required, so the space complexity remains constant.

Worked Examples

Example 1

Input:

[1,1,1,1,2,3,5,1]

Initial state:

current_length = 2
best_length = 2

i	nums[i-2]	nums[i-1]	nums[i]	Fibonacci?	current_length	best_length
2	1	1	1	No	2	2
3	1	1	1	No	2	2
4	1	1	2	Yes	3	3
5	1	2	3	Yes	4	4
6	2	3	5	Yes	5	5
7	3	5	1	No	2	5

Result:

5

The longest Fibonacci subarray is:

[1,1,2,3,5]

Example 2

Input:

[5,2,7,9,16]

Initial state:

current_length = 2
best_length = 2

i	nums[i-2]	nums[i-1]	nums[i]	Fibonacci?	current_length	best_length
2	5	2	7	Yes	3	3
3	2	7	9	Yes	4	4
4	7	9	16	Yes	5	5

Result:

5

The entire array is Fibonacci.

Example 3

Input:

[1000000000,1000000000,1000000000]

Initial state:

current_length = 2
best_length = 2

i	nums[i-2]	nums[i-1]	nums[i]	Fibonacci?	current_length	best_length
2	1000000000	1000000000	1000000000	No	2	2

Result:

2

No length-three Fibonacci subarray exists, so the answer remains two.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only a few integer variables are stored

The algorithm performs a single left-to-right scan of the array. Every iteration executes a constant amount of work, producing linear time complexity. No auxiliary data structures whose size depends on n are allocated, so the space complexity is constant.

Test Cases

from typing import List

s = Solution()

assert s.longestSubarray([1, 1, 1, 1, 2, 3, 5, 1]) == 5  # provided example 1
assert s.longestSubarray([5, 2, 7, 9, 16]) == 5  # provided example 2
assert s.longestSubarray([1000000000, 1000000000, 1000000000]) == 2  # provided example 3

assert s.longestSubarray([1, 1, 2]) == 3  # smallest full Fibonacci array
assert s.longestSubarray([1, 2, 4]) == 2  # no valid length-3 Fibonacci run
assert s.longestSubarray([1, 1, 2, 3, 5, 8, 13]) == 7  # entire array Fibonacci
assert s.longestSubarray([1, 2, 3, 5, 8, 1, 2]) == 5  # Fibonacci run at start
assert s.longestSubarray([9, 9, 1, 1, 2, 3, 5]) == 5  # Fibonacci run at end
assert s.longestSubarray([1, 1, 2, 7, 1, 1, 2, 3]) == 4  # restart after break
assert s.longestSubarray([2, 2, 4, 6, 10, 16, 26]) == 7  # non-classical Fibonacci sequence
assert s.longestSubarray([7, 7, 7, 7, 7]) == 2  # all equal values
assert s.longestSubarray([1, 1, 2, 3, 5, 9, 14, 23]) == 4  # longest run in middle

Test Summary

Test	Why
[1,1,1,1,2,3,5,1]	Provided example with run in middle
[5,2,7,9,16]	Entire array is Fibonacci
[1000000000,1000000000,1000000000]	Large values, no valid length-3 run
[1,1,2]	Smallest valid Fibonacci array
[1,2,4]	Answer remains 2
[1,1,2,3,5,8,13]	Long Fibonacci sequence
[1,2,3,5,8,1,2]	Run appears at start
[9,9,1,1,2,3,5]	Run appears at end
[1,1,2,7,1,1,2,3]	Run reset and restart
[2,2,4,6,10,16,26]	Generic Fibonacci pattern
[7,7,7,7,7]	Repeated values
[1,1,2,3,5,9,14,23]	Longest run not covering whole array

Edge Cases

No Valid Length-Three Fibonacci Subarray

An array such as:

[1, 2, 4]

never satisfies the Fibonacci condition because 1 + 2 != 4. A buggy implementation might incorrectly return 1 or 0. The problem explicitly states that every subarray of length two is Fibonacci, so the correct answer is 2. The algorithm naturally handles this by initializing both lengths to 2.

Entire Array Is Fibonacci

Consider:

[1, 1, 2, 3, 5, 8, 13]

Every new element extends the existing run. The algorithm keeps increasing current_length and eventually returns the full array length. No special handling is required because the extension rule works uniformly throughout the scan.

Multiple Independent Fibonacci Runs

Consider:

[1, 1, 2, 7, 1, 1, 2, 3]

The first Fibonacci run has length three, then the sequence breaks at 7. A common bug is failing to reset state correctly after a break. The algorithm immediately resets current_length to 2, allowing a new run to start and correctly discover the later Fibonacci subarray of length four.

Large Integer Values

Consider:

[1000000000, 1000000000, 1000000000]

The values are near the upper constraint limit. Since the algorithm only performs one addition per iteration and the maximum possible sum is 2 * 10^9, arithmetic remains safe. Both Python and Go handle these values without overflow issues in the context of this problem.