Jobs

Interviews

Discussions

Longest Arithmetic Subsequence

Medium

Asked by:

More companies

39 views

Topics:

ArraysDynamic Programming

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:  The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:  The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:  The longest arithmetic subsequence is [20,15,10,5].

Constraints:

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Try coding it in LeetCode

Longest Arithmetic Subsequence

Medium

Asked by:

39 views

Topics:

ArraysDynamic Programming

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:  The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:  The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:  The longest arithmetic subsequence is [20,15,10,5].

Constraints:

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array, `nums`? Are we expecting it to be very large?
Can the input array `nums` contain negative integers, zero, or any non-integer values?
If there is no arithmetic subsequence of length greater than or equal to 2, what should the function return?
If there are multiple arithmetic subsequences with the same maximum length, is it sufficient to return the length of any one of them?
Does the order of the elements in the longest arithmetic subsequence need to be the same as in the original array? (e.g., can elements be skipped to form the subsequence)?

Brute Force Solution

Approach

The brute force approach to finding the longest arithmetic sequence means we're going to check every possible sequence. We'll look at all combinations of numbers, see if they form an arithmetic sequence, and if so, keep track of how long that sequence is. Eventually, we will have checked them all, and we can pick the longest one we found.

Here's how the algorithm would work step-by-step:

Pick the first number in the list.
Then pick a second number from the list that comes after the first number.
Figure out the difference between these two numbers.
Now, go through the rest of the list and see if any other numbers follow the same difference to extend the sequence.
If you find a number that fits, add it to your sequence and keep searching for more numbers with the same difference.
Keep track of how many numbers are in this sequence.
Once you've gone through the entire list, start over by picking a different second number to start a new sequence from the initial first number.
After you've tried all possible second numbers, pick a different first number and repeat the whole process.
Do this until you have tried every possible pair of starting numbers.
Compare the lengths of all the sequences you found and choose the longest one.

Code Implementation

def longest_arithmetic_subsequence_brute_force(numbers):
    longest_sequence_length = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Determine the common difference
            common_difference = numbers[second_index] - numbers[first_index]

            current_sequence_length = 2
            current_number = numbers[second_index]

            # Try to extend the sequence
            for third_index in range(second_index + 1, list_length):
                if numbers[third_index] == current_number + common_difference:
                    # Found next number in arithmetic subsequence
                    current_sequence_length += 1
                    current_number = numbers[third_index]

            # Keep track of longest sequence found so far
            if current_sequence_length > longest_sequence_length:
                longest_sequence_length = current_sequence_length

    # Need to return 1 if the input array has length 0 or 1
    if list_length <= 1:
        return list_length
    
    return longest_sequence_length

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible pairs of numbers in the array, taking O(n^2) time. For each pair, it searches for additional elements to extend the arithmetic subsequence. In the worst case, this search iterates through the remaining elements of the array, taking O(n) time. Therefore, the overall time complexity is O(n^2 * n) which simplifies to O(n^3).

Space Complexity

O(1) – The described brute force algorithm primarily uses a few variables to store the lengths of sequences and iterate through the input list. It does not involve creating any auxiliary data structures like arrays, hashmaps, or stacks that scale with the input size N (where N is the number of elements in the list). Therefore, the additional memory required remains constant, irrespective of the input size.

Optimal Solution

Approach

The goal is to find the longest sequence of numbers where the difference between consecutive numbers is constant. Instead of checking every possible sequence, we'll efficiently remember the longest sequences we've seen so far for each possible difference.

Here's how the algorithm would work step-by-step:

For each number in the list, consider it as the end of a potential arithmetic sequence.
For every number that comes before it, calculate the difference between the two numbers.
Check if there's an existing arithmetic sequence ending with the previous number and having that difference. If so, extend that sequence by adding the current number to it.
If there isn't, then start a new arithmetic sequence of length two using these two numbers.
Keep track of the length of the longest arithmetic sequence seen so far for each possible difference.
Return the maximum length found across all differences. This avoids redundant calculations.

Code Implementation

