Restore The Array

Hard

#1310Time: Exponential, roughly O(2^N) in the worst case. The function `solve(i)` can call `solve(i+1), solve(i+2), ...`, leading to a large number of overlapping subproblems.Space: O(N), where N is the length of the string `s`. This is for the recursion call stack depth.

Patterns

Dynamic Programming

Data structures

String

Prompt

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

Constraints:

1 <= s.length <= 10⁵
s consists of only digits and does not contain leading zeros.
1 <= k <= 10⁹

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's partitioning nature into a recursive structure. We define a function that explores all possible ways to split the string from a given starting position. For each position, we try to form a valid number by taking one or more digits. If a valid number is formed, we recursively call the function for the rest of the string. The total number of ways is the sum of ways from all valid splits.

Algorithm

Define a recursive function, say solve(index), that calculates the number of ways to parse the suffix of the string s starting from index.
Base Case: If index reaches the end of the string (s.length()), it means we have successfully found one valid partition. Return 1.
Recursive Step: For the current index: a. If s.charAt(index) is '0', no valid number can be formed. Return 0. b. Initialize a counter for the number of ways, count = 0. c. Iterate from j = index to s.length() - 1 to form substrings s[index...j]. d. Convert the substring to a number. Let's call it num. e. If num is greater than k, any longer substring starting at index will also be greater than k. So, break the loop. f. If 1 <= num <= k, we have found a valid number. This means we can make a partition here. The number of ways to partition the rest of the string s[j+1:] is given by solve(j + 1). Add this to count. g. Remember to perform calculations modulo 10^9 + 7.
Return the final count.
The initial call to the function will be solve(0).

Walkthrough

The core idea is to define a function solve(i) which computes the number of ways to decode the suffix of the string s starting at index i. The final answer is solve(0).

To compute solve(i), we can try to form the first number of the partition. This number can be s[i], s[i...i+1], s[i...i+2], and so on. For each potential first number, say formed by s[i...j], we check if it's valid. A number is valid if it's within the range [1, k] and doesn't have a leading zero. Since the problem statement guarantees s itself doesn't start with '0', we only need to check for leading zeros in subsequent partitions (i.e., if s[i] is '0'). If s[i] is '0', no valid partition can start from i, so solve(i) is 0.

If the number from s[i...j] is valid, we've found one valid way to form the first number. The remaining problem is to find how many ways the rest of the string, s[j+1:], can be partitioned. This is exactly what solve(j+1) calculates. So, we add solve(j+1) to our total for solve(i). We sum this over all valid j.

The base case for the recursion is when we have successfully parsed the entire string, i.e., when i == s.length(). This counts as one valid way, so we return 1.

1class Solution {2    private int MOD = 1_000_000_007;3    private String s;4    private int k;5 6    public int numberOfArrays(String s, int k) {7        this.s = s;8        this.k = k;9        return solve(0);10    }11 12    private int solve(int index) {13        if (index == s.length()) {14            return 1; // Found a valid partition15        }16        if (s.charAt(index) == '0') {17            return 0; // Numbers cannot have leading zeros18        }19 20        long count = 0;21        long num = 0;22        for (int j = index; j < s.length(); j++) {23            num = num * 10 + (s.charAt(j) - '0');24            if (num > k) {25                break; // Number is too large, no need to check longer numbers26            }27            count = (count + solve(j + 1)) % MOD;28        }29        return (int) count;30    }31}

Complexity

Time

Exponential, roughly O(2^N) in the worst case. The function `solve(i)` can call `solve(i+1), solve(i+2), ...`, leading to a large number of overlapping subproblems.

Space

O(N), where N is the length of the string `s`. This is for the recursion call stack depth.

Trade-offs

Pros

Simple to conceptualize and implement based on the problem definition.

Cons

Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error for larger inputs.

The brute-force recursive solution is slow because it repeatedly solves the same subproblems. For example, solve(5) might be called when partitioning s[0:], s[1:], s[2:], etc. We can significantly optimize this by storing the result of each subproblem solve(i) the first time it's computed and reusing the stored result for subsequent calls. This technique is called memoization, which is a form of top-down dynamic programming.

Algorithm

Use the same recursive structure as the brute-force approach.
Create a memoization array, memo, of size N (where N is the length of s), to store the results of solve(index). Initialize it with a value indicating that the state has not been computed (e.g., -1).
In the recursive function solve(index): a. First, check if memo[index] already contains a computed result. If so, return it immediately. b. If not, compute the result as in the brute-force approach. c. Before returning the computed result, store it in memo[index] for future use.
The rest of the logic remains the same.

Walkthrough

We augment the recursive solution with a memoization table, typically an array memo, to store the results of solve(i). The memo array is initialized with a sentinel value (like -1) to indicate that a subproblem has not yet been solved.

When solve(i) is called, it first checks memo[i]. If memo[i] is not the sentinel value, it means we've already computed the answer for the suffix s[i:], so we can just return the stored value. Otherwise, we proceed with the computation as before. Once the result is computed, we store it in memo[i] before returning. This ensures that each distinct subproblem solve(i) is computed only once.

1class Solution {2    private int MOD = 1_000_000_007;3    private String s;4    private int k;5    private int[] memo;6 7    public int numberOfArrays(String s, int k) {8        this.s = s;9        this.k = k;10        this.memo = new int[s.length()];11        java.util.Arrays.fill(memo, -1);12        return solve(0);13    }14 15    private int solve(int index) {16        if (index == s.length()) {17            return 1;18        }19        if (s.charAt(index) == '0') {20            return 0;21        }22        if (memo[index] != -1) {23            return memo[index];24        }25 26        long count = 0;27        long num = 0;28        for (int j = index; j < s.length(); j++) {29            num = num * 10 + (s.charAt(j) - '0');30            if (num > k) {31                break;32            }33            count = (count + solve(j + 1)) % MOD;34        }35        36        return memo[index] = (int) count;37    }38}

Complexity

Time

O(N * log K). Each state `dp[i]` is computed once. The loop to compute `dp[i]` runs at most `d` times, where `d` is the number of digits in `k` (i.e., `d` is approximately `log10(K)`). Any number with more digits than `k` will be larger than `k`.

Space

O(N) for both the recursion stack and the memoization array.

Trade-offs

Pros

Drastically improves time complexity, making it efficient enough to pass the given constraints.
Maintains the logical structure of the recursive solution, making it relatively easy to implement.

Cons

Uses O(N) extra space for the memoization table.
For very deep recursion (large N), it might lead to a StackOverflowError, although this is less common in modern systems for N=10^5.

This approach is the iterative, or bottom-up, version of the dynamic programming solution. It eliminates recursion, which can prevent stack overflow issues and sometimes offers a slight performance improvement due to the removal of function call overhead. We build the solution from the smallest subproblems to the largest. The subproblem dp[i] (number of ways to parse s[i:]) is solved using the results of already solved subproblems dp[j] where j > i.

Algorithm

Create a DP array, dp, of size N+1. dp[i] will store the number of ways to parse the suffix s[i:].
Base Case: Initialize dp[N] = 1. This signifies that there is one way to parse an empty string (the empty partition).
Iteration: Loop i from N-1 down to 0. a. If s.charAt(i) is '0', set dp[i] = 0 and continue to the next i. b. Otherwise, initialize dp[i] = 0. c. Start forming a number num from s[i]. Iterate with j from i to N-1. d. In each step of the inner loop, update num with the next digit s.charAt(j). e. If num exceeds k, break the inner loop. f. If num is valid, add dp[j+1] to dp[i]. dp[j+1] contains the pre-computed number of ways to parse the rest of the string. g. Perform additions modulo 10^9 + 7.
Result: The final answer is dp[0], which is the number of ways to parse the entire string s[0:].

Walkthrough

We define a dp array where dp[i] holds the number of ways to restore the array from the suffix s[i:]. The size of this array will be N+1.

The base case is dp[N] = 1, as there's one way to parse an empty suffix (by doing nothing). We then iterate backward from i = N-1 to 0. For each i, we calculate dp[i] by considering all possible first numbers that can be formed starting at s[i].

For each i, we iterate j from i to N-1, forming a number from the substring s[i...j]. If this number is valid (i.e., 1 <= num <= k and no leading zero), we can make a cut after j. The number of ways to parse the rest of the string s[j+1:] is already computed and stored in dp[j+1]. We add this to the total for dp[i]. We continue this process until the number formed exceeds k or we reach the end of the string.

1class Solution {2    public int numberOfArrays(String s, int k) {3        int n = s.length();4        int MOD = 1_000_000_007;5        int[] dp = new int[n + 1];6        dp[n] = 1; // Base case: one way to parse an empty string7 8        for (int i = n - 1; i >= 0; i--) {9            if (s.charAt(i) == '0') {10                dp[i] = 0;11                continue;12            }13 14            long num = 0;15            long count = 0;16            for (int j = i; j < n; j++) {17                num = num * 10 + (s.charAt(j) - '0');18                if (num > k) {19                    break;20                }21                count = (count + dp[j + 1]) % MOD;22            }23            dp[i] = (int) count;24        }25 26        return dp[0];27    }28}

Complexity

Time

O(N * log K). The outer loop runs N times, and the inner loop runs at most `d = log10(K)` times.

Space

O(N) for the DP array.

Trade-offs

Pros

Avoids recursion and potential stack overflow errors.
Often slightly more performant than memoization due to no recursion overhead.
Clear and systematic way to build the solution from base cases.

Cons

Uses O(N) space, which might be a concern for extremely large N, although it's acceptable for the given constraints.

This approach optimizes the space complexity of the bottom-up DP solution. By analyzing the dependencies in the DP recurrence relation, dp[i] = sum(dp[j+1]), we notice that dp[i] only depends on states dp[j+1] where the length of the number s[i...j] is at most d = log10(K). This means j is at most i+d-1, so dp[i] depends only on dp[i+1] through dp[i+d]. Instead of keeping the entire O(N) DP table, we only need to maintain a sliding window of d+1 most recent values.

Algorithm

Let d be the number of digits in k. Any valid number formed from s cannot have more than d digits.
We observe that dp[i] depends only on dp[i+1], dp[i+2], ..., dp[i+d]. This means we only need to store the last d+1 values of the DP table at any time.
Create a smaller DP array, dp_opt, of size d+1.
We will use this array as a circular buffer. dp_opt[i % (d+1)] will store the value for dp[i].
Base Case: Initialize dp_opt[N % (d+1)] = 1.
Iteration: Loop i from N-1 down to 0. a. Calculate the value for dp[i] using the same logic as the standard bottom-up DP. b. When you need dp[j+1], access it from the circular array as dp_opt[(j+1) % (d+1)]. c. Store the final computed value for dp[i] in dp_opt[i % (d+1)].
Result: The final answer is dp_opt[0 % (d+1)].

Walkthrough

The time complexity of the bottom-up DP is efficient, but the O(N) space can be improved. The calculation of dp[i] requires values dp[i+1], dp[i+2], ... up to dp[i+d], where d is the number of digits in k. We don't need dp[i+d+1] or any subsequent values. This suggests we can use a space-optimized DP table of size d+1 that acts as a circular array.

We can use the modulo operator to map an index i from the original O(N) DP table to an index in our O(d) table. For example, dp[i] is stored at dp_opt[i % (d+1)]. The logic for calculating the DP value at each step remains identical to the standard bottom-up approach, but all accesses to the DP table are mapped through the modulo operator. This reduces the space complexity from O(N) to O(d), which is O(log K). Since k <= 10^9, d is at most 10, making the space usage constant and very small.

1class Solution {2    public int numberOfArrays(String s, int k) {3        int n = s.length();4        int MOD = 1_000_000_007;5        int d = String.valueOf(k).length();6        7        // dp_opt will store the last d+1 values of our DP table.8        int[] dp_opt = new int[d + 1];9        dp_opt[n % (d + 1)] = 1; // Base case10 11        for (int i = n - 1; i >= 0; i--) {12            int i_mod = i % (d + 1);13            dp_opt[i_mod] = 0; // Reset for current calculation14 15            if (s.charAt(i) == '0') {16                continue;17            }18 19            long num = 0;20            long count = 0;21            for (int j = i; j < n; j++) {22                // Optimization: a number with more digits than k is always larger.23                if (j - i + 1 > d) {24                    break;25                }26                num = num * 10 + (s.charAt(j) - '0');27                if (num > k) {28                    break;29                }30                int j_mod = (j + 1) % (d + 1);31                count = (count + dp_opt[j_mod]) % MOD;32            }33            dp_opt[i_mod] = (int) count;34        }35 36        return dp_opt[0];37    }38}

Complexity

Time

O(N * log K). The time complexity is identical to the non-space-optimized DP approaches.

Space

O(log K). The size of the DP array is proportional to the number of digits in `k`.

Trade-offs

Pros

Most efficient solution in terms of space complexity.
Maintains the optimal time complexity.

Cons

The implementation is slightly more complex due to managing indices in the circular array.

Solutions

Solution

1class Solution {2public3  int numberOfArrays(String s, int k) {4    final int MODULO = 1000000007;5    int length = s.length();6    int kLength = String.valueOf(k).length();7    int[] dp = new int[length];8    dp[0] = 1;9    for (int i = 1; i < length; i++) {10      if (i < kLength && Long.parseLong(s.substring(0, i + 1)) <= (long)k)11        dp[i]++;12      int min = Math.max(0, i - kLength);13      for (int j = min; j < i; j++) {14        if (s.charAt(j + 1) == '0')15          continue;16        long curNum = Long.parseLong(s.substring(j + 1, i + 1));17        if (curNum <= (long)k)18          dp[i] = (dp[i] + dp[j]) % MODULO;19      }20    }21    return dp[length - 1];22  }23}

1// OJ: https://leetcode.com/problems/restore-the-array/ // Time: O(N^2) // Space: O(N) class Solution { typedef long long LL ; public: int numberOfArrays ( string s , int k ) { if ( s [ 0 ] - '0' > k ) return 0 ; int cnt = 0 , tmp = k ; while ( tmp ) { tmp /= 10 ; ++ cnt ; } int N = s . size (), mod = 1e9 + 7 ; vector < int > dp ( N + 1 ); dp [ 0 ] = dp [ 1 ] = 1 ; for ( int i = 2 ; i <= N ; ++ i ) { LL p = 1 , n = 0 ; for ( int j = i - 1 ; j >= 0 ; -- j ) { n += ( s [ j ] - '0' ) * p ; p *= 10 ; if ( n > k || i - j > cnt ) break ; if ( n == 0 || s [ j ] == '0' ) continue ; dp [ i ] = ( dp [ i ] + dp [ j ]) % mod ; } } return dp [ N ]; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int numberOfArrays(String s, int k) {4    final int MODULO = 1000000007;5    int length = s.length();6    int kLength = String.valueOf(k).length();7    int[] dp = new int[length];8    dp[0] = 1;9    for (int i = 1; i < length; i++) {10      if (i < kLength && Long.parseLong(s.substring(0, i + 1)) <= (long)k)11        dp[i]++;12      int min = Math.max(0, i - kLength);13      for (int j = min; j < i; j++) {14        if (s.charAt(j + 1) == '0')15          continue;16        long curNum = Long.parseLong(s.substring(j + 1, i + 1));17        if (curNum <= (long)k)18          dp[i] = (dp[i] + dp[j]) % MODULO;19      }20    }21    return dp[length - 1];22  }23}

1// OJ: https://leetcode.com/problems/restore-the-array/ // Time: O(N^2) // Space: O(N) class Solution { typedef long long LL ; public: int numberOfArrays ( string s , int k ) { if ( s [ 0 ] - '0' > k ) return 0 ; int cnt = 0 , tmp = k ; while ( tmp ) { tmp /= 10 ; ++ cnt ; } int N = s . size (), mod = 1e9 + 7 ; vector < int > dp ( N + 1 ); dp [ 0 ] = dp [ 1 ] = 1 ; for ( int i = 2 ; i <= N ; ++ i ) { LL p = 1 , n = 0 ; for ( int j = i - 1 ; j >= 0 ; -- j ) { n += ( s [ j ] - '0' ) * p ; p *= 10 ; if ( n > k || i - j > cnt ) break ; if ( n == 0 || s [ j ] == '0' ) continue ; dp [ i ] = ( dp [ i ] + dp [ j ]) % mod ; } } return dp [ N ]; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.