Jobs

Interviews

Discussions

Longest Arithmetic Subsequence of Given Difference

Medium

Google

2 views

Topics:

ArraysDynamic Programming

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

For example:

arr = [1,2,3,4], difference = 1. The longest arithmetic subsequence is [1,2,3,4]. The function should return 4.
arr = [1,3,5,7], difference = 1. The longest arithmetic subsequence is any single element. The function should return 1.
arr = [1,5,7,8,5,3,4,2,1], difference = -2. The longest arithmetic subsequence is [7,5,3,1]. The function should return 4.

Write a function that efficiently finds the length of the longest arithmetic subsequence.

Longest Arithmetic Subsequence of Given Difference

Medium

Google

2 views

Topics:

ArraysDynamic Programming

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

For example:

arr = [1,2,3,4], difference = 1. The longest arithmetic subsequence is [1,2,3,4]. The function should return 4.
arr = [1,3,5,7], difference = 1. The longest arithmetic subsequence is any single element. The function should return 1.
arr = [1,5,7,8,5,3,4,2,1], difference = -2. The longest arithmetic subsequence is [7,5,3,1]. The function should return 4.

Write a function that efficiently finds the length of the longest arithmetic subsequence.

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 possible ranges for the integers in the input array and the given difference?
Can the input array be empty or null? If so, what should I return?
If there are multiple longest arithmetic subsequences with the given difference, should I return any one of them, or is there a preference?
Are duplicate values allowed in the input array, and if so, how should they be handled in determining the subsequence?
Is the input array guaranteed to be sorted?

Brute Force Solution

Approach

The brute force way to solve this is to check every possible group of numbers to see if it forms the sequence we want. We will look at every possible combination of numbers and see if they fit the rule.

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

Start by picking the first number in our group.
Then, consider every number after the first to see if it fits the sequence rule with the first number.
If it fits, add it to our group. If it doesn't, try the next number.
Repeat this process, looking for more numbers that fit the sequence rule and adding them to the group if they do.
Once we've gone through all the numbers, we have one possible sequence. Remember how long that sequence is.
Now, start again, but this time begin with the second number as the start of our sequence.
Repeat the whole process above, checking every possible sequence and remembering its length.
Do this for every starting number in the original list.
Finally, compare the lengths of all the sequences we found and pick the longest one.

Code Implementation

def longest_arithmetic_subsequence_brute_force(numbers, difference):
    longest_sequence_length = 0

    for starting_index in range(len(numbers)):
        current_sequence_length = 1
        current_sequence = [numbers[starting_index]]

        # Start the sequence with a new value from input
        for next_index in range(starting_index + 1, len(numbers)):
            if numbers[next_index] - current_sequence[-1] == difference:
                current_sequence.append(numbers[next_index])
                current_sequence_length += 1

        # Store the sequence length found
        if current_sequence_length > longest_sequence_length:
            longest_sequence_length = current_sequence_length

    return longest_sequence_length

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each element of the input array of size n as a potential starting point for an arithmetic subsequence. For each starting element, it then iterates through the remaining elements to check if they can extend the subsequence. This nested loop structure implies that, in the worst case, every pair of elements needs to be considered. The total number of pair checks approximates n * (n-1) / 2 operations. Therefore, the time complexity simplifies to O(n^2).

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating through the input array and comparing elements. It doesn't explicitly create any additional data structures like arrays, hash maps, or sets to store intermediate results or visited elements. The length of the current arithmetic subsequence is tracked by a few integer variables whose size is independent of the input size N, where N is the number of elements in the input array. Therefore, the auxiliary space complexity remains constant, regardless of the size of the input.

Optimal Solution

Approach

The goal is to find the longest sequence of numbers where the difference between adjacent numbers is constant. Instead of checking every possible sequence, we'll remember the lengths of the arithmetic sequences we've seen so far, building them up as we go.

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

Go through the numbers one by one.
For each number, check if it can extend any of the arithmetic sequences we've already found. We can do this by looking for the previous number in the sequence (current number minus the difference).
If we find the previous number, it means we can add the current number to that sequence, making it one number longer.
If we don't find the previous number, it means we're starting a new arithmetic sequence of length one.
Keep track of the longest sequence we've found so far. As we go through all the numbers, we update the longest sequence if we find a longer one.
By the end, we'll know the length of the longest arithmetic sequence with the given difference.

Code Implementation

def longest_arithmetic_subsequence(numbers, difference):
    sequence_lengths = {}
    longest_sequence = 0

    for number in numbers:
        # Check for the previous number's sequence length
        previous_number = number - difference
        if previous_number in sequence_lengths:

            sequence_lengths[number] = sequence_lengths[previous_number] + 1
        # Start a new sequence if previous not found
        else:

            sequence_lengths[number] = 1

        # Keep track of the longest arithmetic sequence
        longest_sequence = max(longest_sequence, sequence_lengths[number])

    return longest_sequence

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the 'n' numbers in the input array once. For each number, it performs a constant time lookup in a hash map (or dictionary) to check if the previous number in the arithmetic sequence exists. Because each number is processed once, with a constant-time operation, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a data structure (likely a hash map or dictionary based on the description's 'remembering the lengths of arithmetic sequences') to store the lengths of arithmetic subsequences ending at each number encountered so far. In the worst-case scenario, every number in the input array can potentially be the end of a different arithmetic subsequence, leading to the storage of N entries in this data structure, where N is the number of elements in the input array. Therefore, the auxiliary space used is proportional to the size of the input array. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or an empty list, depending on problem specification, since no arithmetic subsequence can be formed.
Array with a single element	Return 1, as a single element can be considered an arithmetic subsequence of length 1.
Array with two elements not forming an arithmetic sequence	Return 1, as each element forms a subsequence of length 1.
Input array with all identical elements and a difference of 0	Return the length of the array, as the entire array is an arithmetic subsequence.
Input array with all identical elements and a non-zero difference	Return 1, as no subsequence of length greater than 1 is possible.
Large input array that might cause memory issues with dynamic programming	Consider optimizing memory usage by using a rolling array or hash map if memory becomes a bottleneck.
Integer overflow when calculating the next expected value in the sequence.	Use long data type to prevent integer overflow during calculations of next values, or check before calculation
Array contains negative numbers	The standard hash map approach will correctly handle negative numbers as keys.

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 possible ranges for the integers in the input array and the given difference?
Can the input array be empty or null? If so, what should I return?
If there are multiple longest arithmetic subsequences with the given difference, should I return any one of them, or is there a preference?
Are duplicate values allowed in the input array, and if so, how should they be handled in determining the subsequence?
Is the input array guaranteed to be sorted?

Brute Force Solution

Approach

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

Start by picking the first number in our group.
Then, consider every number after the first to see if it fits the sequence rule with the first number.
If it fits, add it to our group. If it doesn't, try the next number.
Repeat this process, looking for more numbers that fit the sequence rule and adding them to the group if they do.
Once we've gone through all the numbers, we have one possible sequence. Remember how long that sequence is.
Now, start again, but this time begin with the second number as the start of our sequence.
Repeat the whole process above, checking every possible sequence and remembering its length.
Do this for every starting number in the original list.
Finally, compare the lengths of all the sequences we found and pick the longest one.

Code Implementation

def longest_arithmetic_subsequence_brute_force(numbers, difference):
    longest_sequence_length = 0

    for starting_index in range(len(numbers)):
        current_sequence_length = 1
        current_sequence = [numbers[starting_index]]

        # Start the sequence with a new value from input
        for next_index in range(starting_index + 1, len(numbers)):
            if numbers[next_index] - current_sequence[-1] == difference:
                current_sequence.append(numbers[next_index])
                current_sequence_length += 1

        # Store the sequence length found
        if current_sequence_length > longest_sequence_length:
            longest_sequence_length = current_sequence_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:

Go through the numbers one by one.
For each number, check if it can extend any of the arithmetic sequences we've already found. We can do this by looking for the previous number in the sequence (current number minus the difference).
If we find the previous number, it means we can add the current number to that sequence, making it one number longer.
If we don't find the previous number, it means we're starting a new arithmetic sequence of length one.
Keep track of the longest sequence we've found so far. As we go through all the numbers, we update the longest sequence if we find a longer one.
By the end, we'll know the length of the longest arithmetic sequence with the given difference.

Code Implementation

def longest_arithmetic_subsequence(numbers, difference):
    sequence_lengths = {}
    longest_sequence = 0

    for number in numbers:
        # Check for the previous number's sequence length
        previous_number = number - difference
        if previous_number in sequence_lengths:

            sequence_lengths[number] = sequence_lengths[previous_number] + 1
        # Start a new sequence if previous not found
        else:

            sequence_lengths[number] = 1

        # Keep track of the longest arithmetic sequence
        longest_sequence = max(longest_sequence, sequence_lengths[number])

    return longest_sequence

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or an empty list, depending on problem specification, since no arithmetic subsequence can be formed.
Array with a single element	Return 1, as a single element can be considered an arithmetic subsequence of length 1.
Array with two elements not forming an arithmetic sequence	Return 1, as each element forms a subsequence of length 1.
Input array with all identical elements and a difference of 0	Return the length of the array, as the entire array is an arithmetic subsequence.
Input array with all identical elements and a non-zero difference	Return 1, as no subsequence of length greater than 1 is possible.
Large input array that might cause memory issues with dynamic programming	Consider optimizing memory usage by using a rolling array or hash map if memory becomes a bottleneck.
Integer overflow when calculating the next expected value in the sequence.	Use long data type to prevent integer overflow during calculations of next values, or check before calculation
Array contains negative numbers	The standard hash map approach will correctly handle negative numbers as keys.