Leetcode 1027. Longest Arithmetic Sequence

Problem Explanation

Given an array of integers, our goal is to find the length of the longest arithmetic sequence within this array. An arithmetic sequence or progression is a sequence of numbers in which the difference between the consecutive terms is constant.

For example, in the sequence 5, 7, 9, 11, 13, the difference between consecutive terms is 2, hence, it is an arithmetic sequence. A subsequence from an array is a sequence of elements without changing the order but not necessarily consecutive. So we want to find the longest subsequence that forms an arithmetic sequence.

To illustrate this, let's take an example. If the input array is [3,6,9,12], then the whole array is an arithmetic sequence with steps of length = 3. So the output will be 4.

Solution Explanation

We can make use of dynamic programming to solve this problem efficiently. Our dynamic programming state is represented by (i, d) where i is the index of the element and d is the arithmetic difference. We use a hash table to store all dynamic programming states. For each element in the given array, we compute the difference with all elements before it and check if there are any subsequences that have the same arithmetic difference.

We initialize the dp[i][d] with 1, which represents the smallest size an arithmetic subsequence can have. While iterating over the dp array, whenever we find an element pair that gives the same difference as before, we update the corresponding dp value.

Let's illustrate this approach with a small example. Assume our input array is [9,4,7,2,10]. We start with the second element, get the difference with the first element which is -5, look it up in our hashmap and find no arithmetic subsequence that ends with 9 with difference 5, so we insert the pair into our hashmap. For the subsequent elements, we continue the same operation. Eventually, we find a subsequence [4,7,10] with difference 3 and the maximum length of the subsequence is 3.

Python Solution

1
2python
3class Solution:
4    def longestArithSeqLength(self, A):
5        dp = {}  # Create a dictionary to hold our dynamic programming state
6        for i in range(len(A)):  # Iterate over the array
7            for j in range(i):  # For the current element, check against all elements before it
8                diff = A[i] - A[j]  # Calculate the difference between current element and previous element
9                # The state is represented by current index i and difference diff
10                # If there already exists such a state, we use the maximum value of existing one and current
11                # Otherwise we start from 2
12                dp[i, diff] = dp.get((j, diff), 1) + 1
13        return max(dp.values())  # Return the maximum value

Java Solution

1
2java
3class Solution {
4    public int longestArithSeqLength(int[] A) {
5        int max = 0;
6        Map<Integer, Integer>[] dp = new HashMap[A.length];  // Create a HashMap to hold our dynamic programming state
7        for (int i = 0; i < A.length; i++) {
8            dp[i] = new HashMap<>();
9            for (int j = 0; j < i; j++) {  // For the current element, check against all elements before it
10                int diff = A[i] - A[j];  // Calculate the difference between current element and previous element
11                // The state is represented by current index i and difference diff
12                // If there already exists such a state, we use the maximum value of existing one and current
13                // Otherwise we start from 2
14                dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
15                max = Math.max(max, dp[i].get(diff));  // Update the maximum value
16            }
17        }
18        return max;  // Return the maximum value
19    }
20}

C++ Solution

1
2c++
3class Solution {
4public:
5    int longestArithSeqLength(vector<int>& A) {
6        int ans = 0;
7        vector<map<int, int>> dp(A.size());
8        for (int i = 1; i < A.size(); i++) {  // Iterate over the array
9            for (int j = 0; j < i; j++) {  // For the current element, check against all elements before it
10                int diff = A[i] - A[j];  // Calculate the difference between current element and previous element
11                // The state is represented by current index i and difference diff
12                // If there already exists such a state, we use the maximum value of existing one and current
13                // Otherwise we start from 2
14                dp[i][diff] = max(2, 1 + dp[j][diff]);
15                ans = max(ans, dp[i][diff]);  // Update the maximum value
16            }
17        }
18        return ans;  // Return the maximum value
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int LongestArithSeqLength(int[] A) {
5        int max = 0;
6        // Create a dictionary to hold our dynamic programming state
7        var dp = new Dictionary<int, int>[A.Length];
8        for (int i = 0; i < A.Length; i++) {
9            dp[i] = new Dictionary<int, int>();
10            for (int j = 0; j < i; j++) {  // For the current element, check against all elements before it
11                int diff = A[i] - A[j];  // Calculate the difference between current element and previous element
12                // The state is represented by current index i and difference diff
13                // If there already exists such a state, we use the maximum value of existing one and current
14                // Otherwise we start from 2
15                dp[i][diff] = dp[j].ContainsKey(diff) ? dp[j][diff] + 1 : 2;
16                max = Math.Max(max, dp[i][diff]);  // Update the maximum value
17            }
18        }
19        return max;  // Return the maximum value
20    }
21}

JavaScript Solution

1
2javascript
3var longestArithSeqLength = function(A) {
4    let max = 0;
5    let dp = Array(A.length).fill().map(() => new Map());  // Create a map to hold our dynamic programming state
6    for (let i = 0; i < A.length; i++) {
7        for (let j = 0; j < i; j++) {  // For the current element, check against all elements before it
8            let diff = A[i] - A[j];  // Calculate the difference between current element and previous element
9            // The state is represented by current index i and difference diff
10            // If there already exists such a state, we use the maximum value of existing one and current
11            // Otherwise we start from 2
12            dp[i].set(diff, Math.max((dp[j].get(diff) || 1) + 1, dp[i].get(diff) || 2));
13            max = Math.max(max, dp[i].get(diff));  // Update the maximum value
14        }
15    }
16    return max;  // Return the maximum value
17};

All these solutions have a time complexity of O(N^2) where N is the number of elements in the array. Each element is compared with every other element in the array to determine the longest arithmetic sequence.

In terms of space complexity, the solutions also require O(N^2) space to store the dynamic programming states. The dictionary or map uses two keys for each combination of elements - one for the index and one for the difference.

For further improvements, it might be possible to optimize space usage by using an integer array instead of hashmap if the difference values are within a small range.

These solutions provide a powerful demonstration of dynamic programming and how it leverages solving smaller sub-problems to construct the solution for larger problems. This makes the problem of finding longest arithmetic subsequence a classic example of demonstrating dynamic programming in real-world scenarios.

It's also worth mentioning that the JavaScript solution is more similar to the Python solution in that it uses conceptually similar constructs like dictionaries (Maps) and the map() function. The Java and C# solutions, on the other hand, use built-in features of respective languages like the HashMap<> and Dictionary<> classes for attaching additional information to an element of the array.

All these solutions further illustrate how the application of different programming languages' features and constructs can solve the same problem.