LeetCode 1218: Longest Arithmetic Subsequence of Given Difference Solution

Master LeetCode problem 1218 (Longest Arithmetic Subsequence of Given Difference), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1218. Longest Arithmetic Subsequence of Given Difference

Medium

Array Hash Table Dynamic Programming

Problem Explanation

Explanation:

Algorithmic Idea:
- We can solve this problem using dynamic programming.
- We will maintain a hashmap where the key is the current element arr[i] and the value is the length of the longest arithmetic subsequence ending at arr[i].
- For each element arr[i], we check if arr[i] - difference is present in the hashmap. If it is present, we update the length of the current subsequence as dp[arr[i]] = dp[arr[i] - difference] + 1.
- Finally, we find the maximum length of the subsequence in the hashmap.
Time Complexity: O(N), where N is the number of elements in the input array.
Space Complexity: O(N), where N is the number of elements in the input array.

Solution Code

import java.util.HashMap;

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer, Integer> dp = new HashMap<>();
        int maxLength = 1;
        
        for (int num : arr) {
            dp.put(num, dp.getOrDefault(num - difference, 0) + 1);
            maxLength = Math.max(maxLength, dp.get(num));
        }
        
        return maxLength;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1218 (Longest Arithmetic Subsequence of Given Difference)?

This page provides optimized solutions for LeetCode problem 1218 (Longest Arithmetic Subsequence of Given Difference) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1218 (Longest Arithmetic Subsequence of Given Difference)?

The time complexity for LeetCode 1218 (Longest Arithmetic Subsequence of Given Difference) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1218 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1218 in Java, C++, or Python.

Back to LeetCode Solutions