Longest Arithmetic Subsequence of Given Difference

MEDIUM

Description

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.

Example 1:

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

1 <= arr.length <= 10⁵
-10⁴ <= arr[i], difference <= 10⁴

Approaches

Checkout 3 different approaches to solve Longest Arithmetic Subsequence of Given Difference. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach iterates through every element of the array, considering each as a potential starting point for an arithmetic subsequence. For each starting element, it scans the rest of the array to find subsequent elements that fit the arithmetic progression with the given difference. It's a straightforward brute-force method.

Algorithm

Initialize a variable maxLength to 1.
Iterate through the input array arr with an index i from 0 to n-1.
For each i, consider arr[i] as the start of a potential subsequence. Initialize currentLength = 1 and lastElement = arr[i].
Start a nested loop with index j from i+1 to n-1.
Inside the nested loop, check if arr[j] is equal to lastElement + difference.
If it is, increment currentLength and update lastElement to arr[j].
After the inner loop finishes, update maxLength with the maximum of maxLength and currentLength.
After the outer loop finishes, return maxLength.

The brute-force strategy involves a nested loop structure. The outer loop selects a starting element for a subsequence. The inner loop then traverses the remainder of the array to find the next elements that maintain the required difference. We keep track of the longest such subsequence found starting from any element.

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            int currentLength = 1;
            int lastElement = arr[i];
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == lastElement + difference) {
                    currentLength++;
                    lastElement = arr[j];
                }
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in `arr`. The nested loops lead to a quadratic time complexity, as for each element, we potentially scan the rest of the array.Space Complexity: O(1), as we only use a few variables to store the current state, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space, making it memory efficient.

Cons:

Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.

Code Solutions

Checking out 4 solutions in different languages for Longest Arithmetic Subsequence of Given Difference. Click on different languages to view the code.

/** * @param {number[]} arr * @param {number} difference * @return {number} */ var longestSubsequence =
  function (arr, difference) {
    const f = new Map();
    for (const x of arr) {
      f.set(x, (f.get(x - difference) || 0) + 1);
    }
    return Math.max(...f.values());
  };

Video Solution

Watch the video walkthrough for Longest Arithmetic Subsequence of Given Difference

Patterns:

Dynamic Programming

Data Structures:

ArrayHash Table