Skip to main content

1027. Longest Arithmetic Subsequence

medium

Longest subsequence with constant pairwise difference. Per-index hash map keyed by difference — every (i, d) pair stores the running length.

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 is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements, and 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 longest arithmetic subsequence ending at i with common difference d.

Hint 2

Transition: dp[i][d] = dp[j][d] + 1 for every j < i with nums[i] - nums[j] == d. Default 1 if no such j.

Hint 3

Use an array of hash maps so d can be any integer without enumerating a range.

Solution approach

Reveal approach

Use an array of hash maps dp[0..n-1] where dp[i] maps a common-difference d to the length of the longest arithmetic subsequence ending at index i with that difference. For each i from 0 to n-1, for each j from 0 to i-1, compute d = nums[i] - nums[j]. Then dp[i][d] = dp[j].get(d, 1) + 1 — either extend the arithmetic chain that ended at j with the same difference, or start a length-2 chain (j, i). Track the global max. Return max length. O(n^2) time, O(n^2) space.

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
  • Google

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →