Longest Arithmetic Progression

Difficulty: Medium

Asked in: Google, Microsoft

Understanding The Problem

Problem Description

Given a set of integers in an array A[] of size n , write a program to find the length of the longest arithmetic subsequence in A .

In other wrods, find the longest sequence of indices, 0 <= i1 < i2 < … < ik <= n-1 such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression.

Problem Note:

Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence P[0], P[1], P[2], …, P[m — 1] of length m is an Arithmetic Progression if and only if P[1] — P[0] == P[2] — P[1] == P[3] — P[2] == … == P[m — 1] — P[m — 2]
The common difference can be positive, negative or 0.

Example 1

Input: A[] = [3, 6, 9, 12]
Output: 4
Explanation: [3, 6, 9, 12] form an arithmetic progression.

Example 2

Input: A[] = [9, 4, 7, 2, 10]
Output: 3
Explanation:[4, 7, 10] form an arithmetic progression.

Solutions

We will be discussing two different solutions for this problem

Brute Force Solution: For every pair of numbers in the array, check if the second number + their difference exists in the array and maintain the count accordingly.
Dynamic Programming: Store the number of sequences for each pair of numbers and fill the DP table.

You may try to solve this problem here.

1. Brute Force Solution

An arithmetic progression(AP) is a sequence of numbers in which each differs from the preceding one by a constant quantity. If we consider any pair ( 1st_num , 2nd_num ) of numbers from the array, then the next number in the arithmetic sequence will be ( 2nd_num + diff ) where diff is ( 2nd_num — 1st_num ) from the formula. This makes our problem easy to solve. We just have to take each pair of numbers and check if the next number following the formula of AP exists or not in the array.

If the next number of the series considering the pair(1st_num, 2nd_num) exists then, we will have to look for the 3rd_num + diff and thus maintain a counter to keep track of the maximum length of such a sequence.

Solution Steps

For each pair of numbers from the nums array

check if the next number (3rd_num) = 2nd_num + diff exists
If the 3rd_num exists, then look for 4th_num = 3rd_num + diff exists and so on.

2. Maintain a maxLength variable that will tell about the maximum length of an AP that exists in the nums array.

Pseudo Code

int longestArithSeqLength(int[] nums) {
    if(nums.size() <= 2){
        return nums.size()
    }
    maxLength = 2
    for(int i=0 to i < nums.size()){
        for(int j=i+1 to j < nums.size()){
            diff = nums[j] - nums[i]
            nextTarget = nums[j] + diff
            currentLongestLength = 2
            for(int k = 0 to k < nums.size()){
                 if(nums[k] == nextTarget){
                      currentLongestLength += 1
                      maxLength = max(maxLength, currentLongestLength)
                      nextTarget = nextTarget + diff
                 }
            }
        }
    }
    return maxLength
}

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(1)

Critical Ideas to Think

How did we find the next number of the sequence for each valid AP sequence?
The currentLongestLength contains the longest sequence of AP for which elements?
Try to dry run the code on some example and check for overlapping problems.

2. Dynamic Programming

If we analyze the above brute force solution, we will find that there are overlapping cases when we recalculate the length of an arithmetic progression for a pair of numbers.

The idea is to create a 2D table dp[n][n]. An entry dp[i][j] in this table stores the Longest arithmetic progression with nums[i] and nums[j] as the first two elements of AP and (j > i) . The last column of the table is always 2 (as discussed above). The rest of the table is filled from the bottom right to top left. To fill the rest of the table, j (second element in AP) is first fixed . i and k are searched for a fixed j . If i and k are found such that i , j , k form an AP, then the value of dp[i][j] is set as dp[j][k] + 1 . Note that the value of dp[j][k] must have been filled before as the loop traverses from right to left columns.

Solution Steps

For j = n, dp[i][j] = 2 for 0<i<n , bottom-most column filled with 2 .
Fix j = n-1 to 1 and for each j do the below steps:

Find all i and k such that nums[i] , nums[j] and nums[k] form AP.
Fill dp[i][j] = 1 + dp[j][k]
Check if dp[i][j] is longer than the current max length, if yes, update it.
A slight change for optimization, if nums[i] + nums[k] > 2*nums[j] , we can safely fill nums[i][j] as 2 .
While i > 0 even after k > n , fill all dp[i][j] = 2 .

Pseudo Code

int lenghtOfLongestAP(int[] nums) 
{   
    n = nums.size()
    int dp[n][n]
    int longestAP = 2
    // Fill entries in last column as 2. 
    for (int i = 0 to i < n) 
        dp[i][n-1] = 2
    // Consider every element as second element of AP 
    for (int j=n-2 to j>=1) { 
        i = j-1
        k = j+1
        while (i >= 0 and k <= n-1) { 
           if (nums[i] + nums[k] <= 2*nums[j]) 
               k = k + 1
           else if (nums[i] + nums[k] > 2*nums[j]) {   
               dp[i][j] = 2
               i = i - 1
           } 
           else { 
               dp[i][j] = dp[j][k] + 1 
               longestAP = max(longestAP, dp[i][j])
               // Change i and k to fill more dp[i][j] values for 
               // current j 
               i = i - 1
               k = k + 1
           } 
        } 
        // If the loop was stopped due to k becoming more than 
        // n-1, set the remaining entties in column j as 2 
        while (i >= 0) { 
            dp[i][j] = 2
            i = i - 1
        } 
    } 
    return longestAP
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n²)

Critical Ideas to Think

Why did we initialize the DP[i][n-i] with 2 ?
What did we insert in DP[i][j] when nums[i] + nums[k] > 2*nums[j] and why?
What is the meaning of the value stored in DP[i][j] ? What does the value represent?