Leetcode 1027: Longest Arithmetic Subsequence

Input: The input consists of a single array of integers.

Example: nums = [5,10,15,20]

Constraints:

• 2 <= nums.length <= 1000

• 0 <= nums[i] <= 500

Output: The output is a single integer representing the length of the longest arithmetic subsequence in the given array.

Example: Output: 4

Constraints:

• The arithmetic subsequence is derived by deleting some elements without changing the order.

Goal: The goal is to find the length of the longest subsequence with a constant difference between consecutive elements. This can be done using dynamic programming.

Steps:

• 1. Use dynamic programming with a hash map to track the longest arithmetic subsequences for each difference between pairs of elements.

• 2. Iterate through each pair of elements in the array and compute the difference.

• 3. Update the hash map with the longest subsequence length for the calculated difference.

• 4. Keep track of the longest subsequence found during the iteration.

Goal: The solution must handle arrays with up to 1000 elements efficiently.

Steps:

• The solution must compute the longest subsequence in O(n^2) time complexity.

Assumptions:

• The input array has at least 2 elements.

• Input: Input: nums = [5,10,15,20]

• Explanation: In this example, the difference between each consecutive pair of elements is 5. The entire array forms an arithmetic subsequence with length 4.

• Input: Input: nums = [10, 5, 15, 25, 30]

• Explanation: Here, the longest arithmetic subsequence is [5, 15, 25] with a difference of 10, so the output is 3.

Approach: We can solve this problem using dynamic programming (DP) where we maintain a hash map for each element to store the length of the longest subsequence for each difference encountered.

Observations:

• The problem involves finding subsequences, which suggests a dynamic programming approach.

• The use of hash maps allows us to efficiently track the longest subsequences for each difference, reducing redundant calculations.

Steps:

• 1. Initialize a vector of hash maps where each element's map tracks the length of subsequences for each possible difference.

• 2. Loop through each pair of elements in the array to calculate the difference between them.

• 3. Update the map for the current element based on the difference and the longest subsequence length found so far.

• 4. The longest subsequence will be the maximum length stored in the hash maps.

Empty Inputs:

• An array with fewer than 2 elements should not be given (based on the constraints).

Large Inputs:

• The solution must efficiently handle arrays with up to 1000 elements.

Special Values:

• If all elements are the same, the longest arithmetic subsequence is the entire array, since the difference is 0.

Constraints:

• The array will not contain values outside the range 0 to 500.

int longestArithSeqLength(vector<int>& nums) {
    
    int n = nums.size();
    vector<unordered_map<int, int>> mp;
    mp.resize(n);
    int res = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            int d = nums[j] - nums[i];
            if(mp[j].count(d)) mp[i][d] = max(mp[i][d], mp[j][d] + 1);
            else mp[i][d] = max(mp[i][d], 2);
            res = max(mp[i][d], res);
        }
    }
    return res;
}

1 : Function Definition

int longestArithSeqLength(vector<int>& nums) {

Define the function `longestArithSeqLength` which calculates the length of the longest arithmetic subsequence in the given array.

2 : Initialize Size

    int n = nums.size();

Store the size of the input array `nums` into the variable `n`.

3 : Data Structure Initialization

    vector<unordered_map<int, int>> mp;

Declare a vector of unordered maps to store the difference and its count for each element in the array.

4 : Resize Vector

    mp.resize(n);

Resize the vector of unordered maps to the size of the input array.

5 : Initialize Result

    int res = 1;

Initialize the result variable `res` to 1, as the minimum possible arithmetic subsequence length is 1.

6 : Outer Loop

    for(int i = 0; i < n; i++) {

Iterate over the array elements with index `i` as the end of a potential arithmetic subsequence.

7 : Inner Loop

        for(int j = 0; j < i; j++) {

Iterate over previous elements with index `j` to calculate the difference `d` between elements at indices `j` and `i`.

8 : Calculate Difference

            int d = nums[j] - nums[i];

Calculate the difference `d` between elements at indices `j` and `i`.

9 : Update Map

            if(mp[j].count(d)) mp[i][d] = max(mp[i][d], mp[j][d] + 1);

If the difference `d` exists in the map for index `j`, update the map for index `i` with the incremented count of the subsequence.

10 : Initialize Difference

            else mp[i][d] = max(mp[i][d], 2);

If the difference `d` does not exist in the map for index `j`, initialize it with a value of 2.

11 : Update Result

            res = max(mp[i][d], res);

Update the result `res` to the maximum length found so far.

12 : Return Result

    return res;

Return the length of the longest arithmetic subsequence.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: The time complexity is O(n^2) due to the nested loop over pairs of elements.

Best Case: O(n)

Worst Case: O(n^2)

Description: The space complexity is O(n^2) due to the hash maps storing subsequences for each difference.

Leetcode 1027: Longest Arithmetic Subsequence

Explore →