Detailed explanation for Java O(n^2) solution


  • 77
    F

    At first glance of the problem description, I had a strong feeling that the solution to the original problem can be built through its subproblems, i.e., the total number of arithmetic subsequence slices of the whole input array can be constructed from those of the subarrays of the input array. While I was on the right track to the final solution, it's not so easy to figure out the relations between the original problem and its subproblems.

    To begin with, let's be ambitious and reformulate our problem as follows: let T(i) denote the total number of arithmetic subsequence slices that can be formed within subarray A[0, i], where A is the input array and 0 <= i < n with n = A.length. Then our original problem will be T(n - 1), and the base case is T(0) = 0.

    To make the above idea work, we need to relate T(i) to all T(j) with 0 <= j < i. Let's take some specific j as an example. If we want to incorporate element A[i] into the subarray A[0, j], what information do we need? As far as I can see, we need to know at least the total number of arithmetic subsequence slices ending at each index k with difference d where 0 <= k <= j and d = A[i] - A[k], (i.e., for each such slice, its last element is A[k] and the difference between every two consecutive elements is d), so that adding A[i] to the end of each such slice will make a new arithmetic subsequence slice.

    However, our original formulation of T(i) says nothing about the the total number of arithmetic subsequence slices ending at some particular index and with some particular difference. This renders it impossible to relate T(i) to all T(j). As a rule of thumb, when there is difficulty relating original problem to its subproblems, it usually indicates something goes wrong with your formulation for the original problem.

    From our analyses above, each intermediate solution should at least contain information about the total number of arithmetic subsequence slices ending at some particular index with some particular difference. So let's go along this line and reformulate our problem as T(i, d), which denotes the total number of arithmetic subsequence slices ending at index i with difference d. The base case and recurrence relation are as follows:

    1. Base case: T(0, d) = 0 (This is true for any d).
    2. Recurrence relation: T(i, d) = summation of (1 + T(j, d)) as long as 0 <= j < i && d == A[i] - A[j].

    For the recurrence relation, it's straightforward to understand the T(j, d) part: for each slice ending at index j with difference d == A[i] - A[j], adding A[i] to the end of the slice will make a new arithmetic subsequence slice, therefore the total number of such new slices will be the same as T(j, d). What you are probably wondering is: where does the 1 come from?

    The point here is that to make our recurrence relation work properly, the meaning of arithmetic subsequence slice has to be extended to include slices with only two elements (of course we will make sure these "phony" slices won't contribute to our final count). This is because for each slice, we are adding A[i] to its end to form a new one. If the original slice is of length two, after adding we will have a valid arithmetic subsequence slice with three elements. Our T(i, d) will include all these "generalized" slices. And for each pair of elements (A[j], A[i]), they will form one such "generalized" slice (with only two elements) and thus contribute to one count of T(i, d).

    Before jumping to the solution below, I'd like to point out that there are actually overlapping among our subproblems (for example, both T(i, d) and T(i + 1, d) require knowledge of T(j, d) with 0 <= j < i). This necessitates memorization of the intermediate results. Each intermediate result is characterized by two integers: i and d. The former is bounded (i.e., 0 <= i < n) since they are the indices of the element in the input array while the latter is not as d is the difference of two elements in the input array and can be any value. For bounded integers, we can use them to index arrays (or lists) while for unbounded ones, use of HashMap would be more appropriate. So we end up with an array of the same length as the input and whose element type is HashMap.

    Here is the Java program (with a quick explanation given at the end). Both time and space complexities are O(n^2). Some minor points for improving the time and space performance are:

    1. Define the type of the difference as Integer type instead of Long. This is because there is no valid arithmetic subsequence slice that can have difference out of the Integer value range. But we do need a long integer to filter out those invalid cases.
    2. Preallocate the HashMap to avoid reallocation to deal with extreme cases.
    3. Refrain from using lambda expressions inside loops.
    public int numberOfArithmeticSlices(int[] A) {
        int res = 0;
        Map<Integer, Integer>[] map = new Map[A.length];
    		
        for (int i = 0; i < A.length; i++) {
            map[i] = new HashMap<>(i);
            	
            for (int j = 0; j < i; j++) {
                long diff = (long)A[i] - A[j];
                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
            		
                int d = (int)diff;
                int c1 = map[i].getOrDefault(d, 0);
                int c2 = map[j].getOrDefault(d, 0);
                res += c2;
                map[i].put(d, c1 + c2 + 1);
            }
        }
    		
        return res;
    }
    

    Quick explanation:

    1. res is the final count of all valid arithmetic subsequence slices; map will store the intermediate results T(i, d), with i indexed into the array and d as the key of the corresponding HashMap.
    2. For each index i, we find the total number of "generalized" arithmetic subsequence slices ending at it with all possible differences. This is done by attaching A[i] to all slices of T(j, d) with j less than i.
    3. Within the inner loop, we first use a long variable diff to filter out invalid cases, then get the counts of all valid slices (with element >= 3) as c2 and add it to the final count. At last we update the count of all "generalized" slices for T(i, d) by adding the three parts together: the original value of T(i, d), which is c1 here, the counts from T(j, d), which is c2 and lastly the 1 count of the "two-element" slice (A[j], A[i]).

  • 0
    S

    Python version of the above:

    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            ans = 0
            m = {}
            for i in range(len(A)):
                m[i] = {}        
                for j in range(i):
                    d = A[i] - A[j]
                    c1 = m[i][d] if d in m[i] else 0
                    c2 = m[j][d] if d in m[j] else 0
                    ans += c2
                    m[i][d] = c1 + c2 + 1
            return ans
    

  • 0
    J

    why
    res +=c2 ?


  • 6
    F

    @jadetang Hi jadetang. c2 denotes the total number of "generalized" arithmetic subsequence slices ending at index j with difference d. For each such slice, its length is at least 2. Then we are adding the element A[i] to the end of this slice to form a new one, which means the length of the new slice will be at least 3 thus it will be a valid arithmetic subsequence slice. The number of these new slices will be the same as c2. While c1 denotes the total number of "generalized" arithmetic subsequence slices ending at index i with difference d and it will include slices with length both greater than and equal to 2. So c1 will "over-count" with invalid slices of length 2.


  • 0
    D

    @fun4LeetCode genius!


  • 0
    D

    This is the most under-voted answer I've seen so far!


  • 0
    S
    This post is deleted!

  • 0
    S

    In what cases would c1 be needed?


  • 1
    F

    @sean46 Hi sean46. In the inner loop, c1 denotes the total number of generalized arithmetic subsequence slices ending at index i with difference d obtained so far. This is necessary because there may be duplicate elements. As an example, consider the input array [1, 2, 2, 3] and we are examining the last element 3. In the inner loop, when j = 1, we will have two generalized slices with difference 1. Next when j = 2, we will have another two generalized slices with difference 1. So the total number of generalized slices with difference 1 will be 4, which is the summation of the original number and that of the newly formed ones. And here c1 represents the original number of slices with the given difference.


  • 0
    D

    Brilliant idea! Learned a lot.

    I have put two Map to represent length-two slices (not valid) and length-greater-than-two slices. But could you help me why it got TLE?

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int totalSlices = 0;
            Map<Integer, Integer>[] two = new Map[A.length];
            Map<Integer, Integer>[] gttwo = new Map[A.length];
            for (int i = 0; i < A.length; i++) {
                two[i] = new HashMap<>();
                gttwo[i] = new HashMap<>();
                for (int j = 0; j < i; j++) {
                    long difflong = (long)A[i] - A[j];
                    if (difflong < Integer.MIN_VALUE || difflong > Integer.MAX_VALUE) {
                        continue;
                    }
                    int diff = (int)difflong;
                    two[i].put(diff, two[i].getOrDefault(diff, 0) + 1);
                    int jtwo = two[j].getOrDefault(diff, 0);
                    int jgttwo = gttwo[j].getOrDefault(diff, 0);
                    gttwo[i].put(diff, gttwo[i].getOrDefault(diff, 0) + jtwo + jgttwo);
                    totalSlices += jtwo + jgttwo;
                }
            }
            return totalSlices;
        }
    }
    
    

  • 0
    F

    @dachuan.huang Hi dachuan.huang. I tested you code and mine with the same input. Your runtime was roughly twice of mine. My guess is that the allocation and initialization of the HashMap's took a lot of time. You were using two HashMap's for each index, so your allocation and initialization time would be doubled.


  • 1

    I have same idea with you, but got confused when how to deal with duplicates. I stuck at case like
    [2, 2, 3, 3, 4].
    The way you accumulate slices is brilliant!


  • 0

    Somehow my dfs solution here is faster than this dp one...


  • 0
    H

    wow the "generalized slices" idea is so tricky..


  • 0
    S

    Why [1,1,1,1] has 5 arithmetic sequences?


  • 1
    F

    @skyahead Hi skyahead. [1,1,1,1] has the following five arithmetic subsequences: [1st, 2nd, 3rd], [1st, 2nd, 4th], [1st, 3rd, 4th], [2nd, 3rd, 4th], [1st, 2nd, 3rd, 4th]. Here I used the positions of the elements to specify the subsequences instead of their values (as the values are all the same).


Log in to reply
 

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