O(n) time, O(1) Space, no recurssion, simple buttom-up DP approach.

  • 0

    Code Below Explanation.

    We at least need 3 elements to start with. let's call them [a,b,c]. And let's assume it is an arithmetic. Now lets adds 1 element. If the new element also forms an arithmetic, then it adds 2 new arithmetics to the number of possible arithmetics: elements [a,b,c,d] and [b,c,d]. If we add yet another element that still forms an arithmetic with them now we have added 3 new arithmetics to total arithmetics [a,b,c,d,e], [b,c,d,e], and [c,d,e].

    As a result, with addition of each new element to an arithmetic, that element is going to add N-2 new arithmetics to the previous ones, where N is the length of the current arithmetic including the new element. If the current arithmetic is broken then we have to wait until a new one is started and we can do the same with that.

    The following code keeps the N-2 (length of the arithmetic minus 2) in the variable "contribution".

    class Solution {
        int numberOfArithmeticSlices(vector<int>& A) {
            if (A.size() < 3)
                return 0;
            int count = 0, contribution = 0, dist = A[1] - A[0];
            for (int i = 2; i < A.size(); ++i)
                if (A[i] - A[i - 1] == dist)
                    count += contribution;
                contribution = 0;
                dist = A[i] - A[i - 1];
            return count;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.