Skip to main content
Talentd

Longest Arithmetic Sequence After Changing At Most One Element - Solution & Explanation

MediumArrayEnumeration15 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given an integer array nums.

A subarray is arithmetic if the difference between consecutive elements in the subarray is constant.

You can replace at most one element in nums with any integer. Then, you select an arithmetic subarray from nums.

Return an integer denoting the maximum length of the arithmetic subarray you can select.

 

Example 1:

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

Output: 5

Explanation:

  • Replace nums[3] = 10 with 3. The array becomes [9, 7, 5, 3, 1].
  • Select the subarray [9, 7, 5, 3, 1], which is arithmetic because consecutive elements have a common difference of -2.

Example 2:

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

Output: 3

Explanation:

  • Replace nums[0] = 1 with -2. The array becomes [-2, 2, 6, 7].
  • Select the subarray [-2, 2, 6, 7], which is arithmetic because consecutive elements have a common difference of 4.

 

Constraints:

  • 4 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach Overview

Problem Overview: You receive an integer array and can modify at most one element to any value. The goal is to maximize the length of a contiguous arithmetic sequence. An arithmetic sequence means the difference between consecutive elements remains constant.

Approach 1: Brute Force Difference Checking (O(n²) time, O(1) space)

Try every possible position as the element to change and test different arithmetic differences around it. For each candidate difference d, scan left and right while verifying whether elements already match the progression or can be fixed by using the single modification. This requires repeatedly rechecking segments of the array, leading to quadratic behavior. The approach is straightforward and useful for reasoning about how changing one element can bridge two arithmetic segments, but it becomes slow when the array grows.

Approach 2: Prefix and Suffix Decomposition + Enumeration (O(n) time, O(n) space)

Precompute the length of arithmetic segments ending at each index and starting at each index. Maintain two arrays: a prefix array where pref[i] stores the length of the arithmetic subarray ending at i, and a suffix array where suf[i] stores the length starting at i. Both can be filled in linear time by comparing consecutive differences.

Next, enumerate each index as the potential element to modify. The key observation: if you change nums[i], you may connect the arithmetic sequence on the left and the one on the right. Compute the expected difference using (nums[i+1] - nums[i-1]) / 2 and check whether the surrounding elements can form a valid arithmetic progression. If valid, combine pref[i-1] and suf[i+1]. Otherwise extend only one side. This enumeration step runs in O(n) and checks constant-time conditions at each index.

The decomposition avoids re-scanning the array. Prefix and suffix lengths capture all existing arithmetic segments, while enumeration simulates the best possible replacement. The method works well for array problems where local modifications affect adjacent segments and is a common pattern in enumeration style interview questions.

Recommended for interviews: The prefix–suffix enumeration approach is the expected solution. Brute force demonstrates understanding of arithmetic progression properties, but the linear solution shows stronger problem decomposition skills and efficient handling of array segments.

Solution

We first compute the differences between adjacent elements of the array, stored as array d, where d[i] = nums[i] - nums[i - 1].

Next, we define two arrays f and g, where f[i] represents the length of the longest arithmetic subarray ending at the i-th element, and g[i] represents the length of the longest arithmetic subarray starting at the i-th element. Initially, f[0] = 1, g[n - 1] = 1, and all other elements are initialized to 2.

We can compute the values of f and g in a single pass:

  • For f: if d[i] == d[i - 1], then f[i] = f[i - 1] + 1.
  • For g: if d[i + 1] == d[i + 2], then g[i] = g[i + 1] + 1.

Then we initialize the answer to 3, since we can always form an arithmetic subarray of length 3 by replacing one element. We then enumerate each element and try to replace it with a suitable value to form a longer arithmetic subarray:

  • For each element i, we can directly use f[i] or g[i] to update the answer.
  • If i > 0, we can replace nums[i] with nums[i - 1] + d[i - 1] to extend the arithmetic subarray ending at i - 1, updating the answer to f[i - 1] + 1.
  • If i + 1 < n, we can replace nums[i] with nums[i + 1] - d[i + 1] to extend the arithmetic subarray starting at i + 1, updating the answer to g[i + 1] + 1.
  • If 0 < i < n - 1, we can replace nums[i] with nums[i - 1] + \frac{nums[i + 1] - nums[i - 1]}{2} to try to bridge f[i - 1] and g[i + 1]. If this value is an integer and matches both d[i - 1] and d[i + 1], we update the answer to 3 + (f[i - 1] - 1) + (g[i + 1] - 1).

Finally, return the answer.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Difference CheckingO(n²)O(1)Useful for understanding the arithmetic progression constraint and validating small inputs
Prefix and Suffix Decomposition + EnumerationO(n)O(n)Optimal approach for large arrays; combines left and right arithmetic segments efficiently

Video Solution

Leetcode 3872 | Longest Arithmetic Sequence After Changing At Most One Element | Weekly contest 493 • CodeWithMeGuys • 1,367 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Longest Arithmetic Sequence After Changing At Most One Element easy or hard?
The problem is typically classified as Medium difficulty. Identifying arithmetic segments is straightforward, but the challenge is realizing that a single modification can merge two sequences. Using prefix and suffix decomposition turns the idea into an efficient O(n) implementation.
Longest Arithmetic Sequence After Changing At Most One Element Python/Java solution
Implement the prefix and suffix preprocessing arrays, then iterate through the array to test each index as the modified element. The same logic works across Python, Java, C++, Go, and TypeScript because the algorithm relies on simple array traversal and difference calculations.
How to solve Longest Arithmetic Sequence After Changing At Most One Element in O(n)?
Compute prefix and suffix arrays storing lengths of contiguous arithmetic segments. Then iterate through each index as the candidate element to change. Check whether adjusting that element can connect the arithmetic progression on the left and right using the expected difference derived from neighbors. Each step requires constant time, giving an overall O(n) algorithm.
What is the best approach for Longest Arithmetic Sequence After Changing At Most One Element?
The most efficient method uses prefix and suffix decomposition with enumeration. Precompute arithmetic segment lengths ending at each index and starting at each index, then enumerate the element you might modify. This allows you to combine left and right segments if the difference matches. The solution runs in O(n) time and O(n) space.
Is Longest Arithmetic Sequence After Changing At Most One Element asked at Google/Amazon/Meta?
Problems involving arithmetic sequences and array modification patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test your ability to detect patterns in differences and combine segments efficiently. This question reflects common array optimization techniques used in those interviews.
What data structure is used in Longest Arithmetic Sequence After Changing At Most One Element?
The solution mainly relies on arrays to store prefix and suffix lengths of arithmetic segments. Simple arithmetic difference checks and enumeration are used rather than complex data structures. This keeps the algorithm linear and cache‑friendly.
What is the time complexity of Longest Arithmetic Sequence After Changing At Most One Element?
The optimal solution runs in O(n) time. It performs two linear passes to compute prefix and suffix arithmetic segment lengths and one more pass to enumerate the position where the element may be modified. Space complexity is O(n) for the auxiliary arrays.

Ready to solve this problem?

Practice Longest Arithmetic Sequence After Changing At Most One Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays