Longest Arithmetic Progression

Facebook Interview Dynamic Programming

Find the length of longest arithmetic progression in array.
For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is {1, 3, 5, 7}.
Give the length 4 as the output.

Solution

If you have solved the longest increasing subsequence problem before, the same idea applies to this problem.

At each index 'idx' in the array, cache the lengths of all the arithmetic progressions that end with array[idx]. This can be done by looking at all the arithmetic progressions from [index 0 to index (idx - 1)] and see if array[idx] belongs to that progression.

The cache will store the ending number, the difference and the length of each progression.

{
    End_number1: {Diff1: Length1, Diff2: Length2, Diff3: Length3, ... },
    End_number2: {Diff4: Length4, ...}
    End_number3: {...}
    ...
}

For example, given input array = {1, 6, 3, 5, 9, 7}
When idx = 0, array[0] = 1
I. Check for all progressions before idx = 0, which is none.

{
    array[0]: None,
}

When idx = 1, array[1] = 6
Check for all progressions in [0, 0], which is none.
I. At array[0], array[1] - array[0] = 5
array[0] and array[1] together make a progression with a difference of (6 - 1) = 5. Store this progression with its Diff = 5 and its Length = 2.

{
    array[0]: None,
    array[1]: { (5: 2) }
}

When idx = 2, array[2] = 3
Check for all progressions in [0, 1]
I. At array[1], array[2] - array[1] = -3.
There is no key in { (5: 2) } that matches -3. Therefore the longest arithmetic progression that ends with array[1] AND array[2] has only the two numbers in the sequence. Add this to the progressions list of array[2].

II. At array[0], array[2] - array[0] = 2
There is no key in None that matches 2. Therefore the longest arithmetic progression that ends with array[0] AND array[2] has only the two numbers in the sequence. Add this to the progressions list of array[2].

{
    array[0]: None,
    array[1]: { (5: 2) }
    array[2]: { (-3, 2), (2, 2) }
}

When idx = 3, array[3] = 5
Check for all progressions between index [0, 2]
I. At array[2], array[3] - array[2] = 2.
There is a key in { (-3, 2), (2, 2) } that matches 2 which means a progression with a difference of 2 that ends with array[2] is found. This progression has a length of 2.
Therefore the longest arithmetic progression that ends with array[2] AND array[3] has (2 + 1) numbers in the sequence. Add this to the progressions list of array[3].

II. At array[1], array[3] - array[1] = -1
There is no key in { (5: 2) } that matches -1. Therefore the longest arithmetic progression that ends with array[1] AND array[3] has only the two numbers in the sequence. Add this to the progressions list of array[3].

III. At array[0], array[3] - array[0] = 4
There is no key in None that matches 4. Therefore the longest arithmetic progression that ends with array[0] AND array[3] has only the two numbers in the sequence. Add this to the progressions list of array[3].

{
    array[0]: None,
    array[1]: { (5: 2) }
    array[2]: { (-3, 2), (2, 2) }
    array[3]: { (2, 3), (-1, 2), (4, 2)}
}

IV. When idx = 4, array[4] = 9
Run through all previous numbers between index [0, 3] and find all the arithmetic progression ending with them. Check if the difference applies to the current number.
The map will be updated to

{
    array[0]: None,
    array[1]: { (5: 2) }
    array[2]: { (-3, 2), (2, 2) }
    array[3]: { (2, 3), (-1, 2), (4, 2)}
    array[4]: { (4, 3), (6, 2), (3, 2), (8, 2) }
}

IV. When idx = 5, array[5] = 7
Run through all previous numbers between index [0, 4] and find all the arithmetic progression ending with them. Check if the difference applies to the current number.
The map will be updated to

{
    array[0]: None,
    array[1]: { (5: 2) }
    array[2]: { (-3, 2), (2, 2) }
    array[3]: { (2, 3), (-1, 2), (4, 2)}
    array[4]: { (4, 3), (6, 2), (3, 2), (8, 2) }
    array[5]: { (-2, 2), MAX(2, 4), (4, 2), (1, 2), (6, 2) }
}

As a result, the progression with a difference of 2 has the max length 4.
Though in other cases the longest progression does not necessarily ends with the last number in the array, so we need a variable max to keep track of the MAX length that could show up anytime during the process.

Implementation

public class LLAC {
    public int llac(int[] array) {
        if(array.length == 0) return 0;
        int max = 1;
        //Map<currentIndex, Map<difference, length>>
        Map<Integer,Map<nteger, Integer>> index_to_llac = new HashMap<>(); 
        for(int current = 1; current < array.length; current++) {
            index_to_llac.put(current, new HashMap<>());
            for(int prev = 0; prev < current; prev++) {
                int diff = array[current] - array[prev];
                int length = 2;
                if(index_to_llac.containsKey(prev) && index_to_llac.get(prev).containsKey(diff)) {
                    length = index_to_llac.get(prev).get(diff) + 1;
                }
                Map<Integer, Integer> diff_to_llac = index_to_llac.get(current);
                //if this is a arithmetic progression with [diff] exists before current, add 1 to the length to include current in the progression
                //otherwise, [prev, current] forms a progression of size 2
                diff_to_llac.put(diff, length);
                max = Math.max(length, max);
            }
        }
        return max;
    }