Longest arithmetic progression in a sorted array

Problem

Given a sorted array, find the longest arithmetic progression in the same.

Solution

Method 1 - Dynamic Programming

Before solving this problem, let us solve a different problem first.

How to find if a sorted array contains an arithmetic progression of length 3?

This can be done by looping over the array and then finding numbers ‘i’ and ‘k’ on either side of current number ‘j’ such that

arr[j] + arr[k] = 2*arr[i] and
k < i < j

To find the longest AP efficiently, we can use dynamic programming (DP). We’ll use a 2D DP table where dp[i][j] represents the length of the longest AP ending with elements at indices i and j. The idea is to iterate over all pairs (i, j) where i < j, and for each pair, we look for the previous element in the AP (2*a[i] - a[j]). If such an element exists, we update the DP table accordingly.

Steps

Here are the steps:

Initialization:
- Create a DP table of size n x n where n is the length of the array.
- Set all values of dp to 2 initially, as a minimum AP length with two elements is 2.
Fill DP Table:
- Iterate through all pairs (i, j) where i < j.
- For each pair, find the previous element needed to form an AP. If it exists, update the DP value.
Track Maximum Length:
- Track the maximum length of the AP found during the process.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


import java.util.HashMap;

public class Solution {
    public int longestArithSeqLength(int[] arr) {
        int n = arr.length;
        if (n <= 2) {
            return n;
        }

        HashMap<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }

        int maxLen = 2;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int diff = arr[j] - arr[i];
                dp[j].put(diff, dp[i].getOrDefault(diff, 1) + 1);
                maxLen = Math.max(maxLen, dp[j].get(diff));
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr1 = {1, 7, 10, 13, 14, 19};
        System.out.println("Longest AP length in "
            + java.util.Arrays.toString(arr1)
            + " is: " + solution.longestArithSeqLength(arr1)); // Output: 4

        int[] arr2 = {1, 3, 5, 7, 9};
        System.out.println("Longest AP length in "
            + java.util.Arrays.toString(arr2)
            + " is: " + solution.longestArithSeqLength(arr2)); // Output: 5
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


def longest_arith_seq_length(arr):
    n = len(arr)
    if n <= 2:
        return n

    dp = [{} for _ in range(n)]
    max_len = 2

    for j in range(n):
        for i in range(j):
            diff = arr[j] - arr[i]
            if diff in dp[i]:
                dp[j][diff] = dp[i][diff] + 1
            else:
                dp[j][diff] = 2
            max_len = max(max_len, dp[j][diff])

    return max_len

# Example usage
arr1 = [1, 7, 10, 13, 14, 19]
print(f"Longest AP length in {arr1} is: {longest_arith_seq_length(arr1)}")  # Output: 4 (i.e., [1, 7, 13, 19])

arr2 = [1, 3, 5, 7, 9]
print(f"Longest AP length in {arr2} is: {longest_arith_seq_length(arr2)}")  # Output: 5 (i.e., [1, 3, 5, 7, 9])

Complexity

⏰ Time complexity: O(n^2), due to the nested loops iterating through all pairs.
🧺 Space complexity: O(n^2), in the worst case if all elements have unique differences.

Problem#

Solution#

Method 1 - Dynamic Programming#

Steps#

Code#

Complexity#