Simple Java solution 9 lines, 2ms


  • 119
    L
    public int numberOfArithmeticSlices(int[] A) {
        int curr = 0, sum = 0;
        for (int i=2; i<A.length; i++)
            if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
                curr += 1;
                sum += curr;
            } else {
                curr = 0;
            }
        return sum;
    }

  • 27
    M

    @lcl7722 Clever! thanks for the concise code.
    If I understand correctly, the way it works is:
    i) We need minimum 3 indices to make arithmetic progression,
    ii) So start at index 2, see if we got two diffs same, so we get a current 1 arith sequence
    iii) At any index i, if we see it forms arith seq with former two, that means running (curr) sequence gets extended upto this index, at the same time we get one more sequence (the three numbers ending at i), so curr++. Any time this happens, add the curr value to total sum.
    iv) Any time we find ith index does not form arith seq, make currently running no of seqs to zero.


  • 0
    X

    thanks a lot!


  • 1
    L

    Thanks for your idea.

    sum += curr;

    This line does the trick. It accumulates all the possible seqs of the longest arithmetic seq of it's kind.


  • 19
    F

    sum += curr really does the trick. Brilliant!

    I think the easy way to understand this is that adding current number to our existing arithmetic sequence, we will have curr additional combinations of new arithmetic slices.

    Let's say if we have [1, 2, 3, 4] and currently we have 3 arithmetic slices (curr is 2). We are going to add 5 to our arithmetic sequence. So that we will have curr new slices (curr is 3), which is [3, 4, 5], [2, 3, 4, 5] and [1, 2, 3, 4, 5]. Now, the total valid arithmetic slices is 3 + curr = 6. That's exactly the same as sum += curr.


  • 15
    S

    if (A[i]-A[i-1] == A[i-1]-A[i-2]) this introduces an integer overflow bug.

    If the input is [Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE - 1], it returns 1, but it should be 0.

    Correction:

    public int numberOfArithmeticSlices(int[] A) {
        int curr = 0, sum = 0;
        for (int i = 2; i < A.length; i++) {
            if ((long)A[i] - A[i - 1] == (long)A[i - 1] - A[i - 2]) {
                curr += 1;
                sum += curr;
            }
            else curr = 0;
        }
        return sum;
    }
    

  • 0

    Such a brilliant function. I love it!


  • 0
    J

    @Free9
    thank you for your explaintion


  • 0
    S

    @Free9 Easy explanation! thanks


  • 3

    Nice solution, very concise. The way I think about it is as your slice grows by 1, you have created the 1 longer slice plus a new position for each of the lengths you have already created. So, if you have a slice that is length 5 you will have slices of lengths 5, 4, 3 (all but the largest have multiple positions). If you now grow from 5 to 6, you create a new slice of length 6 and a new position for 5, 4, and 3.

    Here's the DP part, but really you only need to hang onto the previous result or apply the logic directly in the code.

    f(length of sequece) = number of slices you can make
    f(len) = 1 + f(len - 1) + (len - 3)
    f(2) = 0
    f(3) = 1 + f(2) + (3 - 3) = 1
    f(4) = 1 + f(3) + (4 - 3) = 3
    f(5) = 1 + f(4) + (5 - 3) = 6
    f(6) = 1 + f(5) + (6 - 3) = 10
    f(7) = 1 + f(6) + (7 - 3) = 15
    f(8) = 1 + f(7) + (8 - 3) = 21
    f(9) = 1 + f(8) + (9 - 3) = 28
     
    
        public int NumberOfArithmeticSlices(int[] A) 
        {
            int count = 0;
            for (int start = 0; start < A.Length - 2; start++)
            {
                int delta = A[start+1] - A[start];
                
                // for this starting point discover the length 
                // NOTE: this is additional length from 3 onwards (3 will have a "len = 1")
                int len = 0;
                for (int i = start + 2; i < A.Length; i++)
                {
                    if (A[i] - A[i-1] == delta)
                    {
                        len++;
                        count += len; // 1 for each length
                    }
                    else 
                    {
                        break;
                    }
                }
    
                // skip to final element in the sequence for next start position
                start += len;
            }
            
            return count;
        }
    
    

  • 0

    said in Simple Java solution 9 lines, 2ms:

    sum += curr

    Very concise solution! But it seems to update the total count by sum += curr every time if the common difference is same. It could update sum only when common difference changes by a total of (subsum-1)*(subsum-2)/2.


  • 1
    G

    @Free9
    thank you for explain it, i wander why not count [1,3,5] ,if[1,2,3,4,5] is Arithmetic Slices ,then [1,3,5] must also be Arithmetic Slices.can you explain it?


  • 1

    @guk said in Simple Java solution 9 lines, 2ms:

    @Free9
    thank you for explain it, i wander why not count [1,3,5] ,if[1,2,3,4,5] is Arithmetic Slices ,then [1,3,5] must also be Arithmetic Slices.can you explain it?

    Note that in this problem, the slice is defined as subsequence with consecutive index, so [1,3,5] does not qualify for arithmetic slices.

    The example you are making is actually for the harder version 446. arithmetic slices II.


  • 0
    R

    These are just slices of length 3, what about slices of length 4, 5, ... A.Length-3 ?
    Won't they increase the overall slice count ?


  • 0

    @rohan5 said in Simple Java solution 9 lines, 2ms:

    These are just slices of length 3, what about slices of length 4, 5, ... A.Length-3 ?
    Won't they increase the overall slice count ?

    Actually, it already counted all slices with length at least 3 (which is the definition). Line curr += 1 counts the number of arithmetic slices ending with current number and sum += curr just adds up the counts towards the total.


  • 0
    R

    I can see it now,
    we are basically assuming an extra slice, ie, if
    1 2 3 is a slice and 2 3 4 is a slice then 1 2 3 4 must be a slice.
    Thus, we do curr+=1 and not cur = 1.

    We've basically assumed 1 2 3 4 is a slice and when we reach 2 3 4 we have 2 slices to add to the current sum.

    If we had nums uptil 5 and we reached 3 4 5, we would have 3 slices to add to current sum.


  • 1

    @rohan5 Yes, that is the basic idea for the key line sum += curr.

    Actually, I prefer to scan all the way to the end of a longest arithmetic subsequence before start counting the sum (which I personally think more readable in logic) simply because of the following fact:

    • Arithmetic array of size N has exactly (N-1)*(N-2)/2 arithmetic slices (length >= 3).

    Also, it will minimize the number of times to update sum. I had a post here if you are interested.


  • 0
    R

    @zzg_zzm Where did you get that formula (N-1)*(N-2)/2 ?


  • 2

    @rohan5 said in Simple Java solution 9 lines, 2ms:

    @zzg_zzm Where did you get that formula (N-1)*(N-2)/2 ?

    Just count total number of arithmetic slices by various lengths. For any given arithmetic array A of size N, it has

    • 1 arithmetic slice of length N (itself);
    • 2 arithmetic slices of length N-1 (0~N-2 and 1~N-1);
    • 3 arithmetic slices of length N-2;
      ...
    • N-2 arithmetic slices of length 3.

    So the total count of arithmetic slices is 1+2+3+...+(N-2) = (N-1)*(N-2)/2.

    Or simply using combination number CN2 - (N-1) = (N-1)*(N-2)/2 (taking any 2 indices from N indices but they cannot be adjacent).


  • 0
    N

    omg! sososo brilliant!


Log in to reply
 

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