Longest Arithmetic Subsequence

▶

Steps

setup

Initialize dp array and max_len

Create an array dp of empty hash maps, one for each element in nums, and initialize max_len to 0.

💡 This sets up the data structure to track subsequences ending at each index and prepares to record the longest length found.

Line:

n = len(nums)
dp = [dict() for _ in range(n)]
max_len = 0

💡 We need a separate map for each index to track subsequences ending there by difference.

traverse

Start outer loop with i=0

Begin iterating over nums with i=0; no inner loop runs because j < i is false.

💡 No pairs to compare yet; dp[0] remains empty and max_len unchanged.

Line:

for i in range(n):
    for j in range(i):

💡 The first element alone cannot form an arithmetic subsequence with a previous element.

compare

Start inner loop with i=1, j=0

Calculate difference diff = nums[1] - nums[0] = 6 - 3 = 3. Check dp[0] for diff=3.

💡 We look for existing subsequences ending at index 0 with difference 3 to extend.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 No existing subsequence with diff=3 at index 0 means we start a new subsequence of length 2 at index 1.

insert

Update dp[1] with diff=3 length=2

Insert dp[1][3] = prev_len + 1 = 2, representing a subsequence of length 2 ending at index 1 with difference 3.

💡 We record the new subsequence length for difference 3 at index 1.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 This step shows how subsequences are tracked per index and difference, and max_len updates accordingly.

compare

Start inner loop with i=2, j=0

Calculate diff = nums[2] - nums[0] = 9 - 3 = 6. Check dp[0] for diff=6.

💡 Looking for subsequences ending at index 0 with difference 6 to extend.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 No subsequence with diff=6 at index 0 means starting a new subsequence of length 2 at index 2.

insert

Update dp[2] with diff=6 length=2

Insert dp[2][6] = 2, starting a new subsequence ending at index 2 with difference 6.

💡 Record the new subsequence length for difference 6 at index 2.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 Tracking multiple differences per index allows capturing all possible subsequences.

compare

Continue inner loop with i=2, j=1

Calculate diff = nums[2] - nums[1] = 9 - 6 = 3. Check dp[1] for diff=3.

💡 Check if subsequence with difference 3 exists ending at index 1 to extend.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 Found existing subsequence to extend, so length will increase by 1.

update

Update dp[2] with diff=3 length=3

Update dp[2][3] = prev_len + 1 = 3, extending the subsequence ending at index 1 with difference 3.

💡 Extend the subsequence length for difference 3 at index 2.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 Subsequences can be extended by chaining differences across indices.

compare

Start inner loop with i=3, j=0

Calculate diff = nums[3] - nums[0] = 12 - 3 = 9. Check dp[0] for diff=9.

💡 Look for subsequences ending at index 0 with difference 9.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 No subsequence with diff=9 at index 0 means starting a new subsequence at index 3.

insert

Update dp[3] with diff=9 length=2

Insert dp[3][9] = 2, starting a new subsequence ending at index 3 with difference 9.

💡 Record the new subsequence length for difference 9 at index 3.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 Multiple subsequences with different differences can coexist at the same index.

compare

Continue inner loop with i=3, j=1

Calculate diff = nums[3] - nums[1] = 12 - 6 = 6. Check dp[1] for diff=6.

💡 Check if subsequence with difference 6 exists ending at index 1.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 No subsequence with diff=6 at index 1 means starting a new subsequence at index 3.

insert

Update dp[3] with diff=6 length=2

Insert dp[3][6] = 2, starting a new subsequence ending at index 3 with difference 6.

💡 Record the new subsequence length for difference 6 at index 3.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 dp[3] now tracks multiple differences with subsequence lengths.

compare

Continue inner loop with i=3, j=2

Calculate diff = nums[3] - nums[2] = 12 - 9 = 3. Check dp[2] for diff=3.

💡 Check if subsequence with difference 3 exists ending at index 2 to extend.

Line:

diff = nums[i] - nums[j]
prev_len = dp[j].get(diff, 1)

💡 Found subsequence to extend, so length will increase by 1.

update

Update dp[3] with diff=3 length=4

Update dp[3][3] = prev_len + 1 = 4, extending the subsequence ending at index 2 with difference 3.

💡 Extend the longest arithmetic subsequence to length 4 at index 3.

Line:

dp[i][diff] = prev_len + 1
max_len = max(max_len, dp[i][diff])

💡 This step captures the final extension of the longest arithmetic subsequence in the array.

reconstruct

End of loops, return max_len

All pairs processed; return max_len = 4 as the length of the longest arithmetic subsequence.

💡 The global maximum length found during iteration is the final answer.

Line:

return max_len if max_len > 0 else n

💡 The algorithm efficiently tracked and updated subsequences to find the longest length.

def longestArithSeqLength(nums):
    n = len(nums)  # STEP 1
    dp = [dict() for _ in range(n)]  # STEP 1
    max_len = 0  # STEP 1
    for i in range(n):  # STEP 2
        for j in range(i):  # STEP 3
            diff = nums[i] - nums[j]  # STEP 3
            prev_len = dp[j].get(diff, 1)  # STEP 3
            dp[i][diff] = prev_len + 1  # STEP 4,6,8,10,12,14
            max_len = max(max_len, dp[i][diff])  # STEP 4,6,8,10,12,14
    return max_len if max_len > 0 else n  # STEP 15

if __name__ == '__main__':
    print(longestArithSeqLength([3,6,9,12]))  # Output: 4

📊

Longest Arithmetic Subsequence - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the algorithm efficiently tracks multiple sequences simultaneously using hash maps, which is hard to grasp from code alone.

insert

empty map

Result: 0

check

empty map

Result: 0

lookup

Lookup: 3

empty map

Result: 0

insert

3→2

Result: 2

lookup

Lookup: 6

3→2

Result: 2

insert

3→2

Result: 2

lookup

Lookup: 3→ 2

6→2

Result: 2

insert

6→2

Result: 3

lookup

Lookup: 9

6→2

3→3

Result: 3

insert

empty map

Result: 3

lookup

Lookup: 6

9→2

Result: 3

insert

9→2

Result: 3

lookup

Lookup: 3→ 3

9→2

6→2

Result: 3

insert

9→2

6→2

Result: 4

none

empty map

Result: 4

Key Takeaways

✓ Tracking subsequences by difference at each index using hash maps allows efficient extension and avoids redundant computations.

This insight is hard to see from code alone because the data structure usage is implicit; visualization makes it explicit.

✓ The algorithm dynamically updates the global maximum length during iteration, reflecting the longest subsequence found so far.

Seeing max_len update step-by-step clarifies how the answer emerges progressively.

✓ When a difference is not found in a previous index's map, a new subsequence of length 2 starts, showing how subsequences initiate.

This concrete example from the trace helps understand the base case for subsequence lengths.

Practice

1. You are given an array of integers and a target sum k. You want to find the maximum number of pairs of elements whose sum equals k, with each element used at most once. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use a greedy approach to pick pairs from the start only.

B. Use nested loops to check all pairs and mark used elements.

C. Use a hash map to track frequencies of elements and find complements in one pass.

D. Use dynamic programming to count subsets that sum to k.

Solution

1. Step 1: Understand problem constraints

   The problem requires pairing elements to sum to k without reuse, maximizing count.

2. Step 2: Identify approach with linear time

   Using a hash map to track frequencies allows checking complements in O(1) per element, achieving O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map frequency counting is optimal and linear time [OK]

Hint: Hash map frequency counting solves pairing in O(n) [OK]

Common Mistakes:

• Assuming sorting alone solves pairing optimally
• Confusing subset sum DP with pair counting
• Using nested loops without optimization

2. You are given a sorted list of unique integers and need to summarize consecutive sequences as ranges (e.g., [0,1,2,4,5,7] -> ['0->2','4->5','7']). Which approach guarantees an optimal O(n) time solution with minimal extra space?

easy

A. Using two pointers to scan the list once, expanding the end pointer while consecutive numbers continue, then recording ranges.

B. Using nested loops to check every possible range start and end, appending ranges when sequences break.

C. Using dynamic programming to store the longest consecutive subsequence ending at each index and reconstruct ranges.

D. Using a greedy approach that picks the next number if it is consecutive, otherwise starts a new range, but restarts scanning from the beginning each time.

Solution

1. Step 1: Understand the problem constraints

   The input is sorted and unique, so consecutive sequences can be detected by checking if nums[end + 1] == nums[end] + 1.

2. Step 2: Identify the optimal approach

   Two pointers allow a single pass: one pointer marks the start of a range, the other expands until the sequence breaks, then record the range and move start pointer forward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers scan once -> O(n) time and O(n) space for output [OK]

Hint: Two pointers scan sorted list once for consecutive ranges [OK]

Common Mistakes:

• Thinking nested loops are necessary
• Confusing DP with this linear scan
• Restarting scan repeatedly wastes time

3. The following code attempts to find all anagrams of p in s using the sliding window approach. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. Missing matches adjustment after decreasing s_count[index_l]

B. Line updating s_count[index_l] after removing left char

C. Line appending index l to result when matches == 26

D. Line updating s_count[index_r] and matches after adding right char

Solution

1. Step 1: Identify where matches count is updated

   Matches are updated correctly when adding the right character but not when removing the left character.

2. Step 2: Locate missing matches adjustment

   After decreasing s_count[index_l], matches should be updated if counts now match or mismatch, but this is missing, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug causes false negatives on some inputs due to stale matches count [OK]

Hint: Check matches update after both add and remove steps [OK]

Common Mistakes:

• Forgetting to update matches after removing left char
• Updating matches twice incorrectly
• Off-by-one in window boundaries

4. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best

5. Suppose the problem is modified so that elements can be negative and the bounds left and right can also be negative. Which of the following changes is necessary to correctly count the number of subarrays with bounded maximum in this scenario?

hard

A. Adjust the logic to reset length when encountering elements outside the [left, right] range, not just greater than right.

B. Modify countAtMost to track minimum instead of maximum because negative numbers invert ordering.

C. Use a segment tree or balanced BST to query maximums efficiently due to negative values.

D. No change needed; the existing approach works for negative numbers as well.

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers do not invalidate the approach, but the reset condition must consider elements outside the bounds, including those less than left.

2. Step 2: Adjust reset logic

   Reset 'length' when elements are either > right or < left, because subarrays with max outside [left, right] are invalid.

3. Step 3: Why other options fail

   Tracking minimum is incorrect; segment trees add unnecessary complexity; existing approach assumes only upper bound resets.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reset on elements outside [left, right] range for correctness [OK]

Hint: Reset on elements outside both bounds, not just upper bound [OK]

Common Mistakes:

• Assuming no change needed
• Switching to minimum tracking
• Adding complex data structures unnecessarily