This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1416. Restore The Array, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, prefix sums.
The notes already sitting in the source point us in the right direction:
- TLE
- 25 / 83 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are check, numberOfArrays, count.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//25 / 83 test cases passed.
03class Solution {
04public:
05 int k;
06
07 bool check(string& s, int idx){
08 if(idx != 0){
09 //reserve this case when "s" is at the front of the comb it belongs to
10 //leading 0
11 if(s.size() > 1 && s[0] == '0') return false;
12 }
13
14 //too large
15 if(s.size() > 10 || (s.size() == 10 && s[0] != '1')) return false;
16
17 if(idx != 0){
18 if(stoi(s) >=1 && stoi(s) <= k){
19 return true;
20 }
21 }else{
22 //reserve the case when s is '0'
23 if(stoi(s) <= k){
24 return true;
25 }
26 }
27 return false;
28 };
29
30 bool check(vector<string>& v){
31 for(int i = 0; i < v.size(); i++){
32 if(!check(v[i], i)) return false;
33 }
34 return true;
35 };
36
37 int numberOfArrays(string s, int k) {
38 int n = s.size();
39 this->k = k;
40
41 vector<int> dp(n, 0);
42
43 vector<vector<string>> combs, nextCombs;
44 vector<string> comb;
45
46 for(int i = n-1; i >= 0; i--){
47 if(combs.size() == 0){
48 //haven't found valid comb yet
49 comb.clear();
50 comb.push_back(s.substr(i));
51 if(check(comb)){
52 combs.push_back(comb);
53 }
54 }else{
55 //prefix current char to previous comb
56 // cout << "before: " << endl;
57 // for(vector<string> comb : combs){
58 // for(string& s : comb){
59 // cout << s << "/";
60 // }
61 // cout << " ";
62 // }
63 // cout << endl;
64 for(vector<string> comb : combs){
65 //isolated token
66 vector<string> comb2 = comb;
67 comb2.insert(comb2.begin(), string(1, s[i]));
68 if(check(comb2)){
69 nextCombs.push_back(comb2);
70 }
71 //merge with first token in "combs[i]"
72 comb[0] = string(1, s[i]) + comb[0];
73 if(check(comb)){
74 nextCombs.push_back(comb);
75 }
76 // for(string& s : comb){
77 // cout << s << "/";
78 // }
79 // cout << " ";
80 // for(string& s : comb2){
81 // cout << s << "/";
82 // }
83 // cout << " ";
84 }
85 // cout << endl;
86 combs = nextCombs;
87 nextCombs.clear();
88 }
89 }
90
91 // for(int i = 0; i < combs.size(); i++){
92 // for(string& s : combs[i]){
93 // cout << s << "/";
94 // }
95 // cout << " ";
96 // }
97 // cout << endl;
98
99 return combs.size();
100 }
101};
102
103//DP
104//https://leetcode.com/problems/restore-the-array/discuss/585553/Python-DP-O(len(s)-*-10)-clean-code-with-explanations.
105//Runtime: 980 ms, faster than 13.29% of C++ online submissions for Restore The Array.
106//Memory Usage: 12 MB, less than 100.00% of C++ online submissions for Restore The Array.
107class Solution {
108public:
109 int numberOfArrays(string s, int k) {
110 int n = s.size();
111 int t = to_string(k).size(); //max 10
112 vector<int> count(n+1, 0);
113 count[0] = count[1] = 1;
114 int MOD = 1e9+7;
115 int ans = 0;
116
117 for(int i = 1; i < n ; i++){
118 for(int j = 0; j <= min(i, t-1); j++){
119 // for(int j = i; j >= 0; j--){
120 //s[i-j:i]
121 string sub = s.substr(i-j, j+1);
122 // cout << i-j << " " << i << " sub: " << sub << endl;
123 if(sub[0] == '0') continue;
124 //avoid overflow
125 if(sub.size() >= 10 && s[0] != '1') continue;
126 if(stoi(sub) >= 1 && stoi(sub) <= k){
127 // cout << i+1 << " " << count[i+1] << " " << i-j << " " << count[i-j] << endl;
128 count[i+1] = (count[i+1]%MOD)+(count[i-j]%MOD);
129 }
130 }
131 }
132
133 return count[n] % MOD;
134 }
135};
136
137//1-D DP
138//https://leetcode.com/problems/restore-the-array/discuss/587726/Java-DP-(bottom-up)-16-line-solution-2x100-O(n-log-k)-time-O(n)-space-with-simple-explanation
139//Runtime: 640 ms, faster than 19.77% of C++ online submissions for Restore The Array.
140//Memory Usage: 12 MB, less than 100.00% of C++ online submissions for Restore The Array.
141class Solution {
142public:
143 int numberOfArrays(string s, int k) {
144 int n = s.size();
145 //the max length of valid token
146 int intMaxLen = to_string(INT_MAX).size();
147 int maxLen = min((int)to_string(k).size(), intMaxLen);
148 int MOD = 1e9 + 7;
149 vector<int> dp(n, 0); //count for s[0:end]
150 for(int end = 0; end < n; end++){
151 for(int start = end; start >= 0 && (end-start+1) <= maxLen; start--){
152 //we are looking at s[start:end]
153
154 //leading 0
155 if(s[start] == '0') continue;
156 //[start,end]
157 string sub = s.substr(start, end-start+1);
158 //stoi(sub) must >= 1, don't need to check
159 //same digits as INT_MAX, first check its leading digit
160 if(sub.size() == intMaxLen && sub[0] != '1') continue;
161 //don't need to worry about overflow now
162 if(stoi(sub) > k) continue;
163 /*
164 now s[start:end] is a valid token,
165 meaning s[0:end] can be split into s[0:start-1] and s[start:end],
166 so for s[0:end], its count is increased by the count of s[0:start-1]
167 if start is 0, s[0:end] is a valid token by itself, we only find "one" valid token, so increase one
168 */
169 dp[end] += (start > 0) ? dp[start-1] : 1;
170 dp[end] %= MOD;
171 }
172 // cout << "dp[" << end << "]: " << dp[end] << endl;
173 }
174 return dp[n-1];
175 }
176};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.