Today we're looking at Longest Arithmetic Sequence After Changing At Most One Element. This is one of those problems that tests your ability to take a step back and precompute states rather than trying to simulate everything brute-force.
Let's break it down.
The Problem
We're given an integer array nums. A subarray is arithmetic if the difference between consecutive elements is constant. We're allowed to replace at most one element with any integer we want.
Return the maximum length of an arithmetic subarray we can form after making this single replacement.
Example:
Input: nums = [9, 7, 5, 10, 1]
Output: 5
Replace 10 with 3 → [9, 7, 5, 3, 1]. Common difference of -2. Length = 5.
Brute Force
The obvious approach: iterate through every index, try replacing it, and check how long of an arithmetic subarray you can form.
What do you change it to? You look at the surrounding elements to guess the common difference, then scan left and right.
Doing this for every index is O(n²). Given constraints of N ≤ 10^5, that's a TLE. We need O(N).
Intuition
Here's the key observation.
The element we replace acts as a bridge — connecting a valid arithmetic sequence on its left to one on its right.
So instead of simulating every replacement, precompute two arrays:
-
left[i]— length of the longest arithmetic subarray ending at indexi -
right[i]— length of the longest arithmetic subarray starting at indexi
Both can be built in a single O(N) pass.
Then for each index i (treated as the element we replace), look at neighbors l = i - 1 and r = i + 1. We have three options:
-
Extend left only — append our replaced element to the sequence ending at
l. Length =left[l] + 1 -
Extend right only — prepend our replaced element to the sequence starting at
r. Length =right[r] + 1 -
Bridge both sides — make
nums[i]the exact middle value betweennums[l]andnums[r]. This requires(nums[r] - nums[l]) % 2 == 0. The needed diff =(nums[r] - nums[l]) / 2. If the sequences on both sides share this diff, we can merge them through our replaced element.
Walkthrough
nums = [9, 7, 5, 10, 1]
Build left:
left[0] = 1
left[1] = 2 (7-9 == 9-? no, just start fresh → diff -2, length 2)
left[2] = 3 (5-7 == 7-9 ✓, diff -2, extend)
left[3] = 2 (10-5 ≠ 7-5, reset)
left[4] = 2 (1-10 ≠ 10-5, reset)
Build right:
right[4] = 1
right[3] = 2 (1-10 = -9, length 2)
right[2] = 2 (10-5 ≠ 1-10, reset)
right[1] = 3 (5-7 == 7-9 ✓, diff -2, extend)
right[0] = 4
Try bridging at i = 3 (value 10), l = 2, r = 4:
nums[l] = 5, nums[r] = 1
(1 - 5) = -4, -4 % 2 == 0 ✓
diff = -4 / 2 = -2
curr_len = 3 (nums[2], replaced nums[3], nums[4])
Check left: nums[2] - nums[1] = 5 - 7 = -2 == diff ✓
→ curr_len += left[2] - 1 = 3 - 1 = 2 → curr_len = 5
ans = max(ans, 5) = 5 ✓
Solution
Python
class Solution:
def longestArithmetic(self, nums: List[int]) -> int:
n = len(nums)
if n <= 2:
return n
# left[i] = length of longest arithmetic subarray ending at i
left = [2] * n
left[0] = 1
for i in range(2, n):
if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
left[i] = left[i-1] + 1
# right[i] = length of longest arithmetic subarray starting at i
right = [2] * n
right[-1] = 1
for i in range(n-3, -1, -1):
if nums[i+1] - nums[i] == nums[i+2] - nums[i+1]:
right[i] = right[i+1] + 1
ans = 2
# Edge case: modifying first or last element
ans = max(ans, right[1] + 1)
ans = max(ans, left[n-2] + 1)
# Try modifying each middle element
for i in range(1, n - 1):
l, r = i - 1, i + 1
# Option 1 & 2: extend from one side only
ans = max(ans, left[l] + 1, right[r] + 1)
# Option 3: bridge both sides
if (nums[r] - nums[l]) % 2 == 0:
diff = (nums[r] - nums[l]) // 2
curr_len = 3 # nums[l], replaced nums[i], nums[r]
if l > 0 and (nums[l] - nums[l-1]) == diff:
curr_len += left[l] - 1
if r < n - 1 and (nums[r+1] - nums[r]) == diff:
curr_len += right[r] - 1
ans = max(ans, curr_len)
return ans
C++
class Solution {
public:
int longestArithmetic(vector<int>& nums) {
int n = nums.size();
if (n <= 2) return n;
vector<int> left(n, 2), right(n, 2);
left[0] = 1; right[n-1] = 1;
for (int i = 2; i < n; ++i) {
if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2])
left[i] = left[i-1] + 1;
}
for (int i = n - 3; i >= 0; --i) {
if (nums[i+1] - nums[i] == nums[i+2] - nums[i+1])
right[i] = right[i+1] + 1;
}
int ans = 2;
ans = max(ans, right[1] + 1);
ans = max(ans, left[n-2] + 1);
for (int i = 1; i < n - 1; ++i) {
int l = i - 1, r = i + 1;
ans = max({ans, left[l] + 1, right[r] + 1});
if ((nums[r] - nums[l]) % 2 == 0) {
int diff = (nums[r] - nums[l]) / 2;
int curr_len = 3;
if (l > 0 && (nums[l] - nums[l-1]) == diff)
curr_len += left[l] - 1;
if (r < n - 1 && (nums[r+1] - nums[r]) == diff)
curr_len += right[r] - 1;
ans = max(ans, curr_len);
}
}
return ans;
}
};
Complexity
| Complexity | Notes | |
|---|---|---|
| Time | O(N) | Three sequential passes, no nested loops |
| Space | O(N) | Two extra arrays of size N |
Common Mistakes
Forgetting the edge cases — The first and last elements are a special case since they don't have neighbors on both sides. Handle right[1] + 1 and left[n-2] + 1 separately before the main loop.
Even check for bridging — When trying to bridge, (nums[r] - nums[l]) must be even for an integer middle value to exist. Skip it if it's odd.
Off-by-one when merging — When adding the left sequence length into curr_len, it's left[l] - 1 (not left[l]), because nums[l] is already counted in the base curr_len = 3.
Key Takeaway
When you're allowed to change one element, that element becomes a bridge. The trick is to precompute what exists on each side so you can evaluate every possible bridge position in O(1).
This pattern — precomputing prefix/suffix states and combining them at each index — shows up constantly in problems involving:
- At most one replacement / deletion
- Merging two valid subarrays through a single element
- Sliding window variants with one "free pass"
Whenever you see "change at most one element", think about what you can precompute from the left and from the right.
Top comments (0)