LeetCode 3872 - Longest Arithmetic Sequence After Changing At Most One Element

Difficulty: 🟡 Medium
Topics: Array, Enumeration

Solution

Problem Understanding

The problem requires us to find the longest arithmetic subarray from a given array of integers nums if we are allowed to modify at most one element. An arithmetic subarray is a contiguous sequence in which the difference between consecutive elements is constant.

The input, nums, is an integer array of length between 4 and 105, and the values are all positive integers up to 105. The output is a single integer representing the maximum length of any arithmetic subarray achievable by changing at most one element in the array.

Key points include that the modification can occur anywhere in the array and we are allowed to choose any integer for that modification, which means it could help extend an existing arithmetic sequence or create a new one.

Important edge cases include arrays where the entire array is already arithmetic, arrays where only one element breaks the sequence, and arrays where no single change can extend a sequence beyond a few elements. Because the array size can be large (up to 10^5), brute force solutions that examine all subarrays are impractical.

Approaches

Brute-Force Approach

A naive approach would be to iterate over each element, try replacing it with all possible values that could form an arithmetic sequence with its neighbors, then check the longest arithmetic subarray for each possible replacement. This approach is correct because it explicitly examines all possibilities, but it is too slow. For an array of size n, this could result in O(n^2) or worse operations for checking all subarrays, which is infeasible for n up to 10^5.

Optimal Approach

The key observation is that an arithmetic sequence is defined entirely by its first element and the common difference. Since we can change at most one element, for every position in the array, we only need to consider sequences formed by its immediate neighbors. We can attempt to extend a sequence by either using the current difference, the previous difference, or making a single replacement to fit a difference.

We can maintain two pointers (or two running lengths): one tracking the current arithmetic sequence without modification, and another tracking the length considering one modification. At each step, we update these lengths based on the difference between consecutive elements and whether a single replacement can align the sequence. This approach allows a single linear scan of the array, yielding O(n) time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Try replacing each element and compute all subarray lengths
Optimal	O(n)	O(1)	Linear scan with tracking of sequences with and without one modification

Algorithm Walkthrough

Initialize variables to track the current arithmetic sequence length (current_len), the maximum length found (max_len), and the length considering a single modification (modified_len).
Compute the differences between consecutive elements as diff = nums[i] - nums[i-1].
For each element starting from the second, compare the current difference with the previous difference:

If the difference matches the previous one, increment both current_len and modified_len.
If the difference does not match, attempt a single replacement by assuming either the current element or the next element can be changed to match the sequence. Reset current_len and adjust modified_len accordingly.

Update max_len at each step by taking the maximum of max_len, current_len, and modified_len.
Return max_len after traversing the entire array.

Why it works: The algorithm guarantees correctness because it maintains two invariants: the longest arithmetic subarray without any changes and the longest with at most one modification. By continuously extending sequences using local differences and simulating a single change when differences break, the algorithm explores all feasible sequences efficiently.

Python Solution

from typing import List

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n
        
        max_len = 2
        current_len = 2
        modified_len = 2
        prev_diff = nums[1] - nums[0]

        for i in range(2, n):
            diff = nums[i] - nums[i-1]

            if diff == prev_diff:
                current_len += 1
                modified_len += 1
            else:
                # Try modifying nums[i] to continue previous difference
                if i >= 2 and nums[i] - nums[i-2] == 2 * prev_diff:
                    modified_len = current_len + 1
                else:
                    modified_len = 2
                
                current_len = 2
                prev_diff = nums[i] - nums[i-1]
            
            max_len = max(max_len, current_len, modified_len)

        return max_len

This implementation maintains two sequence lengths, updates them according to differences, and checks if a single modification can extend the sequence. It ensures linear traversal and constant space usage.

Go Solution

func longestArithmetic(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }

    maxLen := 2
    currentLen := 2
    modifiedLen := 2
    prevDiff := nums[1] - nums[0]

    for i := 2; i < n; i++ {
        diff := nums[i] - nums[i-1]

        if diff == prevDiff {
            currentLen++
            modifiedLen++
        } else {
            if nums[i]-nums[i-2] == 2*prevDiff {
                modifiedLen = currentLen + 1
            } else {
                modifiedLen = 2
            }
            currentLen = 2
            prevDiff = diff
        }
        if modifiedLen > maxLen {
            maxLen = modifiedLen
        }
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

In Go, the implementation is similar. Slices are used for arrays, integer arithmetic handles differences safely since constraints guarantee no overflow.

Worked Examples

Example 1: nums = [9, 7, 5, 10, 1]

i	nums[i]	diff	current_len	modified_len	max_len
2	5	-2	3	3	3
3	10	5	2	4	4
4	1	-9	2	5	5

Output: 5

Example 2: nums = [1, 2, 6, 7]

i	nums[i]	diff	current_len	modified_len	max_len
2	6	4	2	3	3
3	7	1	2	3	3

Output: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over the array to calculate differences and sequence lengths
Space	O(1)	Only a few integer variables are used for tracking lengths and differences

The algorithm avoids nested loops or storing extra arrays, so it achieves linear time with constant space.

Test Cases

# Provided examples
assert Solution().longestArithmetic([9,7,5,10,1]) == 5  # Replace 10 -> 3
assert Solution().longestArithmetic([1,2,6,7]) == 3      # Replace 1 -> -2

# Edge cases
assert Solution().longestArithmetic([1,1,1,1]) == 4      # Already arithmetic
assert Solution().longestArithmetic([1,3,5,9]) == 4      # Replace 9 -> 7
assert Solution().longestArithmetic([10,20,30,25,40]) == 4 # Replace 25 -> 40 or 40 -> 50
assert Solution().longestArithmetic([5,5,5,5,10]) == 5   # Replace 10 -> 5
assert Solution().longestArithmetic([1,100000,200000,300000]) == 4 # Large numbers

Test	Why
[9,7,5,10,1]	Checks a sequence that requires a middle element replacement
[1,2,6,7]	Checks replacement at the start to form longer sequence
[1,1,1,1]	Already arithmetic, no replacement needed
[1,3,5,9]	Replace last element to extend arithmetic sequence
[5,5,5,5,10]	Replace last element to match repeated numbers
[1,100000,200000,300000]	Handles large values within constraints

Edge Cases

Already arithmetic sequence: If the array is already arithmetic, any modification might not improve length. The implementation correctly identifies this by extending the current sequence and comparing lengths.
Single break in sequence: When one element breaks the arithmetic pattern, it is crucial to correctly simulate changing that element. The algorithm checks if modifying the current element can align with the previous difference and adjusts modified_len accordingly.