def longest_arithmetic_subsequence(numbers):
    # Store the length of longest arithmetic sequence ending at each index.
    sequences_by_index = {}
    max_length = 0

    for index in range(len(numbers)):
        sequences_by_index[index] = {}
        for previous_index in range(index):
            difference = numbers[index] - numbers[previous_index]

            # Extend the sequence if the difference is found.
            if difference in sequences_by_index[previous_index]:
                current_length = sequences_by_index[previous_index][difference] + 1
            # Start a new sequence if the difference is new.
            else:
                current_length = 2

            sequences_by_index[index][difference] = current_length

            # Update the max length found.
            max_length = max(max_length, current_length)

    #The problem requires us to return 0 if the input is invalid.
    if len(numbers) == 0:
        return 0

    return max_length

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n numbers in the input list. For each number, it then iterates through all preceding numbers to calculate the difference between them. This inner loop, on average, will execute approximately n/2 times for each outer loop iteration. Therefore, the dominant operation involves nested loops, resulting in roughly n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(N^2) – The algorithm uses a dictionary (or hash map) to store the lengths of arithmetic subsequences ending at each number for every possible difference. In the worst-case scenario, for each of the N numbers in the input, we may need to store subsequence lengths for all possible differences encountered with the preceding numbers. This leads to storing subsequence lengths for approximately N * N possible combinations of ending numbers and differences, resulting in auxiliary space proportional to N^2. Thus, the space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as an arithmetic subsequence requires at least two elements.
Input array with only one element	Return 1, since a single element can be considered a subsequence of length 1 (though not arithmetic per se).
Input array with two identical elements	Return 2, as two identical elements form an arithmetic subsequence with common difference 0.
Input array with a large number of elements (scalability)	Ensure the algorithm's time complexity is efficient (e.g., O(n^2) or better) to handle large inputs without exceeding time limits.
Input array with all identical elements	Return the length of the array, as any two elements will form an arithmetic subsequence.
Input array with negative numbers, zeros, and positive numbers	The solution should correctly handle all integer values without overflow issues as long as the differences are representable.
Input array where no arithmetic subsequence exists (e.g., randomly distributed numbers)	The solution should return 1, as the longest subsequence is each individual element.
Integer overflow when calculating the difference between numbers	Use appropriate data types (e.g., long) to store intermediate results to prevent integer overflow during difference calculation.

Null or empty input array

How to Handle:

Return 0 as an arithmetic subsequence requires at least two elements.

Input array with only one element

How to Handle:

Return 1, since a single element can be considered a subsequence of length 1 (though not arithmetic per se).

Input array with two identical elements

How to Handle:

Return 2, as two identical elements form an arithmetic subsequence with common difference 0.

Input array with a large number of elements (scalability)

How to Handle:

Ensure the algorithm's time complexity is efficient (e.g., O(n^2) or better) to handle large inputs without exceeding time limits.

Input array with all identical elements

How to Handle:

Return the length of the array, as any two elements will form an arithmetic subsequence.

Input array with negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly handle all integer values without overflow issues as long as the differences are representable.

Input array where no arithmetic subsequence exists (e.g., randomly distributed numbers)

How to Handle:

The solution should return 1, as the longest subsequence is each individual element.

Integer overflow when calculating the difference between numbers

How to Handle:

Use appropriate data types (e.g., long) to store intermediate results to prevent integer overflow during difference calculation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array, `nums`? Are we expecting it to be very large?
Can the input array `nums` contain negative integers, zero, or any non-integer values?
If there is no arithmetic subsequence of length greater than or equal to 2, what should the function return?
If there are multiple arithmetic subsequences with the same maximum length, is it sufficient to return the length of any one of them?
Does the order of the elements in the longest arithmetic subsequence need to be the same as in the original array? (e.g., can elements be skipped to form the subsequence)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick the first number in the list.
Then pick a second number from the list that comes after the first number.
Figure out the difference between these two numbers.
Now, go through the rest of the list and see if any other numbers follow the same difference to extend the sequence.
If you find a number that fits, add it to your sequence and keep searching for more numbers with the same difference.
Keep track of how many numbers are in this sequence.
Once you've gone through the entire list, start over by picking a different second number to start a new sequence from the initial first number.
After you've tried all possible second numbers, pick a different first number and repeat the whole process.
Do this until you have tried every possible pair of starting numbers.
Compare the lengths of all the sequences you found and choose the longest one.

