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.

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.

Description Hints 4 Solution Video 25:20

3872. Longest Arithmetic Sequence After Changing At Most One Element

Q: 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.

Q: 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.

Medium21.4% acceptance1 company

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 <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Amazon

Topics

Array Enumeration

Hints open one at a time

Hint 1

Precompute L[i] = length of longest arithmetic subarray ending at i using fixed differences.

Hint 2

Precompute R[i] = length of longest arithmetic subarray starting at i.

Hint 3

For each index i as the replaced element, check if neighbors allow a common difference d = (nums[i+1] - nums[i-1]) / 2 and combine L[i-1] and R[i+1].

Hint 4

Also consider extending only left or only right, and take the maximum over all positions.

25:20

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestArithmetic(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[9,7,5,10,1]

Input

[1,2,6,7]

Your code is saved on this device.Solution