Formatted question description: https://leetcode.ca/all/1218.html

1218. Longest Arithmetic Subsequence of Given Difference

Level

Medium

Description

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.

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

Constraints:

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

Solution

Use dynamic programming. Create an array subLengths of length arr.length, where subLengths[i] represents the length of the longest arithmetic subsequence with difference difference that ends at index i. Use a map to store each number and the last index that the number occurs. Initially, set subLengths[0] = 1 and put the key-value pair (arr[0], 0) into the map.

Loop over arr starting from index 1. At each index i, obtain the number at index i and the previous number in the arithmetic subsequence. If the previous number exists in the key set of the map, then obtain the previous number’s index prevIndex and the previous subsequence length subLengths[prevIndex], set subLengths[i] = subLengths[prevIndex] + 1, and update the maximum length of arithmetic subsequence as well. If the previous number does not exist in the key set of the map, then simply set subLengths[i] = 1. For each index i, put the key-value pair (arr[i], i) into the map.

Finally, return the maximum length of arithmetic subsequence.

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int length = arr.length;
        int[] subLengths = new int[length];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        subLengths[0] = 1;
        map.put(arr[0], 0);
        int max = 1;
        for (int i = 1; i < length; i++) {
            int num = arr[i];
            int prevNum = num - difference;
            if (map.containsKey(prevNum)) {
                int prevIndex = map.get(prevNum);
                subLengths[i] = subLengths[prevIndex] + 1;
                max = Math.max(max, subLengths[i]);
            } else
                subLengths[i] = 1;
            map.put(num, i);
        }
        return max;
    }
}

All Problems

All Solutions