Python DP O(N^2) solution (792 ms)


  • 0
    J

    Naive solution (O(N^3), Time out error)

    A naive solution is scanning the array (A) from left to right and keeping a record of potential arithmetic slices (sub-array with one or two elements) and arithmetic slices seen so far (Let's name this record history). During the scanning, we can construct new arithmetic slices based on record array history.

    Let's take A=[2,4,6,8,10] as an example:
    When we meet 2: history= [ [2] ]
    When we meet 4: history= [ [2], [4], [2,4] ]
    When we meet 6: history= [ [2], [4], [2,4], [6], [2,6], [4,6], [2,4,6] ]
    When we meet 8: history= [ [2], [4], [2,4], [6], [2,6], [4,6], [2,4,6], [8], [2,8], [4,8], [6,8], [4,6,8], [2,4,6,8] ]
    When we meet 10: history= [ [2], [4], [2,4], [6], [2,6], [4,6], [2,4,6], [8], [2,8], [4,8], [6,8], [4,6,8], [2,4,6,8], [10], [4,10], [6,10],[8,10], [2,6,10],[2,4,6,8,10], [4,6,8,10], [6,8,10] ]
    finally we can found there are 7 arithmetic slices (length>=3)
    Time and Space complexity: O(N^3), O(N^3)

    Dynamic Programming Solution O(n^2)

    In the native solution, we actually already build our solution (N) from a sub problem (N-1) and memorize the history. The dynamic programming solution is based on the same idea but with a few tricks to make it faster and save some space.

    There are several useful observations from the native solution:

    1. The array in history is not necessary. What matters is the last element (last) in this array and the difference (diff) between two elements. To test whether a new num can be added to this array, we only need to test whether num==last+diff. Based on this idea, we may initialize an array called DP with length len(A). DP[i] is a record of diffs when the last element is A[i]. If the diff is unknown (there is only one elements in the array, we set it to "unknown")
      For example, in the native solution:
      When we meet 2: history= [ [2] ]
      When we meet 4: history= [ [2], [4], [2,4] ]
      When we meet 6: history= [ [2], [4], [2,4], [6], [2,6], [4,6], [2,4,6] ]
      Now we can simplify it to
      DP=[None]*n
      DP[0]=[ ["unknown"] ] meaning array end with 2 has diff "unknown" ([2])
      DP[1]=[ ["unknown", 2] ] meaning array end with 4 has diff "unknown" ([4]) and 2 ([2,4])
      DP[2]=[ ["unknown", 4, 2, 2] ] meaning array end with 6 has diff "unknown" ([6]), 4 ([2,6]), 2 ([4,6]) and 2 ([2,4,6])
      Please note that we have two 2 in DP[2] because they are actually from different arrays.

    2. When we meet a new num=A[i], we need to scan all the previous DPs (DP[:i]) and find to which num can be appended. If we store the diffs as an array as shown above, then we need to go through all of them to find the answer. However, since we know the current number num=A[i] and we know that the ending number is A[j] (j>=0 and j<i), we know the diff we are looking at is A[i]-A[j]. To make the lookup faster, instead of array, we can use a dictionary to record diffs for each DP[i]. The key of dictionary is diff and the value will be the counts.
      Using this new methods, the previous sample can be updated to:
      DP=[None]*n
      DP[0]=[ {"unknown":1} ] meaning array end with 2 has diff "unknown" ([2])
      DP[1]=[ {"unknown":1, 2:1} ] meaning array end with 4 has 1 array with diff== "unknown" ([4]) and 1 array with diff==2 ([2,4])
      DP[2]=[ {"unknown":1, 4:1, 2: 2} ] meaning array end with 6 has 1 array with diff=="unknown" ([6]), 1 array with diff==4 ([2,6]),
      and two arrays with diff==2 ([4,6], [2,4,6])


Log in to reply
 

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