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:
nums[3] = 10 with 3. The array becomes [9, 7, 5, 3, 1].[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:
nums[0] = 1 with -2. The array becomes [-2, 2, 6, 7].[-2, 2, 6, 7], which is arithmetic because consecutive elements have a common difference of 4.
Constraints:
4 <= nums.length <= 1051 <= nums[i] <= 105Problem 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.
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:
f: if d[i] == d[i - 1], then f[i] = f[i - 1] + 1.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:
i, we can directly use f[i] or g[i] to update the answer.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.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.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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Difference Checking | O(n²) | O(1) | Useful for understanding the arithmetic progression constraint and validating small inputs |
| Prefix and Suffix Decomposition + Enumeration | O(n) | O(n) | Optimal approach for large arrays; combines left and right arithmetic segments efficiently |
Leetcode 3872 | Longest Arithmetic Sequence After Changing At Most One Element | Weekly contest 493 • CodeWithMeGuys • 1,191 views views
Watch 3 more video solutions →Practice Longest Arithmetic Sequence After Changing At Most One Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor