413. Arithmetic Slices
Last updated
Last updated
/**
* Time complexity : O(n^2), Two for loops are used.
* Space complexity : O(1)
*/
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
for (int s = 0; s < A.length - 2; s++) {
int d = A[s + 1] - A[s];
for (int e = s + 2; e < A.length; e++) {
if (A[e] - A[e - 1] == d)
count++;
else
break;
}
}
return count;
}
}/**
* Time complexity : O(n). The recursive function is called at most n-2 times.
* Space complexity : O(n). The depth of the recursion tree goes upto n-2.
*/
public class Solution {
int sum = 0;
public int numberOfArithmeticSlices(int[] A) {
slices(A, A.length - 1);
return sum;
}
public int slices(int[] A, int i) {
if (i < 2)
return 0;
int ap = 0;
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
ap = 1 + slices(A, i - 1);
sum += ap;
} else
slices(A, i - 1);
return ap;
}
}/**
* Time complexity : O(n). We traverse over the given A array with n elements once only.
* Space complexity : O(n). 1D dp of size n is used.
*/
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];
int sum = 0;
for (int i = 2; i < dp.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = 1 + dp[i - 1];
sum += dp[i];
}
}
return sum;
}
}/**
* Time complexity : O(n). We traverse over the given A array with n elements once only.
* Space complexity : O(1). Constant extra space is used.
*/
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int dp = 0;
int sum = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp = 1 + dp;
sum += dp;
} else
dp = 0;
}
return sum;
}
}/**
* Time complexity : O(n). We iterate over A with n elements exactly once.
* Space complexity : O(1)
*/
class Solution {
public int numberOfArithmeticSlices(int[] A) {
if(A == null || A.length < 3) {
return 0;
}
int n = A.length;
int numOfSlices = 0, count = 0;
for(int i = 0; i+2 < n; i++) {
if(A[i+1]-A[i] == A[i+2]-A[i+1]) {
count++;
} else {
numOfSlices += (count+1)*count/2;
count = 0;
}
}
numOfSlices += (count+1)*count/2;
return numOfSlices;
}
}