Leetcode 1027 - Longest Arithmetic Subsequence
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Understanding the problem
The problem statement on LeetCode reads as follows:
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], …, A[i_k] with 0 <= i_1 < i_2 < … < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation: The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation: The longest arithmetic subsequence is [4,7,10].
Plan your solution
One way to solve this problem is to use dynamic programming. We can create a table dp
where dp[i][j]
represents the length of the longest arithmetic subsequence ending at index i
in the input array with a difference of j
. Then, we can iterate through the input array and for each element, we can check the previous elements and update the dp
table accordingly. Specifically, for each element A[i]
, we can set dp[i][A[i] - A[j]]
to be the maximum of dp[i][A[i] - A[j]]
and dp[j][A[i] - A[j]] + 1
for all j
such that j < i
and A[i] - A[j]
is a valid difference. Finally, we can return the maximum value in the dp
table.
Implement your solution
Now that we have a plan, let’s implement it in Python.
def longestArithSeqLength(A):
# Initialize the dp table with all 2s
dp = [[2] * (100001) for _ in range(len(A))]
# Iterate through the array
for i in range(1, len(A)):
# Iterate through the previous elements
for j in range(i):
# Calculate the difference between the current element and the previous element
diff = A[i] - A[j]
# If the difference is valid, update the dp table
if diff >= 0 and diff <= 100000:
dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1)
# Return the maximum value in the dp table
return max(max(row) for row in dp)
Test your solution
Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Longest Arithmetic Subsequence” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.
For example, we can test our solution with an array that has no arithmetic subsequences, an array that has only one arithmetic subsequence, an array that has multiple arithmetic subsequences with different lengths and differences, and an array that has multiple arithmetic subsequences with the same length but different differences. We can also test our solution with arrays of different lengths and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Related:
Related Posts
- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- How do you guys get good at DP?
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Question 1299 on leetcode
- Leetcode 240 - Search a 2D Matrix II
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- advanced-applications-of-binary-search
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 1283 - Find the Smallest Divisor Given a Threshold
- Leetcode 74 - Search a 2D Matrix
- Leetcode 300 - Longest Increasing Subsequence
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- a-binary-search-template
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together