Watch 4 video solutions for Longest Arithmetic Sequence After Changing At Most One Element, a medium level problem involving Array, Enumeration. This walkthrough by CodeWithMeGuys has 1,191 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |