Longest Arithmetic Subsequence

📋

Problem

Imagine you are analyzing stock prices over days and want to find the longest period where the price changes by a fixed amount each day. This problem helps you identify such consistent trends.

Given an integer array nums, return the length of the longest arithmetic subsequence in nums. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. An arithmetic subsequence is a subsequence where the difference between consecutive elements is the same.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^4

Edge cases: Single element array → output 1All elements equal → output equals array lengthArray with no arithmetic subsequence longer than 2 → output 2

</>

IDE

def longestArithSeqLength(nums: list[int]) -> int:public int longestArithSeqLength(int[] nums)int longestArithSeqLength(vector<int>& nums)function longestArithSeqLength(nums)

def longestArithSeqLength(nums):
    # Write your solution here
    pass

class Solution {
    public int longestArithSeqLength(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function longestArithSeqLength(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 2Greedy approach that only checks consecutive pairs or first found subsequence.✅ Implement DP tracking lengths of subsequences by difference for all pairs: dp[i][diff] = dp[j][diff] + 1.

Wrong: 0Missing base case handling for empty input array.✅ Add guard clause: if not nums: return 0.

Wrong: 1Incorrect handling of single element arrays or all equal elements.✅ Return n if n < 2; handle difference 0 sequences properly.

Wrong: TLEUsing brute force O(n^3) approach instead of O(n^2) DP.✅ Use DP with hash maps to track differences and subsequence lengths in O(n^2) time.

Wrong: Less than actual max lengthOff-by-one errors or not initializing dp[i][diff] to 2 when first encountered.✅ Initialize dp[i][diff] = dp[j][diff] + 1 if exists else 2 for new differences.

✓

Test Cases

Handle base cases like empty and single-element arrays to proceed.

Focus on correct DP updates and avoid greedy traps.

Optimize your solution to O(n^2) time complexity to pass performance tests.

t1_01basic

Input{"nums":[3,6,9,12]}

Expected4

⏱ Performance - must finish in 2000ms

The whole array forms an arithmetic sequence with difference 3, length 4.

💡 Think about differences between pairs of elements.

💡 Use dynamic programming to track lengths of sequences by difference.

💡 Maintain a map of difference to longest subsequence length ending at each index.

Why it failed: Output less than 4 means failure to track sequences across multiple indices or incorrect difference calculation. Fix by updating dp[i][diff] = dp[j][diff] + 1 where j < i and diff = nums[i]-nums[j].

✓ Correctly identifies the longest arithmetic subsequence length.

t1_02basic

Input{"nums":[9,4,7,2,10]}

Expected3

⏱ Performance - must finish in 2000ms

Longest arithmetic subsequence is [4,7,10] with difference 3, length 3.

💡 Check all pairs and their differences.

💡 Use a hash map per index to store lengths by difference.

💡 Update lengths by extending previous subsequences with the same difference.

Why it failed: Output less than 3 means missing subsequences or incorrect dp updates. Fix by ensuring dp[i][diff] = dp[j][diff] + 1 if dp[j][diff] exists, else 2.

✓ Correctly computes longest arithmetic subsequence length for varied input.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subsequence, length 0.

💡 Consider what happens when input array is empty.

💡 Check for base case n=0 and return 0 immediately.

💡 Add a guard clause to handle empty input.

Why it failed: Returning non-zero or error on empty input means missing base case. Fix by adding if not nums: return 0 at start.

✓ Correctly handles empty input by returning 0.

t2_02edge

Input{"nums":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array has longest arithmetic subsequence length 1.

💡 Check behavior when array length is 1.

💡 Longest arithmetic subsequence length is at least 1 for single element.

💡 Return n if n < 2 as base case.

Why it failed: Returning 0 or error for single element means missing base case. Fix by returning n if n < 2.

✓ Correctly returns 1 for single element input.

t2_03edge

Input{"nums":[7,7,7,7]}

Expected4

⏱ Performance - must finish in 2000ms

All elements equal form arithmetic subsequence with difference 0, length equals array length.

💡 Consider difference zero when all elements are equal.

💡 Ensure dp tracks difference 0 correctly.

💡 Longest subsequence length equals array length if all equal.

Why it failed: Output less than 4 means ignoring difference 0 or not extending sequences properly. Fix by handling difference 0 in dp updates.

✓ Correctly handles all-equal elements with difference 0.

t3_01corner

Input{"nums":[1,3,5,7,9,2,4,6,8,10]}

Expected5

⏱ Performance - must finish in 2000ms

Longest arithmetic subsequence is [1,3,5,7,9] or [2,4,6,8,10] with difference 2, length 5.

💡 Beware of greedy approaches picking first subsequence found.

💡 Use DP to track all subsequences by difference.

💡 Update dp[i][diff] = dp[j][diff] + 1 for all valid j < i.

Why it failed: Output less than 5 means greedy approach failing to find longest subsequence. Fix by using DP with hash maps to track all differences.

✓ Correctly finds longest arithmetic subsequence despite interleaved sequences.

t3_02corner

Input{"nums":[1,2,4,7,11]}

Expected3

⏱ Performance - must finish in 2000ms

No arithmetic subsequence longer than 2 exists; longest length is 2.

💡 Check that subsequences of length 2 are valid.

💡 DP must initialize length 2 for new differences.

💡 Do not assume longer subsequences always exist.

Why it failed: Output greater than 2 means incorrect subsequence length calculation. Fix by initializing dp[i][diff] = 2 when difference first encountered.

✓ Correctly returns 2 when no longer arithmetic subsequence exists.

t3_03corner

Input{"nums":[1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81,85,89,93,97,101]}

Expected26

⏱ Performance - must finish in 2000ms

Strict arithmetic sequence with difference 4, length 26.

💡 Check that DP handles long sequences correctly.

💡 Avoid off-by-one errors in indexing.

💡 Ensure dp updates propagate through entire array.

Why it failed: Output less than 26 means off-by-one or incomplete DP updates. Fix by correctly iterating all pairs and updating dp[i][diff] = dp[j][diff] + 1.

✓ Correctly computes length for long arithmetic sequence.

t4_01performance

Input{"nums":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with strictly decreasing sequence difference -1; O(n^2) DP must complete within 2 seconds.

💡 O(n^3) brute force will time out here.

💡 Use O(n^2) DP with hash maps to track differences efficiently.

💡 Avoid nested loops beyond pairs to meet time constraints.

Why it failed: TLE indicates brute force or inefficient DP approach. Fix by implementing O(n^2) DP with hash maps tracking differences.

✓ Solution runs within time limit using O(n^2) DP approach.

Practice

1. Consider the following code snippet for finding the longest contiguous subarray with equal 0s and 1s. What is the value of max_length returned for input [0, 1, 0]?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

Hint: Track prefix sums and earliest indices carefully [OK]

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

2. What is the time complexity of the optimal single-pass pivot index algorithm that uses a running left sum and total sum?

medium

A. O(n) because it iterates through the array once, updating sums in constant time.

B. O(n^2) because of nested sum computations inside the loop.

C. O(n log n) due to sorting the array before processing.

D. O(n) time but O(n) space due to storing prefix sums.

Solution

1. Step 1: Analyze loop iterations

   The algorithm iterates through the array once, performing constant time operations per element.

2. Step 2: Confirm no nested loops or extra space

   There are no nested loops or sorting; space used is O(1) for running sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant time per element -> O(n) [OK]

Hint: Single loop with constant work per iteration -> O(n) [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Forgetting space is O(1) not O(n)

3. What is the time complexity of the optimal hash map frequency counting approach for finding the maximum number of k-sum pairs in an array of length n?

medium

A. O(n log n) due to sorting the array before processing

B. O(n) because each element is processed once with constant-time hash operations

C. O(n^2) because each element is compared with every other element

D. O(n) for iteration plus O(n) for building the frequency map, total O(2n) simplifies to O(n)

Solution

1. Step 1: Identify operations in hash map approach

   Each element is iterated once (O(n)) and frequency map updates are O(1) on average.

2. Step 2: Sum time components

   Building and updating frequency map is also O(n), so total is O(n) + O(n) = O(2n), which simplifies to O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity confirmed by single pass and constant-time map ops [OK]

Hint: Two O(n) steps sum to O(n), not O(n log n) [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause O(n^2)
• Ignoring constant factors in complexity

4. The following code attempts to count the number of subarrays with bounded maximum using the optimal approach, but it contains a subtle bug:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            # Bug: missing reset of length here
            pass
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

What is the bug in this code?

medium

A. The variable 'count' is not reset inside the loop, causing overcounting.

B. The function countAtMost should use max instead of length to track subarray size.

C. The 'length' variable is not reset to zero when encountering a number greater than bound.

D. The subtraction in numSubarrayBoundedMax should be reversed to avoid negative results.

Solution

1. Step 1: Understand the role of 'length'

   'length' tracks the length of the current valid subarray segment where elements ≤ bound.

2. Step 2: Identify the bug

   When an element > bound is encountered, 'length' must reset to 0 to avoid counting invalid subarrays. The code misses this reset, causing overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting 'length' on invalid elements is essential [OK]

Hint: Reset 'length' to zero on elements > bound [OK]

Common Mistakes:

• Forgetting to reset length
• Incorrect subtraction order
• Misusing count variable

5. Suppose the problem changes: now you want the longest substring with at most two distinct characters, but characters can be reused infinitely many times and the input string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Maintain a sliding window with frequency counts but optimize by using a fixed-size array for frequencies instead of a hash map.

B. Use a brute force nested loop approach with early breaks to handle reuse.

C. Use a priority queue to track the least recently used character to evict when distinct count exceeds two.

D. Switch to a dynamic programming approach that stores results for substrings with reuse allowed.

Solution

1. Step 1: Understand reuse and input size impact

   Characters can be reused infinitely, but the problem remains longest substring with at most two distinct chars. The input is very long, so efficiency is critical.

2. Step 2: Identify efficient data structure

   Using a fixed-size array for frequencies (size 128 for ASCII) is more efficient than a hash map, reducing overhead and ensuring O(n) time and O(1) space.

3. Step 3: Confirm approach correctness

   The sliding window logic remains the same, but frequency tracking is optimized for speed and memory, suitable for very long inputs with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Fixed-size array frequency tracking is optimal for large inputs with limited charset [OK]

Hint: Fixed-size array beats hash map for fixed charset [OK]

Common Mistakes:

• Using brute force despite input size
• Using complex data structures unnecessarily
• Switching to DP without need