2ms Java O(n) time, O(1) space solution


  • 11
    S
    public int numberOfArithmeticSlices(int[] A) {
            if(A == null || A.length < 3)
                return 0;
            int sum = 0;
            int len = 2;
    
            for(int i=2;i<A.length;i++) {
    
                // keep increasing the splice
                if(A[i] - A[i-1] == A[i-1] - A[i-2]) {
                    len++;
                }
                else {
                    if(len > 2) {
                        sum += calculateSlices(len);
                    }
                    // reset the length of new slice
                    len = 2;
                }
            }
            // add up the slice in the rear
            if(len>2)
                sum += calculateSlices(len);
    
            return sum;
        }
    
        private int calculateSlices(int n){
            return (n-1)*(n-2)/2;
        }
    

  • 0
    B

    Does the function calculateSlices represent the total number of ways we can pick 3 elements from n elements nC3?


  • 0
    S

    @bhimaraju Yes, that's correct


  • 2
    B

    Hmmm, to me it looks more like the sum of the first n-2 numbers...

    For example, if your sequence was 2,4,6,8,10, then you have the following sub sequences formed:

    1. 2,4,6, 4,6,8, 6,8,10: 3 sub sequences, or rather 5-2 sequences
    2. 2,4,6,8, 4,6,8,10: 2 sub sequences
    3. 2,4,6,8,10: 1 sub sequence

    Thus the total number of sequences is 3+2+1 or in other words, the sum from 1..n-2, which is (n-1)*(n-2)/2.


  • 0

    Here's a C# solution to merge the if (len>2) condition inside the loop.

    public class Solution {
        public int NumberOfArithmeticSlices(int[] A) {
            if (A == null || A.Length < 3) {
                return 0;
            }
            
            // Init the state
            int start = 0;
            int index = 2;
            int diff = A[1] - A[0];
            int result = 0;
            
            while(index <= A.Length) {
                // when reach to end or detect the end of arithmetic
                if (index == A.Length || A[index] - A[index-1] != diff) {
                    // calculate the result. When the sequence number is n,
                    // the result is 1 + 2 + 3 + ... + n - 2
                    // i.e., n*(n+1)/2 - n - (n-1)
                    if (index - start >= 3) {
                        int n = index - start;
                        result += n * (n + 1) / 2 - n - (n-1);
                    }
                    
                    // start with the new potential arithmetic
                    if (index != A.Length) {
                        start = index - 1;
                        diff = A[index] - A[index-1];
                    }
                }
                
                index++;
            }
            
            return result;
        }
    }
    

  • 0
    R

    still have space to improve


  • 0
    Z

    @shiyanch Nice solution. I think this is the straightforward solution that us mere mortals can strive for.


Log in to reply
 

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