Arithmetic Slices

Problem

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.

Solution

Brute Force: O(n^2) time O(1) space

public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int diff = nums[i + 1] - nums[i];
            for (int j = i + 2; j < nums.length; j++) {
                if (nums[j] - nums[j - 1] == diff) res++;
                else break;
            }
        }
        return res;
    }
}

DP Solution: O(n) time, O(1) space

public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int res = 0, dp = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) res += ++dp;
            else dp = 0;
        }
        return res;
    }
}

Analysis

In the brute force solution, the outer loop i is the start of the slice
We first get a diff by nums[i + 1] - nums[i]
Then we use inner loop as ending of slice
As long as the diff is same, we increment the res by 1, otherwise we break the inner loop

In the DP Solution, we have int dp to reduce space complexity from having dp[]
We directly starts from the ending of slice Then we check if there is same difference between nums[i], nums[i - 1], and nums[i - 2]
If so, we increment the dp and then update res with new dp
Otherwise we set dp = 0 because in this i ending, there is no continuous qualified slices
We need to start from a new slice