C++ O(N) runtime, O(1) memory with explanations


  • 0
    G
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) 
        {
            if(A.size() < 3)
            {
                return 0;
            }
            
            int Total = 0;
            int Count = 2;
            
            //the following calcuation is based on the following observation:
            // Total(3 elements) = 1
            // Total(4 elements) = 3
            // Total(5 elements) = 6
            // Total(6 elements) = 10
            // 
            // in other words each element increase the Total count by
            // the previous number of elements - 1
            // 
            // Also,we need to reset our counters when we find a triplet that
            // isn't an arithmetic slice
            //
            
            for(int i = 2; i < A.size(); ++i)
            {
                int Curr = A[i];
                int Prev = A[i - 1];
                int PrevPrev = A[i - 2];
                
                if(Curr - Prev == Prev - PrevPrev)
                {
                    Total += Count - 1;
                    Count++;
                }
                else
                {
                    Count = 2;
                }
            }
            
            return (Total);
        }
    };

Log in to reply
 

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