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

1. 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.
2. 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

1. 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

1. For j = n, dp[i][j] = 2 for 0<i<n, bottom-most column filled with 2.
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?

Comparison of Solutions

Suggested Problems to Solve

• Longest arithmetic progression with the given common difference
• The ratio of mth and nth term in an Arithmetic Progression (AP)
• Program for N-th term of Arithmetic Progression series
• Check whether Arithmetic Progression can be formed from the given array
• Find the missing number in Arithmetic Progression
• Count of AP (Arithmetic Progression) Subsequences in an array

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding! Enjoy Algorithms!