Skip to main content
Talentd

Split Array into Fibonacci Sequence - Solution & Explanation

MediumStringBacktracking10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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, and
  • f[i] + f[i + 1] == f[i + 2] for all 0 <= 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 <= 200
  • num contains 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.

This Python code implements a backtracking solution to split the input string into potential Fibonacci sequences.

  • A helper function backtrack is 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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

This Java code uses an iterative method to find Fibonacci-like sequences.

  • Two loops generate and validate potential Fibonacci starting sequences.
  • The isValid function checks if extending the sequence remains valid.
  • Integer parsing ensures numbers adhere to 32-bit limits.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking and RecursionO(n^3)O(n)When exploring all valid splits and demonstrating recursive pruning in interviews
Iterative Parsing with Dynamic UpdatesO(n^2)O(n)Preferred approach once the first two numbers are fixed and the sequence becomes deterministic

Video Solution

Leetcode 842 | Split Array into Fibonacci Sequence | PayPal Interview Question (Java Solution) • The Tech Granth • 4,217 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Split Array into Fibonacci Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Additive Number

Next

Fibonacci Number