Longest Arithmetic Progression Sequence in Java

An array arr[] is given, and the task is to find the length of the longest sequence in the array such that the sequence forms the arithmetic progression.

Example 1:

Input: int arr[] = {30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140};

Output: 12

Explanation: The sequence of numbers 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140 form the arithmetic progression sequence where the common difference is 10, and the total numbers in the sequence is 12.

Example 2:

Input: int arr[] = {15, 7, 20, 9, 14, 15, 25, 30, 90, 100, 35, 40};

Output: 6

Explanation: The sequence of numbers 15, 20, 25, 30, 35, 40 forms the arithmetic progression sequence where the common difference is 5 and the total numbers in the sequence are 6.

Let's discuss various approaches to solve the problem.

Naive Approach

The naive or simple approach is to consider each pair one by one and treat the elements of the pair as the first two elements (assume the first two elements are: a1 and a2) of the arithmetic progression. Using the first two elements, we can get a common difference (a2 - a1). Using this common difference, we can get the subsequent elements of the arithmetic progression. While finding the subsequent elements, we can also keep the count of elements (countEle) for that arithmetic progression. We will find this count (countEle) for each pair and then will do the comparison for finding the longest arithmetic sequence. Observe the following program.

FileName: LongestArithmeticProgression.java

Output:

For the following array: 30 40 50 60 70 80 90 100 110 120 130 140 The length of the longest arithmetic progression sequence is: 12 For the following array: 15 7 20 9 14 15 25 30 90 100 35 40 The length of the longest arithmetic progression sequence is: 6 

Complexity Analysis: In the above program, three for-loops have been nested. Therefore, the time complexity of the above program O(n³), where n is the total number of the elements present in the input array. The space complexity of the above program is constant, i.e., O(1).

Since the O(n³) time complexity of the program is too high, it is required to reduce the time complexity using some optimization. The following approach shows the same.

Dynamic Programming Approach

FileName: LongestArithmeticProgression1.java

Output:

For the following array: 30 40 50 60 70 80 90 100 110 120 130 140 The length of the longest arithmetic progression sequence is: 12 For the following array: 15 7 20 9 14 15 25 30 90 100 35 40 The length of the longest arithmetic progression sequence is: 6 

Complexity Analysis: In the above program, two for-loops have been nested. Therefore, the time complexity of the above program O(n²), where n is the total number of the elements present in the input array. We have also used the two-dimensional array which makes the space complexity of the program O(n²).

Even, we can do more optimization to reduce the space complexity. The following approach shows the same.

Using Two Pointers Approach

In this approach, we will fix the middle element of the arithmetic progression and will try to find out the previous and the next element of the progression. It will be done using two pointers. However, before doing that we also need to sort the array. It is because two pointers approach will not work if the given array is not sorted.

FileName: LongestArithmeticProgression2.java

Output:

For the following array: 30 40 50 60 70 80 90 100 110 120 130 140 The length of the longest arithmetic progression sequence is: 12 For the following array: 15 7 20 9 14 15 25 30 90 100 35 40 The length of the longest arithmetic progression sequence is: 6 

Complexity Analysis: The time complexity is the same as above. However, we have only used a single dimensional array for accomplishing the task. Therefore, we have reduced the space complexity to O(n), where n is the total number of the elements present in the input array.