A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4] return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
The most naive solution is to consider every pair of elements(with atleast 1 element between them), so that the range of elements lying between these two elements acts as a slice. Then, we can iterate over every such slice(range) to check if all the consecutive elements within this range have the same difference. For every such range found, we can increment the that is used to keep a track of the required result.
Complexity Analysis
Time complexity : . We iterate over the range formed by every pair of elements. Here, refers to the number of elements in the given array .
Space complexity : . Constant extra space is used.
Algorithm
In the last approach, we considered every possible range and then iterated over the range to check if the difference between every consercutive element in this range is the same. We can optimize this approach to some extent, by making a small observation.
We can see, that if we are currently considering the range bound by the elements, let's say, (start) and (end), we have checked the consecutive elements in this range to have the same difference. Now, when we move on to the next range between the indices and , we again perform a check on all the elements in the range , along with one additional pair and . We can remove this redundant check in the range and just check the last pair to have the same difference as the one used for the previous range(same , incremented ).
Note that if the last range didn't constitute an arithmetic slice, the same elements will be a part of the updated range as well. Thus, we can omit the rest of the ranges consisting of the same starting index. The rest of the process remains the same as in the last approach.
Complexity Analysis
Time complexity : . Two for loops are used.
Space complexity : . Constant extra space is used.
Algorithm
By making use of the observation discussed in the last approach, we know, that if a range of elements between the indices constitute an Arithmetic Slice, and another element is included such that and have the same difference as that of the previous common difference, the ranges between will constitutes an arithmetic slice. Further, if the original range doesn't form an arithmetic slice, adding new elements to this range won't do us any good. Thus, no more arithmetic slices can be obtained by adding new elements to it.
By making use of this observation, we can develop a recursive solution for the given problem as well. Assume that a variable is used to store the total number of arithmetic slices in the given array . We make use of a recursive function slices(A,i) which returns the number of Arithmetic Slices in the range , but which are not a part of any range such that . It also updates with the number of arithmetic slices(total) in the current range. Thus, refers to the minimum index such that the range constitutes a valid arithmetic slice.
Now, suppose we know the number of arithmetic slices in the range constituted by the elements , to be say . If this range itself is an arithmetic slice, all the consecutive elements have the same difference(equal to say, ). Now, adding a new element to it to extend the range to will constitute an arithmetic slice only if this new element satisfies . Thus, now, the addition of this new element, will lead to an addition of number of arithmetic slices to the ones obtained in the range . The new arithmetic slices will be the ones constituting the ranges , which are a total of additional arithmetic slices. This is because, apart from the range the rest of the ranges can be mapped to , with count equal to .
Thus, in every call to slices, if the element has the same common difference with the last element as the previous common difference, we can find the number of new arithmetic slices added by the use of this element, and also update the to include this into it, apart from the count obtained by the smaller ranges. But, if the new element doesn't have the same common difference, extra arithmetic slices can't be contributed by it and hence, no addition is done to for the current element. But, of course will be updated as per the count obtained from the smaller ranges.
Complexity Analysis
Time complexity : . The recursive function is called at most times.
Space complexity : . The depth of the recursion tree goes upto .
Algorithm
In the last approach, we start with the full range , where is the number of elements in the given array. We can observe that the result for the range only depends on the elements in the range and not on any element beyond this range. Thus, we can make use of Dynamic Programming to solve the given problem.
We can make use of a 1-D with number of elements equal to . is used to store the number of arithmetic slices possible in the range and not in any range such that . Again, refers to the minimum index possible such that constitutes a valid Arithmetic Slice.
Instead of going in the reverse order as in the recursive approach, we can start filling the in a forward manner. The intuition remains the same as in the last approach. For the element being considered, we check if this element satsfies the common difference criteria with the previous element. If so, we know the number of new arithmetic slices added will be as discussed in the last approach. The is also updated by the same count to reflect the new arithmetic slices added.
The following animation illustrates the filling process.
!?!../Documents/413_Arithmetic_Slices.json:1000,563!?!
Complexity Analysis
Time complexity : . We traverse over the given array with elements once only.
Space complexity : . 1-D of size is used.
Algorithm
In the last approach, we can observe that we only require the element to determine the value to be entered at . Thus, instead of making use of a 1-D array to store the required data, we can simply keep a track of just the last element.
Complexity Analysis
Time complexity : . We traverse over the given array with elements once only.
Space complexity : . Constant extra space is used.
Algorithm
From the solution, we can observe that for consecutive elements sastisfying the common difference criteria, we update the for each such element by counts in that order. Thus, instead of updating the at the same time, we can just keep a track of the number of consecutive elements satisfying the common differnce criteria in a variable and just update the directly as whenver an element not satisfying this criteria is found. At the same time, we also need to reset the value.
Complexity Analysis
Time complexity : . We iterate over with elements exactly once.
Space complexity : . Constant extra space is used.
Analysis written by: @vinod23