Skip to main content

1027. Longest Arithmetic Subsequence

medium

Find the length of the longest arithmetic subsequence in an array. 2D DP keyed on (index, common difference) — every pair (i, j) with j < i extends some sequence ending at j with difference nums[i] - nums[j].

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

Problem

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums. Note that: A subsequence of an array is a list nums[i1], nums[i2], ..., nums[ik] with 0 <= i1 < i2 < ... < ik <= nums.length - 1. A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Constraints

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

Examples

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

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

Define dp[i][d] = length of the longest arithmetic subsequence ending at index i with common difference d.

Hint 2

For each pair (j, i) with j < i: d = nums[i] - nums[j]. dp[i][d] = max(dp[i][d], dp[j][d] + 1) (extend), with dp[i][d] at least 2 (the pair (j, i) alone).

Hint 3

Use a hash map per index since d can be negative or large.

Hint 4

Global answer is the maximum value across all (i, d). O(n^2) time.

Solution approach

Reveal approach

Bottom-up DP indexed by (end position, common difference). Maintain dp[i] as a hash map from difference d to the length of the longest arithmetic subsequence ending at index i with that difference. For each pair (j, i) with j < i, compute d = nums[i] - nums[j], then dp[i][d] = (dp[j].get(d, 1)) + 1 — extending whichever sequence ended at j with the same d, defaulting to 1 if there is no such sequence yet (so two elements alone give length 2). Track the global max as you fill. Time O(n^2), space O(n^2) in the worst case. Listed in dp-2d because the state is genuinely (i, d) — a 2D table when d is bounded, a 2D hash structure otherwise.

Complexity

Time
O(n^2)
Space
O(n^2)

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 and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →