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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →