Scale Engineer

Longest Arithmetic Subsequence of Given Difference

Med
#1137Time: 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: O(1), as we only use a few variables to store the current state, regardless of the input size.
Patterns
Dynamic Programming
Data structures
ArrayHash Table

Prompt

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 <= 105
  • -104 <= arr[i], difference <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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

Time

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

O(1), as we only use a few variables to store the current state, regardless of the input size.

Trade-offs

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.

Solutions

/** * @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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem