Skip to main content

1218. Longest Arithmetic Subsequence of Given Difference

medium

Longest subsequence whose consecutive elements differ by exactly d. A single hash map keyed by element value — no nested loop needed.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i], difference <= 10^4

Examples

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].

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Fixing the difference lets you replace per-index dp arrays with a single value-indexed hash map.

Hint 2

dp[v] = length of the longest valid chain ending at value v. For each x do dp[x] = dp[x - difference] + 1, default 1.

Hint 3

Track and return the running max. O(n) time, O(n) space.

Solution approach

Reveal approach

Because the difference is fixed, replace the per-index 2D DP with a single hash map dp where dp[v] is the length of the longest valid arithmetic subsequence ending at value v. Sweep arr once. For each x compute dp[x] = dp.get(x - difference, 0) + 1 — chain x onto the best subsequence ending at x - difference. Track the max as you go. Return the max. The single-pass design works because subsequence order matches array order: when you see x at position i, any earlier x - difference has been recorded. O(n) time, O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dynamic-programming
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Longest Arithmetic Subsequence of Given Difference and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →