4-line O(N) one pass with arithmetic partition, minimize number of count updates (detailed explanation)


  • 1
        int numberOfArithmeticSlices(vector<int>& A) {
          int subc = 2, count = 0;
          for (auto i = A.begin()+2; i <= A.end(); ++i)
            i<A.end() && *i-*(i-1)==*(i-1)-*(i-2)? ++subc : subc = ((count+=(subc-1)*(subc-2)/2), 2);
          return count;
        }
    

    Key observation:

    1. Arithmetic array of size N has exactly (N-1)*(N-2)/2 arithmetic slices.
    2. Any array A can be uniquely partitioned into consecutive arithmetic subsections {subi=1:M }, where adjacent subi and subi+1 share exactly one element at boundary.

    For example, array

    • A = [1, 2, 3, 4, 6, 8, 10, 12, 15] can be uniquely partitioned into consecutive arithmetic subsections:
    • [1, 2, 3, 4], [4, 6, 8, 10, 12], [12, 15].

    Adding up count of arithmetic slices for each subsection gives the total count.

    Note: Do not count arithmetic slices for a subsection if not complete scanning an entire subsection yet. This makes sure to update total count for minimum number of times.


Log in to reply
 

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