Split Array into Fibonacci Sequence solution and explanation
Google
8 more videos on this problem
Leetcode 842 | Split Array into Fibonacci Sequence | PayPal Interview Question (Java Solution)The Tech Granth · 15:00 · 4K views
LeetCode 842. Split Array into Fibonacci Sequence Explanation and Solutionhappygirlzt · 7:05 · 3K views
花花酱 LeetCode 842. Split Array into Fibonacci Sequence - 刷题找工作 EP296Hua Hua · 14:44 · 2K views
LeetCode 842. Split Array into Fibonacci Sequence 中文解释 Chinese Versionhappygirlzt · 9:39 · 732 views
LeetCode - 842. Split Array into Fibonacci Sequence | Backtracking | JavaOrkhan Gasanov · 14:14 · 528 views
Leetcode 842. Split Array into Fibonacci Sequence (backtracking)LetsCode · 11:17 · 326 views
No Sound Leetcode 842: Split Array into Fibonacci SequenceExtremeProgrammer · 2:51 · 35 views
Split Array into Fibonacci Sequence - LeetCode 842 Solution ExplainedCodeLucky · 3:43 · 33 views
LeetCode 842: Split Array into Fibonacci SequenceAlitaCode · 27:56 · 10 views
The problem
You are given a string of digits num, such as "123456579". We can split it into a Fibonacci-like sequence [123, 456, 579].
Formally, a Fibonacci-like sequence is a list f of non-negative integers such that:
0 <= f[i] < 231, (that is, each integer fits in a 32-bit signed integer type),f.length >= 3, andf[i] + f[i + 1] == f[i + 2]for all0 <= i < f.length - 2.
Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.
Return any Fibonacci-like sequence split from num, or return [] if it cannot be done.
Example 1:
Input: num = "1101111" Output: [11,0,11,11] Explanation: The output [110, 1, 111] would also be accepted.
Example 2:
Input: num = "112358130" Output: [] Explanation: The task is impossible.
Example 3:
Input: num = "0123" Output: [] Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
Constraints:
1 <= num.length <= 200numcontains only digits.
Approach overview
Problem Overview: You receive a numeric string and must split it into a sequence of integers that forms a valid Fibonacci sequence. Each number must equal the sum of the previous two, contain no leading zeros (unless the number is 0), and fit within a 32‑bit signed integer.
Approach 1: Backtracking and Recursion (Time: O(n^3), Space: O(n))
This approach tries every possible split for the first two numbers, then recursively checks whether the rest of the string can extend the Fibonacci sequence. Start by choosing indices i and j to define the first two numbers. From there, compute the expected next value as a + b and check whether the string starting at the current index begins with that value. If it matches, append it to the sequence and continue recursively. The backtracking stops early when a number exceeds the 32‑bit integer limit or when the substring does not match the required Fibonacci sum. Time complexity is roughly O(n^3) in the worst case due to trying splits and substring comparisons, while space complexity is O(n) for the recursion stack and sequence storage. This approach directly models the sequence-building process and is commonly implemented using backtracking over a string.
Approach 2: Iterative Parsing with Dynamic Updates (Time: O(n^2), Space: O(n))
This method removes recursion and builds the sequence iteratively. Loop over possible lengths for the first and second numbers, parse them, and then repeatedly compute the next expected Fibonacci value. Convert the sum to a string and check whether the remaining substring begins with that value. If it matches, advance the pointer and continue generating numbers until the string is consumed. The key optimization is avoiding repeated branching: once the first two numbers are fixed, the rest of the sequence is deterministic. Time complexity becomes about O(n^2) because you only try combinations of the first two numbers and then extend linearly. Space complexity remains O(n) to store the resulting sequence. This iterative approach works well in languages like Java or C# where explicit control over parsing and bounds checking is convenient.
Recommended for interviews: The backtracking approach demonstrates understanding of search space pruning and constraint handling. However, interviewers often prefer the iterative extension method because once the first two numbers are chosen the rest of the sequence is forced, reducing unnecessary recursion. Showing both reasoning paths—brute exploration followed by deterministic extension—demonstrates strong problem-solving depth.
Approach 1: Backtracking and Recursion
This approach uses backtracking to recursively split the string into all potential combinations of integers and checks if they form a valid Fibonacci sequence.
- Start by selecting the first and second numbers of potential Fibonacci sequences.
- Iterate over possible splits of the input string and recursively check if they form a valid sequence of numbers.
- Use constraints to handle leading zeroes and integer size limits.
def splitIntoFibonacci(S):
def backtrack(index):
if index == len(S):
return len(result) >= 3
current_number = 0
for i in range(index, len(S)):
if i > index and S[index] == '0':
break
current_number = current_number * 10 + int(S[i])
if current_number > 2**31 - 1:
break
if len(result) < 2 or current_number == result[-1] + result[-2]:
result.append(current_number)
if backtrack(i + 1):
return True
result.pop()
return False
result = []
return result if backtrack(0) else []function splitIntoFibonacci(S) {
const result = [];
function backtrack(index) {
if (index === S.length) return result.length >= 3;
let currentNumber = 0;
for (let i = index; i < S.length; i++) {
if (i > index && S[index] === '0') break;
currentNumber = currentNumber * 10 + (S[i] - '0');
if (currentNumber > Math.pow(2, 31) - 1) break;
if (result.length < 2 || currentNumber === result[result.length - 1] + result[result.length - 2]) {
result.push(currentNumber);
if (backtrack(i + 1)) return true;
result.pop();
}
}
return false;
}
return backtrack(0) ? result : [];
}This Python code implements a backtracking solution to split the input string into potential Fibonacci sequences.
- A helper function
backtrackis defined to recursively attempt to form a sequence. - The recursion terminates successfully if a valid sequence is found.
- Caution is taken to handle leading zeroes and ensure numbers fit within 32-bit signed integer limits.
Time Complexity: O(2^n), since each combination of splitting points is considered recursively.
Space Complexity: O(n), for the recursion stack and the result list.
Approach 2: Iterative Parsing with Dynamic Updates
This approach involves iteratively parsing possible substrings and dynamically checking for valid Fibonacci sequences.
- Convert parts of the input string into potential Fibonacci numbers iteratively.
- Maintain an in-progress list of numbers and update it as the sequence grows.
- Check constraints like leading zeroes and integer limits at each step.
import java.util.*;
public class FibonacciSplitter {
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < S.length() - 2; ++i) {
if (i > 0 && S.charAt(0) == '0') break;
long a = Long.parseLong(S.substring(0, i+1));
if (a > Integer.MAX_VALUE) break;
result.add((int) a);
for (int j = i + 1; j < S.length() - 1; ++j) {
if (j > i + 1 && S.charAt(i+1) == '0') break;
long b = Long.parseLong(S.substring(i+1, j+1));
if (b > Integer.MAX_VALUE) break;
result.add((int) b);
if (isValid(S.substring(j+1), result)) return result;
result.remove(result.size() - 1);
}
result.remove(result.size() - 1);
}
return new ArrayList<>();
}
private boolean isValid(String S, List<Integer> result) {
int n1 = result.get(result.size() - 2);
int n2 = result.get(result.size() - 1);
for (int k = 0; k < S.length(); k++) {
long next = (long)n1 + n2;
if (next > Integer.MAX_VALUE) return false;
String nextString = String.valueOf(next);
if (!S.startsWith(nextString)) return false;
n1 = n2;
n2 = (int) next;
k += nextString.length() - 1;
}
return true;
}
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> SplitIntoFibonacci(string S) {
var result = new List<int>();
for (int i = 0; i < S.Length - 2; i++) {
if (i > 0 && S[0] == '0') break;
long a = long.Parse(S.Substring(0, i + 1));
if (a > int.MaxValue) break;
result.Add((int)a);
for (int j = i + 1; j < S.Length - 1; j++) {
if (j > i + 1 && S[i + 1] == '0') break;
long b = long.Parse(S.Substring(i + 1, j + 1 - (i + 1)));
if (b > int.MaxValue) break;
result.Add((int)b);
if (IsValid(S.Substring(j + 1), result)) return result;
result.RemoveAt(result.Count - 1);
}
result.RemoveAt(result.Count - 1);
}
return new List<int>();
}
private bool IsValid(string S, List<int> result) {
int n1 = result[result.Count - 2];
int n2 = result[result.Count - 1];
for (int k = 0; k < S.Length; k++) {
long next = (long)n1 + n2;
if (next > int.MaxValue) return false;
string nextString = next.ToString();
if (!S.StartsWith(nextString)) return false;
n1 = n2;
n2 = (int)next;
k += nextString.Length - 1;
}
return true;
}
}This Java code uses an iterative method to find Fibonacci-like sequences.
- Two loops generate and validate potential Fibonacci starting sequences.
- The
isValidfunction checks if extending the sequence remains valid. - Integer parsing ensures numbers adhere to 32-bit limits.
Time Complexity: O(n^3), due to nested loops exploring potential splits and sequence validity.
Space Complexity: O(n), primarily to store intermediate sequence results.
Approach 3: Default Approach
class Solution {
public:
vector<int> splitIntoFibonacci(string num) {
int n = num.size();
vector<int> ans;
function<bool(int)> dfs = [&](int i) -> bool {
if (i == n) {
return ans.size() > 2;
}
long long x = 0;
for (int j = i; j < n; ++j) {
if (j > i && num[i] == '0') {
break;
}
x = x * 10 + num[j] - '0';
if (x > INT_MAX || (ans.size() > 1 && x > (long long) ans[ans.size() - 1] + ans[ans.size() - 2])) {
break;
}
if (ans.size() < 2 || x == (long long) ans[ans.size() - 1] + ans[ans.size() - 2]) {
ans.push_back(x);
if (dfs(j + 1)) {
return true;
}
ans.pop_back();
}
}
return false;
};
dfs(0);
return ans;
}
};func splitIntoFibonacci(num string) []int {
n := len(num)
ans := []int{}
var dfs func(int) bool
dfs = func(i int) bool {
if i == n {
return len(ans) > 2
}
x := 0
for j := i; j < n; j++ {
if j > i && num[i] == '0' {
break
}
x = x*10 + int(num[j]-'0')
if x > math.MaxInt32 || (len(ans) > 1 && x > ans[len(ans)-1]+ans[len(ans)-2]) {
break
}
if len(ans) < 2 || x == ans[len(ans)-1]+ans[len(ans)-2] {
ans = append(ans, x)
if dfs(j + 1) {
return true
}
ans = ans[:len(ans)-1]
}
}
return false
}
dfs(0)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking and Recursion | Time Complexity: O(2^n), since each combination of splitting points is considered recursively. Space Complexity: O(n), for the recursion stack and the result list. |
| Iterative Parsing with Dynamic Updates | Time Complexity: O(n^3), due to nested loops exploring potential splits and sequence validity. Space Complexity: O(n), primarily to store intermediate sequence results. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking and Recursion | O(n^3) | O(n) | When exploring all valid splits and demonstrating recursive pruning in interviews |
| Iterative Parsing with Dynamic Updates | O(n^2) | O(n) | Preferred approach once the first two numbers are fixed and the sequence becomes deterministic |
Frequently asked questions
Is Split Array into Fibonacci Sequence easy or hard?
Split Array into Fibonacci Sequence is considered a Medium problem on LeetCode. The difficulty comes from managing multiple constraints: avoiding leading zeros, respecting 32-bit integer limits, and efficiently validating Fibonacci growth while parsing the string.
Split Array into Fibonacci Sequence Python/Java solution
Python solutions typically use backtracking with recursion and substring checks to build the sequence. Java implementations often prefer iterative parsing where the first two numbers are selected and the rest of the sequence is generated using loops and integer parsing.
How to solve Split Array into Fibonacci Sequence in O(n)?
A strict O(n) solution is generally not possible because the algorithm must try different splits for the first two numbers. The optimal practical approach is O(n^2), where you iterate over possible first and second numbers and then extend the Fibonacci sequence deterministically.
What is the best approach for Split Array into Fibonacci Sequence?
The most practical approach fixes the first two numbers and then iteratively generates the rest of the sequence. Once those two numbers are chosen, every following value must equal their sum, making the sequence deterministic. This reduces branching and runs in about O(n^2) time with O(n) space.
Is Split Array into Fibonacci Sequence asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Google, Amazon, and Meta because it combines string parsing, backtracking, and number constraints. Interviewers use it to evaluate pruning strategies and careful handling of integer limits and leading zeros.
What data structure is used in Split Array into Fibonacci Sequence?
The solution primarily uses arrays or lists to store the current Fibonacci sequence and string operations to parse numbers from the input. Backtracking solutions rely on recursion stacks, while iterative solutions maintain a dynamic list of generated values.
What is the time complexity of Split Array into Fibonacci Sequence?
The typical solution runs in O(n^2) to O(n^3) time depending on implementation. Choosing the first two numbers requires O(n^2) combinations, and extending the sequence requires linear checks of the remaining string. Space complexity is O(n) for storing the sequence.