Solution with explanation. O(n) memory to O(1)


  • 2
    A

    To know how many sequences we can build for position i it is enough to know for how many sequences(with length>2) it can be the tail.
    For example: {1,2,4,6,8,10,11 }
    The number 8 at position 4 (0-based) can be tail for 2 sequences:

    1. [2,4,6,8];
    2. [4,6,8];

    The number 10 can be tail for 3 sequence:

    1. [2,4,6,8,10]
    2. [4,6,8,10]
    3. [6,8,10]

    The sum of values of all tails will give us the number of possible sequences.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            HashMap<Integer, Integer> differences = new HashMap<>();
            
            int d[] = new int[A.length];
            int sum = 0;
            for (int i=2; i<A.length; i++) {
                if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
                    d[i] = d[i-1]+1;
                }
                sum+=d[i];
            }
            return sum;
        }
    }
    

    Optimization for memory:
    However, for calulating the length of sequence with equal differences at position i it is enough to know the answer only for position i-1. It is enough to store the value for i-1;

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

  • 2
    Z

    In the past, I have solved that problem like that. But I like your way.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if(A.length<=2) return 0;
            int ans=  0;
            long diff = Long.MIN_VALUE;
            int prev = A[0];
            int len = 1;
            for(int i =  1;i<A.length;i++){
                if(diff == Long.MIN_VALUE || diff == A[i] - prev){
                    diff = A[i] - prev;
                    len++;
                    prev = A[i];
                } else {
                    ans+=countSlices(len);
                    len = 1;
                    diff = Long.MIN_VALUE;
                    i--;
                }
            }
            ans+=countSlices(len);
            return ans;
        }
        
        public int countSlices(int len){
            int ans = 0;
            for(int i = 3;i<=len;i++){
                ans+=len-i+1;
            }
            return ans;
        }
    }

Log in to reply
 

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