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


  • 0
    F

    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 {
    public:
        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)
                {
                    ++contribution;
                    count += contribution;
                    continue;
                }
                
                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.