algoadvance

Leetcode 842. Split Array into Fibonacci Sequence

Problem Statement

Given a string num that contains only digits, your task is to split it into a Fibonacci-like sequence, where a sequence is Fibonacci-like if:

  1. num starts with a digit sequence representing the first number in the sequence.
  2. The next sequence of digits forms the second number in the sequence.
  3. The third and subsequent numbers in the sequence are the sum of the preceding two numbers.

The sequence should contain at least three numbers. Return any such sequence in the form of a list of integers, or return an empty list if no such sequence can be constructed.

Here is the function signature:

public List<Integer> splitIntoFibonacci(String num)

Clarifying Questions

  1. Input Size: What is the maximum length of the string num?
    • Answer: The length of the string num can be up to 200 digits.
  2. Leading Zeros: How should we handle numbers in the sequence that have leading zeros?
    • Answer: Numbers in the sequence cannot have leading zeros, except for the number 0 itself.
  3. Constraints on the Numbers: Are the numbers in the Fibonacci sequence restricted by the maximum size of a Java integer?
    • Answer: Yes, they should fit into a 32-bit signed integer, meaning values must be between -2^31 and 2^31 - 1.

Strategy

To solve this problem, we can use a backtracking approach:

  1. Initialization: First, we create a list to store our potential Fibonacci sequence.
  2. Backtracking Function: Define a helper function that tries to form a valid sequence by iterating through the string and checking for valid Fibonacci sequences.
  3. Constraints Check: Ensure that the values being formed are within the 32-bit integer range and do not have invalid leading zeros.
  4. Base Case: If the string is consumed entirely and we have a list of at least three numbers that follows the Fibonacci property, return it. Otherwise, backtrack and try other possibilities.
  5. Pruning: Use constraints (like maximum length of sub-strings to form valid Fibonacci numbers) to prune the recursion tree early when the numbers get too large or invalid.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> result = new ArrayList<>();
        if (backtrack(result, num, num.length(), 0, 0, 0)) {
            return result;
        }
        return new ArrayList<>();
    }
    
    private boolean backtrack(List<Integer> result, String num, int length, int index, long sum, int prev) {
        if (index == length) {
            return result.size() >= 3;
        }
        long currLong = 0;
        for (int i = index; i < length; i++) {
            if (i > index && num.charAt(index) == '0') {
                break;
            }
            currLong = currLong * 10 + num.charAt(i) - '0';
            if (currLong > Integer.MAX_VALUE) {
                break;
            }
            int curr = (int) currLong;
            if (result.size() >= 2) {
                if (curr < sum) {
                    continue;
                } else if (curr > sum) {
                    break;
                }
            }
            result.add(curr);
            if (backtrack(result, num, length, i + 1, prev + curr, curr)) {
                return true;
            }
            result.remove(result.size() - 1);
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.splitIntoFibonacci("123456579")); // Output: [123, 456, 579]
    }
}

Time Complexity

The time complexity of this approach is O(2^N), where N is the length of the input string num. This is because in the worst case, every character in the string could potentially start a new number in the sequence.

Note: To improve efficiency in practice, early pruning helps to skip invalid or impossible segments quickly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI