3872. Longest Arithmetic Sequence After Changing At Most One Element

MediumArrayEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A subarray is arithmetic if the difference between consecutive elements in the subarray is constant. For example, [3, 5, 7, 9] is arithmetic because the difference between every pair of consecutive elements is 2. A subarray of length 1 or 2 is always considered arithmetic.

You are allowed to perform the following operation: you can replace at most one element in nums with any integer of your choosing. After performing this optional replacement, you select an arithmetic subarray from nums.

Your task is to return an integer denoting the maximum length of the arithmetic subarray you can select.

Key points to understand:

You may choose to replace one element, or you may choose to replace none. The replacement is optional.
When you replace an element, you may set it to any integer value (positive, negative, or zero). This gives flexibility to "fix" a broken arithmetic pattern.
After the replacement, the arithmetic subarray you select must be a contiguous portion of nums.

Where a single replacement helps:

You can extend an existing arithmetic subarray by replacing a neighboring element so it fits the established common difference.
You can "bridge" two separate arithmetic subarrays by replacing the single element sitting between them, provided the gap can be filled by a value that keeps the difference constant on both sides.

For instance, if nums = [1, 2, 3, 100, 5], the element 100 breaks the arithmetic pattern. By replacing 100 with 4, the entire array becomes [1, 2, 3, 4, 5], which is arithmetic with a common difference of 1, giving a subarray of length 5.

Return the maximum achievable length of an arithmetic subarray after applying at most one replacement.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Build difference array, precompute prefix/suffix run lengths, then enumerate each index trying no-change, extend, and bridge cases.

Open in Flowchart

Intuition

Whether a subarray is arithmetic depends entirely on the differences between adjacent elements. So a natural first step is to convert the original array nums into a difference array d, where d[i] = nums[i] - nums[i - 1]. An arithmetic subarray of nums corresponds to a run of equal values in d. This shift in perspective makes the structure of the problem much clearer.

Now consider the power of replacing a single element. Replacing one element nums[i] affects exactly two differences: d[i] and d[i + 1]. This means a single replacement can only "fix" a problem located at one specific position. With that in mind, we can think about every possible place where we might apply (or not apply) the replacement, and figure out the best arithmetic subarray we can build around it.

To evaluate any position efficiently, it helps to precompute, for each index, how far an arithmetic run already extends to its left and to its right without any modification:

Let f[i] be the length of the longest arithmetic subarray ending at index i. This grows when d[i] == d[i - 1].
Let g[i] be the length of the longest arithmetic subarray starting at index i. This grows when d[i + 1] == d[i + 2].

With f and g ready, we can examine each element and reason about the best outcome. There are a few distinct cases to consider for what a single replacement can accomplish:

No replacement near here: the existing runs f[i] and g[i] are already valid answers on their own.
Append by replacement: replace nums[i] so it continues the arithmetic subarray ending at i - 1. This extends that run by one, giving f[i - 1] + 1. Symmetrically, replacing nums[i] to continue the run starting at i + 1 gives g[i + 1] + 1.
Bridge by replacement: the most interesting case is when nums[i] sits between two arithmetic runs. If we replace nums[i] with a value that makes the left run and the right run share the same common difference, we can merge them into one long arithmetic subarray. For this to work, the gap from nums[i - 1] to nums[i + 1] must be split evenly, so we need nums[i + 1] - nums[i - 1] to be even, with the required difference being (nums[i + 1] - nums[i - 1]) / 2. If this computed difference matches d[i - 1] on the left and d[i + 2] on the right, then both runs join together, and the merged length is 3 + (f[i - 1] - 1) + (g[i + 1] - 1).

Because we can always create an arithmetic subarray of length 3 by freely replacing the middle element, the answer is initialized to 3. We then scan through every index, apply the cases above, and keep the maximum length found. This combination of prefix and suffix decomposition (the f and g arrays) plus enumerating each replacement position lets us cover all possibilities in linear time.

Solution Approach

Solution 1: Prefix and Suffix Decomposition + Enumeration

We first compute the differences between adjacent elements of the array, stored as array d, where d[i] = nums[i] - nums[i - 1]. With this, an arithmetic subarray in nums becomes a run of equal values in d, which is much easier to reason about.

Next, we define two arrays f and g:

f[i] represents the length of the longest arithmetic subarray ending at index i.
g[i] represents the length of the longest arithmetic subarray starting at index i.

Initially, f[0] = 1 and g[n - 1] = 1, since a single element forms an arithmetic subarray of length 1. All other entries are initialized to 2, because any two adjacent elements always form a valid arithmetic subarray.

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

For f: scanning from left to right, if d[i] == d[i - 1], then f[i] = f[i - 1] + 1.
For g: scanning from right to left, 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 index i and try to replace nums[i] with a suitable value to form a longer arithmetic subarray, covering the following cases:

For each element i, we can directly use f[i] or g[i] to update the answer, representing the case where no replacement is applied around i.
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 with 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 with g[i + 1] + 1.
If 0 < i < n - 1, we try to bridge the run ending at i - 1 with the run starting at i + 1 by replacing nums[i]. The replacement value must split the gap evenly, so we compute diff = nums[i + 1] - nums[i - 1]. If diff is even, the required common difference is diff // 2. Starting from a base length of k = 3, we then check:
- If i > 1 and the required difference equals d[i - 1], the left run joins in, so k += f[i - 1] - 1.
- If i < n - 2 and the required difference equals d[i + 2], the right run joins in, so k += g[i + 1] - 1.
We then update the answer with k.

Finally, we return the answer.

The time complexity is O(n), where n is the length of the array nums, since we make a constant number of linear passes. The space complexity is O(n), due to the difference array d and the auxiliary arrays f and g.

Example Walkthrough

Let's trace through the solution using a small example: nums = [1, 2, 3, 100, 5]. The expected answer is 5, since replacing 100 with 4 produces [1, 2, 3, 4, 5].

Step 1: Build the difference array d

We compute d[i] = nums[i] - nums[i - 1] for i from 1 to n - 1. Index 0 has no predecessor, so we leave d[0] unused (treat it as a placeholder).

index `i`	0	1	2	3	4
`nums[i]`	1	2	3	100	5
`d[i]`	–	1	1	97	-95

A run of equal values in d is an arithmetic subarray in nums. We can see d[1] == d[2] == 1 (the run [1, 2, 3]), but d[3] and d[4] break the pattern.

Step 2: Compute f (longest arithmetic subarray ending at i)

Initialize f[0] = 1, and all other entries to 2. Scan left to right: if d[i] == d[i - 1], then f[i] = f[i - 1] + 1.

i = 1: no d[0] to compare → f[1] = 2.
i = 2: d[2] == d[1] (1 == 1) → f[2] = f[1] + 1 = 3.
i = 3: d[3] != d[2] (97 != 1) → f[3] = 2.
i = 4: d[4] != d[3] (-95 != 97) → f[4] = 2.

index `i`	0	1	2	3	4
`f[i]`	1	2	3	2	2

Step 3: Compute g (longest arithmetic subarray starting at i)

Initialize g[n - 1] = g[4] = 1, and all other entries to 2. Scan right to left: if d[i + 1] == d[i + 2], then g[i] = g[i + 1] + 1.

i = 3: d[4] vs d[5] → out of bounds → g[3] = 2.
i = 2: d[3] vs d[4] (97 != -95) → g[2] = 2.
i = 1: d[2] vs d[3] (1 != 97) → g[1] = 2.
i = 0: d[1] vs d[2] (1 == 1) → g[0] = g[1] + 1 = 3.

index `i`	0	1	2	3	4
`g[i]`	3	2	2	2	1

Step 4: Enumerate each index and apply the cases

Initialize ans = 3 (we can always make a length-3 subarray with one replacement).

i = 0: Use f[0] = 1, g[0] = 3. Append-right: g[1] + 1 = 3. Best so far → ans = 3.
i = 1: Use f[1] = 2, g[1] = 2. Append-left: f[0] + 1 = 2. Append-right: g[2] + 1 = 3. Bridge: diff = nums[2] - nums[0] = 3 - 1 = 2, even → required diff = 1. Left run extends if d[0] matched (skipped, i = 1), right run extends if d[3] == 1? 97 != 1, no. So k = 3. → ans = 3.
i = 2: Use f[2] = 3, g[2] = 2. Append-left: f[1] + 1 = 3. Append-right: g[3] + 1 = 3. Bridge: diff = nums[3] - nums[1] = 100 - 2 = 98, even → required diff = 49. Check d[1] == 49? No. Check d[4] == 49? No. k = 3. → ans = 3.
i = 3 (the broken element): Use f[3] = 2, g[3] = 2. Append-left: f[2] + 1 = 4. Append-right: g[4] + 1 = 2. Bridge: diff = nums[4] - nums[2] = 5 - 3 = 2, even → required diff = 1. Start k = 3.
- i = 3 > 1 and required diff 1 == d[2] (1)? Yes → k += f[2] - 1 = 3 - 1 = 2, so k = 5.
- i = 3 < n - 2 = 3? No, so the right side does not extend further.
- k = 5 → ans = 5.
i = 4: Use f[4] = 2, g[4] = 1. Append-left: f[3] + 1 = 3. → ans = 5.

Step 5: Return the answer

The maximum length found is 5, which corresponds to replacing nums[3] = 100 with 4, bridging the run [1, 2, 3] (ending at index 2) and the element 5 (at index 4) into the full arithmetic sequence [1, 2, 3, 4, 5] with common difference 1. The final answer is 5.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def longestArithmetic(self, nums: List[int]) -> int:
6        n = len(nums)
7
8        # diff[i] holds the difference between adjacent elements: nums[i] - nums[i - 1]
9        diff = [0] * n
10        for i in range(1, n):
11            diff[i] = nums[i] - nums[i - 1]
12
13        # prefix_len[i]: length of the longest arithmetic subarray ending at index i
14        # (using the natural differences, no modification involved)
15        prefix_len = [2] * n
16        # suffix_len[i]: length of the longest arithmetic subarray starting at index i
17        suffix_len = [2] * n
18        prefix_len[0] = suffix_len[n - 1] = 1
19
20        # Build prefix_len from left to right:
21        # if the current difference equals the previous one, we can extend the run.
22        for i in range(2, n):
23            if diff[i] == diff[i - 1]:
24                prefix_len[i] = prefix_len[i - 1] + 1
25
26        # Build suffix_len from right to left:
27        # if the next difference equals the one after it, we can extend the run.
28        for i in range(n - 3, -1, -1):
29            if diff[i + 1] == diff[i + 2]:
30                suffix_len[i] = suffix_len[i + 1] + 1
31
32        # The answer is at least 3 (we can always form a length-3 arithmetic
33        # sequence by modifying one element when n >= 3).
34        ans = 3
35        for i in range(n):
36            # Case 1: longest run that does not modify anything.
37            ans = max(ans, prefix_len[i], suffix_len[i])
38
39            # Case 2: modify the element at index i to a value beyond the boundary,
40            # effectively extending an existing run by one element (the modified one).
41            if i > 0:
42                # Extend the prefix run ending at i - 1 by appending a modified element.
43                ans = max(ans, prefix_len[i - 1] + 1)
44            if i + 1 < n:
45                # Extend the suffix run starting at i + 1 by prepending a modified element.
46                ans = max(ans, suffix_len[i + 1] + 1)
47
48            # Case 3: modify the middle element nums[i] so that nums[i-1], nums[i], nums[i+1]
49            # form an arithmetic progression. This requires nums[i] to become the average
50            # of its neighbors, so nums[i+1] - nums[i-1] must be even.
51            if 0 < i < n - 1:
52                gap = nums[i + 1] - nums[i - 1]
53                if gap % 2 == 0:
54                    step = gap // 2  # the required common difference around index i
55                    length = 3       # the central triple nums[i-1], (modified)nums[i], nums[i+1]
56
57                    # Merge with the arithmetic run on the left side if the step matches.
58                    if i > 1 and step == diff[i - 1]:
59                        length += prefix_len[i - 1] - 1
60                    # Merge with the arithmetic run on the right side if the step matches.
61                    if i < n - 2 and step == diff[i + 2]:
62                        length += suffix_len[i + 1] - 1
63
64                    ans = max(ans, length)
65
66        return ans
67

1class Solution {
2    /**
3     * Finds the length of the longest arithmetic (equal-difference) subarray,
4     * allowing at most one element to be modified to an arbitrary value.
5     */
6    public int longestArithmetic(int[] nums) {
7        int n = nums.length;
8
9        // diff[i] holds the difference between nums[i] and its previous element.
10        // diff[0] is unused (kept as 0).
11        int[] diff = new int[n];
12        for (int i = 1; i < n; i++) {
13            diff[i] = nums[i] - nums[i - 1];
14        }
15
16        // prefixRun[i]: length of the longest arithmetic run ENDING at index i.
17        // suffixRun[i]: length of the longest arithmetic run STARTING at index i.
18        int[] prefixRun = new int[n];
19        int[] suffixRun = new int[n];
20        Arrays.fill(prefixRun, 2);
21        Arrays.fill(suffixRun, 2);
22        prefixRun[0] = 1;        // a single element forms a run of length 1
23        suffixRun[n - 1] = 1;
24
25        // Extend prefix runs from left to right: if the current difference
26        // equals the previous difference, the run grows by one.
27        for (int i = 2; i < n; i++) {
28            if (diff[i] == diff[i - 1]) {
29                prefixRun[i] = prefixRun[i - 1] + 1;
30            }
31        }
32
33        // Extend suffix runs from right to left using the same idea.
34        for (int i = n - 3; i >= 0; i--) {
35            if (diff[i + 1] == diff[i + 2]) {
36                suffixRun[i] = suffixRun[i + 1] + 1;
37            }
38        }
39
40        // The answer is at least 3 (we can always make any 3 elements arithmetic
41        // by changing one of them, assuming n >= 3).
42        int ans = 3;
43
44        for (int i = 0; i < n; i++) {
45            // Case 1: pure runs that pass through / touch index i, no modification.
46            ans = Math.max(ans, Math.max(prefixRun[i], suffixRun[i]));
47
48            // Case 2: change the element just after a prefix run ending at i-1,
49            // (or before a suffix run) to extend it by one slot.
50            if (i > 0) {
51                ans = Math.max(ans, prefixRun[i - 1] + 1);
52            }
53            if (i + 1 < n) {
54                ans = Math.max(ans, suffixRun[i + 1] + 1);
55            }
56
57            // Case 3: change nums[i] itself so the left side and right side
58            // can be merged into one arithmetic sequence. For that, the gap
59            // (nums[i+1] - nums[i-1]) must be split evenly, i.e. be even.
60            if (i > 0 && i < n - 1) {
61                int gap = nums[i + 1] - nums[i - 1];
62                if (gap % 2 == 0) {
63                    int half = gap / 2;          // the required common difference
64                    int merged = 3;              // i-1, i (modified), i+1
65
66                    // If the left run's difference matches half, attach it.
67                    if (i > 1 && half == diff[i - 1]) {
68                        merged += prefixRun[i - 1] - 1;
69                    }
70                    // If the right run's difference matches half, attach it.
71                    if (i < n - 2 && half == diff[i + 2]) {
72                        merged += suffixRun[i + 1] - 1;
73                    }
74                    ans = Math.max(ans, merged);
75                }
76            }
77        }
78
79        return ans;
80    }
81}
82

1class Solution {
2public:
3    int longestArithmetic(vector<int>& nums) {
4        int n = nums.size();
5
6        // diff[i] holds the difference between nums[i] and its predecessor nums[i-1].
7        vector<int> diff(n);
8        for (int i = 1; i < n; ++i) {
9            diff[i] = nums[i] - nums[i - 1];
10        }
11
12        // prefixLen[i]: length of the longest arithmetic run (constant difference)
13        //               that ENDS at index i.
14        // suffixLen[i]: length of the longest arithmetic run (constant difference)
15        //               that STARTS at index i.
16        // A run always has at least 2 elements once i >= 1, so the base value is 2.
17        vector<int> prefixLen(n, 2), suffixLen(n, 2);
18        prefixLen[0] = 1;       // a single element on the left edge
19        suffixLen[n - 1] = 1;   // a single element on the right edge
20
21        // Build prefixLen: extend the run if the current difference matches the previous one.
22        for (int i = 2; i < n; ++i) {
23            if (diff[i] == diff[i - 1]) {
24                prefixLen[i] = prefixLen[i - 1] + 1;
25            }
26        }
27
28        // Build suffixLen: extend the run if the next two differences match.
29        for (int i = n - 3; i >= 0; --i) {
30            if (diff[i + 1] == diff[i + 2]) {
31                suffixLen[i] = suffixLen[i + 1] + 1;
32            }
33        }
34
35        // The answer is at least 3 (assuming we can always form a length-3 sequence).
36        int ans = 3;
37        for (int i = 0; i < n; ++i) {
38            // Case 1: take an existing run as-is, ending or starting at i.
39            ans = max(ans, max(prefixLen[i], suffixLen[i]));
40
41            // Case 2: extend the run ending before i by changing nums[i] (one free edit).
42            if (i > 0) {
43                ans = max(ans, prefixLen[i - 1] + 1);
44            }
45
46            // Case 3: extend the run starting after i by changing nums[i] (one free edit).
47            if (i + 1 < n) {
48                ans = max(ans, suffixLen[i + 1] + 1);
49            }
50
51            // Case 4: "bridge" two runs by modifying the middle element nums[i],
52            //         making nums[i-1], nums[i], nums[i+1] an arithmetic progression.
53            if (i > 0 && i < n - 1) {
54                int bridgeDiff = nums[i + 1] - nums[i - 1];
55                // The midpoint must be an integer for a valid arithmetic step.
56                if (bridgeDiff % 2 == 0) {
57                    bridgeDiff /= 2;          // the required common difference
58                    int length = 3;           // nums[i-1], modified nums[i], nums[i+1]
59
60                    // Merge with the left run if its difference matches.
61                    if (i > 1 && bridgeDiff == diff[i - 1]) {
62                        length += prefixLen[i - 1] - 1;
63                    }
64                    // Merge with the right run if its difference matches.
65                    if (i < n - 2 && bridgeDiff == diff[i + 2]) {
66                        length += suffixLen[i + 1] - 1;
67                    }
68                    ans = max(ans, length);
69                }
70            }
71        }
72        return ans;
73    }
74};
75

1/**
2 * Finds the length of the longest arithmetic progression that can be obtained
3 * from a contiguous run in `nums`, given that we are allowed to modify
4 * at most one element's value.
5 *
6 * Approach:
7 *  - Build the difference array between adjacent elements.
8 *  - `prefixLen[i]`: length of the longest arithmetic run ending at index i
9 *    (based on equal consecutive differences).
10 *  - `suffixLen[i]`: length of the longest arithmetic run starting at index i.
11 *  - Then try "bridging" two runs by altering a single middle element so that
12 *    the left run and right run share the same common difference.
13 */
14function longestArithmetic(nums: number[]): number {
15    const length = nums.length;
16
17    // diff[i] holds the difference between nums[i] and the previous element.
18    const diff = new Array<number>(length).fill(0);
19    for (let i = 1; i < length; i++) {
20        diff[i] = nums[i] - nums[i - 1];
21    }
22
23    // prefixLen[i]: length of the longest arithmetic run ending at index i.
24    // suffixLen[i]: length of the longest arithmetic run starting at index i.
25    // A single pair of elements is always an arithmetic run of length 2.
26    const prefixLen = new Array<number>(length).fill(2);
27    const suffixLen = new Array<number>(length).fill(2);
28    prefixLen[0] = 1;            // a single element forms a run of length 1
29    suffixLen[length - 1] = 1;   // a single element forms a run of length 1
30
31    // Extend the prefix run whenever consecutive differences stay equal.
32    for (let i = 2; i < length; i++) {
33        if (diff[i] === diff[i - 1]) {
34            prefixLen[i] = prefixLen[i - 1] + 1;
35        }
36    }
37
38    // Extend the suffix run whenever consecutive differences stay equal.
39    for (let i = length - 3; i >= 0; i--) {
40        if (diff[i + 1] === diff[i + 2]) {
41            suffixLen[i] = suffixLen[i + 1] + 1;
42        }
43    }
44
45    // The minimum answer when modification is allowed is 3.
46    let answer = 3;
47
48    for (let i = 0; i < length; i++) {
49        // Best runs that simply pass through index i without any change.
50        answer = Math.max(answer, prefixLen[i], suffixLen[i]);
51
52        // Modify the current element to extend the run ending at i - 1 by one.
53        if (i > 0) {
54            answer = Math.max(answer, prefixLen[i - 1] + 1);
55        }
56
57        // Modify the current element to extend the run starting at i + 1 by one.
58        if (i + 1 < length) {
59            answer = Math.max(answer, suffixLen[i + 1] + 1);
60        }
61
62        // Try to bridge the left run and the right run by changing nums[i] so
63        // that the gap (nums[i+1] - nums[i-1]) splits evenly into two equal steps.
64        if (i > 0 && i < length - 1) {
65            let bridgeDiff = nums[i + 1] - nums[i - 1];
66
67            // The single common difference must be an integer for both halves.
68            if (bridgeDiff % 2 === 0) {
69                bridgeDiff = Math.floor(bridgeDiff / 2);
70
71                // The three involved elements (i-1, i, i+1) form a base run of 3.
72                let bridgedLen = 3;
73
74                // Attach the left arithmetic run if its difference matches.
75                if (i > 1 && bridgeDiff === diff[i - 1]) {
76                    bridgedLen += prefixLen[i - 1] - 1;
77                }
78
79                // Attach the right arithmetic run if its difference matches.
80                if (i < length - 2 && bridgeDiff === diff[i + 2]) {
81                    bridgedLen += suffixLen[i + 1] - 1;
82                }
83
84                answer = Math.max(answer, bridgedLen);
85            }
86        }
87    }
88
89    return answer;
90}
91

Time and Space Complexity

Time Complexity

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

The analysis is as follows:

Building the difference array d requires a single loop from 1 to n - 1, which takes O(n) time.
Computing the forward array f involves one loop from 2 to n - 1, costing O(n) time.
Computing the backward array g involves one loop from n - 3 down to 0, also costing O(n) time.
The final loop over i from 0 to n - 1 performs only constant-time operations in each iteration (comparisons, arithmetic, and max calls), so it contributes O(n) time.

Since these loops run sequentially and each is O(n), the overall time complexity is O(n).

Space Complexity

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

The analysis is as follows:

The difference array d uses O(n) extra space.
The forward array f uses O(n) extra space.
The backward array g uses O(n) extra space.
The remaining variables (ans, i, diff, k, etc.) only require O(1) extra space.

Therefore, the total additional space used is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to clamp the answer when `n < 3`

The code initializes ans = 3 unconditionally. This silently assumes that the array always has at least three elements, so a length-3 arithmetic subarray can always be formed by replacing one element. However, when n < 3, this assumption breaks:

If n == 1, the only valid answer is 1.
If n == 2, the only valid answer is 2.

By starting ans at 3, the code would incorrectly return 3 for inputs like nums = [5] or nums = [5, 10], overshooting the true maximum subarray length (which cannot exceed n).

Why it happens: The "we can always form a length-3 subarray" logic is only valid when there are at least three positions to work with. The optimistic base value ignores the physical size limit of the array.

Solution: Cap the initial answer at n, or handle small arrays explicitly before the main loop.

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

        # Guard small inputs: the answer can never exceed n.
        if n <= 2:
            return n

        # ... (diff, prefix_len, suffix_len construction unchanged) ...

        # Now it is safe to start at 3, because n >= 3 is guaranteed here.
        ans = 3
        # ... (main enumeration unchanged) ...
        return ans

This single early return removes the edge-case risk while keeping the rest of the logic intact.

Pitfall 2: Mishandling the parity check when bridging two runs

The bridging case (Case 3) computes gap = nums[i + 1] - nums[i - 1] and proceeds only when gap % 2 == 0. A common mistake is to either:

Skip the parity check entirely, computing step = gap // 2 and assuming the midpoint is always a valid integer. In Python, gap // 2 performs floor division, so for an odd gap it produces a value that does not actually make the triple arithmetic. The replaced element nums[i] must be exactly nums[i-1] + step, and nums[i+1] must equal nums[i] + step; this is only possible when gap is even.
Use the wrong sign convention when comparing step against neighboring differences. Note the asymmetry in the merge checks: the left side compares step == diff[i - 1] but uses prefix_len[i - 1], while the right side compares step == diff[i + 2] (not diff[i + 1]) and uses suffix_len[i + 1]. The reason is that diff[i + 1] involves the element being replaced (nums[i]), so it is meaningless after replacement; the first valid difference of the right run is diff[i + 2].

Why it happens: It is tempting to treat both neighbors symmetrically, but the difference array is "shifted" relative to the element being modified. Reaching for diff[i + 1] instead of diff[i + 2] is the most frequent bug here.

Solution: Always verify the parity guard, and carefully align the difference indices with the runs they represent.

if 0 < i < n - 1:
    gap = nums[i + 1] - nums[i - 1]
    if gap % 2 == 0:                 # mandatory: midpoint must be an integer
        step = gap // 2
        length = 3
        # Left run's last difference is diff[i - 1].
        if i > 1 and step == diff[i - 1]:
            length += prefix_len[i - 1] - 1
        # Right run's FIRST valid difference is diff[i + 2], NOT diff[i + 1].
        if i < n - 2 and step == diff[i + 2]:
            length += suffix_len[i + 1] - 1
        ans = max(ans, length)

Pitfall 3: Double-counting the modified element when merging runs

When bridging, the base length = 3 already accounts for three positions: nums[i-1], the modified nums[i], and nums[i+1]. When merging in the left or right run, the code adds prefix_len[i - 1] - 1 and suffix_len[i + 1] - 1 (subtracting 1 each time).

A common mistake is forgetting the - 1, writing length += prefix_len[i - 1] instead. This double-counts the boundary element (nums[i-1] or nums[i+1]), since that element is already included in the base triple of 3.

Why it happens: The interplay between "length of a run" and "number of new elements contributed" is subtle. A run of length L ending at i-1 contributes only L - 1 additional elements once nums[i-1] is already counted.

Solution: Always subtract the shared boundary element. The - 1 correction is essential for correctness.

# Correct: the boundary element nums[i-1] / nums[i+1] is already in `length = 3`.
length += prefix_len[i - 1] - 1
length += suffix_len[i + 1] - 1

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know