Arithmetic Slices II - Subsequence

This page explains Java solution to problem Arithmetic Slices II - Subsequence using Dynamic Programming algorithm.

Problem Statement

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

Input: [2, 4, 6, 8, 10]
Output: 7
Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Solution

package com.vc.hard;

import java.util.HashMap;

class ArithmeticSlicesIiSubsequence {
    public int numberOfArithmeticSlices(int[] A) {
        if(A == null || A.length == 0) return 0;

        HashMap<Integer, Integer>[] dp = new HashMap[A.length];
        dp[0] = new HashMap<Integer, Integer>();

        int res = 0;
        for(int i = 1; i < dp.length; i++) {
            dp[i] = new HashMap<>();
            for(int j = 0; j < i; j++) {
                long diff = (long)A[i] - (long)A[j];

                if(diff >= Integer.MAX_VALUE || diff <= Integer.MIN_VALUE) continue;

                int diffInt = (int)diff;

                int ci = dp[i].getOrDefault(diffInt, 0);
                int cj = dp[j].getOrDefault(diffInt, 0);

                res += cj;
                dp[i].put(diffInt, ci + cj + 1);
            }
        }
        return res;
    }
}

Time Complexity

O(N²) Where
N is total number of elements in an input array.

Space Complexity

O(N)