Code Implementation

def longest_arithmetic_subsequence_brute_force(numbers):
    longest_sequence_length = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Determine the common difference
            common_difference = numbers[second_index] - numbers[first_index]

            current_sequence_length = 2
            current_number = numbers[second_index]

            # Try to extend the sequence
            for third_index in range(second_index + 1, list_length):
                if numbers[third_index] == current_number + common_difference:
                    # Found next number in arithmetic subsequence
                    current_sequence_length += 1
                    current_number = numbers[third_index]

            # Keep track of longest sequence found so far
            if current_sequence_length > longest_sequence_length:
                longest_sequence_length = current_sequence_length

    # Need to return 1 if the input array has length 0 or 1
    if list_length <= 1:
        return list_length
    
    return longest_sequence_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each number in the list, consider it as the end of a potential arithmetic sequence.
For every number that comes before it, calculate the difference between the two numbers.
Check if there's an existing arithmetic sequence ending with the previous number and having that difference. If so, extend that sequence by adding the current number to it.
If there isn't, then start a new arithmetic sequence of length two using these two numbers.
Keep track of the length of the longest arithmetic sequence seen so far for each possible difference.
Return the maximum length found across all differences. This avoids redundant calculations.

Code Implementation

def longest_arithmetic_subsequence(numbers):
    # Store the length of longest arithmetic sequence ending at each index.
    sequences_by_index = {}
    max_length = 0

    for index in range(len(numbers)):
        sequences_by_index[index] = {}
        for previous_index in range(index):
            difference = numbers[index] - numbers[previous_index]

            # Extend the sequence if the difference is found.
            if difference in sequences_by_index[previous_index]:
                current_length = sequences_by_index[previous_index][difference] + 1
            # Start a new sequence if the difference is new.
            else:
                current_length = 2

            sequences_by_index[index][difference] = current_length

            # Update the max length found.
            max_length = max(max_length, current_length)

    #The problem requires us to return 0 if the input is invalid.
    if len(numbers) == 0:
        return 0

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as an arithmetic subsequence requires at least two elements.
Input array with only one element	Return 1, since a single element can be considered a subsequence of length 1 (though not arithmetic per se).
Input array with two identical elements	Return 2, as two identical elements form an arithmetic subsequence with common difference 0.
Input array with a large number of elements (scalability)	Ensure the algorithm's time complexity is efficient (e.g., O(n^2) or better) to handle large inputs without exceeding time limits.
Input array with all identical elements	Return the length of the array, as any two elements will form an arithmetic subsequence.
Input array with negative numbers, zeros, and positive numbers	The solution should correctly handle all integer values without overflow issues as long as the differences are representable.
Input array where no arithmetic subsequence exists (e.g., randomly distributed numbers)	The solution should return 1, as the longest subsequence is each individual element.
Integer overflow when calculating the difference between numbers	Use appropriate data types (e.g., long) to store intermediate results to prevent integer overflow during difference calculation.

Null or empty input array

How to Handle:

Return 0 as an arithmetic subsequence requires at least two elements.

Input array with only one element

How to Handle:

Return 1, since a single element can be considered a subsequence of length 1 (though not arithmetic per se).

Input array with two identical elements

How to Handle:

Return 2, as two identical elements form an arithmetic subsequence with common difference 0.

Input array with a large number of elements (scalability)

How to Handle:

Ensure the algorithm's time complexity is efficient (e.g., O(n^2) or better) to handle large inputs without exceeding time limits.

Input array with all identical elements

How to Handle:

Return the length of the array, as any two elements will form an arithmetic subsequence.

Input array with negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly handle all integer values without overflow issues as long as the differences are representable.

Input array where no arithmetic subsequence exists (e.g., randomly distributed numbers)

How to Handle:

The solution should return 1, as the longest subsequence is each individual element.

Integer overflow when calculating the difference between numbers

How to Handle:

Use appropriate data types (e.g., long) to store intermediate results to prevent integer overflow during difference calculation.