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

Source: Dev.to

Longest Arithmetic Sequence After Changing At Most One Element

Problem link: (add the actual link here)

We are given an integer array nums.
A subarray is arithmetic if the difference between consecutive elements is constant.
We may replace at most one element with any integer we want.

Goal: Return the maximum length of an arithmetic subarray we can obtain after the single replacement.

Example

Input:  nums = [9, 7, 5, 10, 1]
Output: 5

Replace 10 with 3 → [9, 7, 5, 3, 1].
Common difference = -2. Length = 5.

Why a naïve O(N²) solution won’t work

The obvious approach is:

1. Iterate through every index i.
2. Try replacing nums[i] with a value that fits the surrounding elements.
3. Scan left and right to find the longest arithmetic subarray.

Doing this for every index is O(N²), which exceeds the limit N ≤ 10⁵.
We need an O(N) solution.

Key observation

The element we replace acts as a bridge that can connect:

• a valid arithmetic sequence on its left, and
• a valid arithmetic sequence on its right.

Instead of simulating every replacement, we pre‑compute two helper arrays:

Both arrays are built in a single linear pass.

How to use left and right

For each index i (the element we may replace) let

• l = i‑1 (left neighbour)
• r = i+1 (right neighbour)

We have three possibilities:

1. Extend only the left side – append the replaced element to the sequence ending at l.
   len = left[l] + 1
2. Extend only the right side – prepend the replaced element to the sequence starting at r.
   len = right[r] + 1
3. Bridge both sides – make nums[i] the exact middle value between nums[l] and nums[r].
   • This is possible only when (nums[r] - nums[l]) is even.
   • Required common difference: diff = (nums[r] - nums[l]) / 2.
   • If the left and right sequences both have this diff, we can merge them through i.

The bridge length starts at 3 (nums[l], replaced nums[i], nums[r]) and is expanded by the lengths of the left/right sequences that share the same diff.

Building left and right

# left[i] = length of longest arithmetic subarray ending at i
left = [1] * n
for i in range(2, n):
    if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
        left[i] = left[i-1] + 1
    else:
        left[i] = 2          # start a new pair

# right[i] = length of longest arithmetic subarray starting at i
right = [1] * n
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
    else:
        right[i] = 2          # start a new pair

Both loops run in O(N) time.

Full implementations

Python

from typing import List

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        # pre‑compute left and right arrays
        left = [1] * n
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                left[i] = left[i-1] + 1
            else:
                left[i] = 2

        right = [1] * n
        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
            else:
                right[i] = 2

        ans = 2  # at least two elements form an arithmetic subarray

        # try changing each element
        for i in range(1, n-1):
            # case 1: extend left side only
            ans = max(ans, left[i-1] + 1)
            # case 2: extend right side only
            ans = max(ans, right[i+1] + 1)

            # case 3: bridge both sides
            if (nums[i+1] - nums[i-1]) % 2 == 0:
                diff = (nums[i+1] - nums[i-1]) // 2
                cur_len = 3
                # extend left while maintaining diff
                l = i-2
                while l >= 0 and nums[l+1] - nums[l] == diff:
                    cur_len += 1
                    l -= 1
                # extend right while maintaining diff
                r = i+2
                while r < n and nums[r] - nums[r-1] == diff:
                    cur_len += 1
                    r += 1
                ans = max(ans, cur_len)

        # edge cases: modify first or last element
        ans = max(ans, right[1] + 1)   # change nums[0]
        ans = max(ans, left[n-2] + 1)  # change nums[n-1]

        return ans

C++ (as originally posted)

// Note: The original snippet is incomplete; it is reproduced verbatim.
if (n  left(n, 2), right(n, 2);
left[0] = 1;               // only the first element
right[n-1] = 1;            // only the last element

// ----- left -----
for (int i = 2; i = 0; --i) {
    if (nums[i+1] - nums[i] == nums[i+2] - nums[i+1])
        right[i] = right[i+1] + 1;
}

int ans = 2;

// Edge cases: modify first or last element
ans = max(ans, right[1] + 1);          // change nums[0]
ans = max(ans, left[n-2] + 1);         // change nums[n-1]

// ----- try modifying each middle element -----
for (int i = 1; i  0 && (nums[l] - nums[l-1]) == diff)
            cur_len += left[l] - 1;      // left[l] already counts nums[l]

        if (r & nums) {

Insights

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”

Takeaway

Whenever you see “change at most one element”, think about what you can pre‑compute from the left and from the right.