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

More DP 1D practice problems

See all DP 1D problems →