This problem looks busy at first, but the accepted solution is built around one steady invariant. For 413. Arithmetic Slices, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- DP
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are numberOfArithmeticSlices, slices.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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^2), space: O(1)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//Runtime: 212 ms, faster than 5.27% of C++ online submissions for Arithmetic Slices.
03//Memory Usage: 149.1 MB, less than 6.25% of C++ online submissions for Arithmetic Slices.
04class Solution {
05public:
06 int numberOfArithmeticSlices(vector<int>& A) {
07 int n = A.size();
08 vector<vector<int>> dp(n, vector(n, INT_MIN));
09 int ans = 0;
10
11 for(int w = 2; w <= n; w++){
12 for(int l = 0; l+w-1 < n; l++){
13 int r = l+w-1;
14 //base case
15 if(w == 2){
16 // cout << l << ", " << r << endl;
17 dp[l][r] = A[r] - A[l];
18 }else{
19 if((dp[l+1][r] != INT_MIN) && (dp[l+1][r] == dp[l][r-1])){
20 /*
21 [l...r] is valid only if
22 windows of size w-1 are valid,
23 and the two windows' common differences are same
24 */
25 dp[l][r] = dp[l+1][r]+1;
26 }
27 if(dp[l][r] != INT_MIN){
28 // cout << l << ", " << r << endl;
29 ans++;
30 }
31 }
32 }
33 }
34
35 return ans;
36 }
37};
38
39//Approach #2 Better Brute Force
40//time: O(N^2), space: O(1)
41class Solution {
42public:
43 int numberOfArithmeticSlices(vector<int>& A) {
44 int ans = 0;
45 int n = A.size();
46
47 for(int l = 0; l+2 < n; l++){
48 int d = A[l+1] - A[l];
49 //looking at [l...l+2], [l...l+3], [l...l+4], [l...n-1]
50 for(int r = l+2; r < n; r++){
51 //only check last pair to determine if a slice is valid
52 if(A[r] - A[r-1] == d){
53 ans++;
54 }else{
55 //skip all [l...r+1], ... [l...n-1] if [l...r] is invalid
56 break;
57 }
58 }
59 }
60
61 return ans;
62 }
63};
64
65//Recursion?
66//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Arithmetic Slices.
67//Memory Usage: 8 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
68//time: O(N), space: O(N)
69class Solution {
70public:
71 int sum = 0;
72
73 int slices(vector<int>& A, int i){
74 if(i < 2) return 0;
75 int ap = 0;
76 if(A[i] - A[i-1] == A[i-1] - A[i-2]){
77 /*
78 A[0...i]'s subsequence's count is that of A[0...i-1] + 1
79 */
80 ap = 1 + slices(A, i-1);
81 sum += ap;
82 }else{
83 slices(A, i-1);
84 }
85 // cout << i << ", " << ap << ", " << sum << endl;
86 return ap;
87 };
88
89 int numberOfArithmeticSlices(vector<int>& A) {
90 slices(A, A.size()-1);
91 return sum;
92 }
93};
94
95//1-D DP
96//Runtime: 4 ms, faster than 45.89% of C++ online submissions for Arithmetic Slices.
97//Memory Usage: 7.5 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
98//time: O(N), space: O(N)
99class Solution {
100public:
101 int numberOfArithmeticSlices(vector<int>& A) {
102 int n = A.size();
103 vector<int> dp(n);
104 int ans = 0;
105
106 for(int r = 2; r < n; r++){
107 if(A[r] - A[r-1] == A[r-1] - A[r-2]){
108 /*
109 dp[r-1] : count of arithmetic slices ending at r-1
110 suppose these are [r-k...r-1], ..., [r-3...r-1]
111 dp[r] : [r-k...r], ..., [r-3...r], its count is then be dp[r-1]+1
112 */
113 dp[r] = dp[r-1] + 1;
114 ans += dp[r];
115 }
116 }
117
118 return ans;
119 }
120};
121
122//O(1) space DP
123//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Arithmetic Slices.
124//Memory Usage: 7.4 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
125//time: O(N), space: O(1)
126class Solution {
127public:
128 int numberOfArithmeticSlices(vector<int>& A) {
129 int n = A.size();
130 int dp = 0;
131 int ans = 0;
132
133 for(int r = 2; r < n; r++){
134 if(A[r] - A[r-1] == A[r-1] - A[r-2]){
135 //we only need last dp value
136 dp += 1;
137 ans += dp;
138 }else{
139 //need to reset dp value!
140 dp = 0;
141 }
142 }
143
144 return ans;
145 }
146};
147
148//Approach #6 Using Formula
149//time: O(N), space: O(1)
150class Solution {
151public:
152 int numberOfArithmeticSlices(vector<int>& A) {
153 int n = A.size();
154 int count = 0;
155 int ans = 0;
156
157 for(int r = 2; r < n; r++){
158 if(A[r] - A[r-1] == A[r-1] - A[r-2]){
159 //length of consecutive arithmetic slice is count+2
160 count++;
161 }else{
162 //an slice of length count+2 can generate (count+1) * count/2 differenct subslices
163 ans += (count+1) * count/2;
164 //need to reset its value!
165 count = 0;
166 }
167 }
168
169 //handle last iteration
170 return (ans += (count+1) * count/2);
171 }
172};Cost
Complexity
Time
O(N^2), space: O(1)
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.