Skip to content

3872. Longest Arithmetic Sequence After Changing At Most One Element

Description

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

Solutions

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]\).

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        d = [0] * n
        for i in range(1, n):
            d[i] = nums[i] - nums[i - 1]

        f = [2] * n
        g = [2] * n
        f[0] = g[n - 1] = 1
        for i in range(2, n):
            if d[i] == d[i - 1]:
                f[i] = f[i - 1] + 1
        for i in range(n - 3, -1, -1):
            if d[i + 1] == d[i + 2]:
                g[i] = g[i + 1] + 1

        ans = 3
        for i in range(n):
            ans = max(ans, f[i], g[i])
            if i > 0:
                ans = max(ans, f[i - 1] + 1)
            if i + 1 < n:
                ans = max(ans, g[i + 1] + 1)
            if 0 < i < n - 1:
                diff = nums[i + 1] - nums[i -1]
                if diff % 2 == 0:
                    diff //= 2
                    k = 3
                    if i > 1 and diff == d[i - 1]:
                        k += f[i - 1] - 1
                    if i < n - 2 and diff == d[i + 2]:
                        k += g[i + 1] - 1
                    ans = max(ans, k)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int longestArithmetic(int[] nums) {
        int n = nums.length;
        int[] d = new int[n];
        for (int i = 1; i < n; i++) {
            d[i] = nums[i] - nums[i - 1];
        }

        int[] f = new int[n];
        int[] g = new int[n];
        Arrays.fill(f, 2);
        Arrays.fill(g, 2);
        f[0] = 1;
        g[n - 1] = 1;

        for (int i = 2; i < n; i++) {
            if (d[i] == d[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }

        for (int i = n - 3; i >= 0; i--) {
            if (d[i + 1] == d[i + 2]) {
                g[i] = g[i + 1] + 1;
            }
        }

        int ans = 3;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, Math.max(f[i], g[i]));
            if (i > 0) {
                ans = Math.max(ans, f[i - 1] + 1);
            }
            if (i + 1 < n) {
                ans = Math.max(ans, g[i + 1] + 1);
            }
            if (i > 0 && i < n - 1) {
                int diff = nums[i + 1] - nums[i - 1];
                if (diff % 2 == 0) {
                    diff /= 2;
                    int k = 3;
                    if (i > 1 && diff == d[i - 1]) {
                        k += f[i - 1] - 1;
                    }
                    if (i < n - 2 && diff == d[i + 2]) {
                        k += g[i + 1] - 1;
                    }
                    ans = Math.max(ans, k);
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int longestArithmetic(vector<int>& nums) {
        int n = nums.size();
        vector<int> d(n);
        for (int i = 1; i < n; i++) {
            d[i] = nums[i] - nums[i - 1];
        }

        vector<int> f(n, 2), g(n, 2);
        f[0] = 1;
        g[n - 1] = 1;

        for (int i = 2; i < n; i++) {
            if (d[i] == d[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }

        for (int i = n - 3; i >= 0; i--) {
            if (d[i + 1] == d[i + 2]) {
                g[i] = g[i + 1] + 1;
            }
        }

        int ans = 3;
        for (int i = 0; i < n; i++) {
            ans = max(ans, max(f[i], g[i]));
            if (i > 0) {
                ans = max(ans, f[i - 1] + 1);
            }
            if (i + 1 < n) {
                ans = max(ans, g[i + 1] + 1);
            }
            if (i > 0 && i < n - 1) {
                int diff = nums[i + 1] - nums[i - 1];
                if (diff % 2 == 0) {
                    diff /= 2;
                    int k = 3;
                    if (i > 1 && diff == d[i - 1]) {
                        k += f[i - 1] - 1;
                    }
                    if (i < n - 2 && diff == d[i + 2]) {
                        k += g[i + 1] - 1;
                    }
                    ans = max(ans, k);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func longestArithmetic(nums []int) int {
    n := len(nums)
    d := make([]int, n)
    for i := 1; i < n; i++ {
        d[i] = nums[i] - nums[i-1]
    }

    f := make([]int, n)
    g := make([]int, n)
    for i := range f {
        f[i], g[i] = 2, 2
    }
    f[0], g[n-1] = 1, 1

    for i := 2; i < n; i++ {
        if d[i] == d[i-1] {
            f[i] = f[i-1] + 1
        }
    }

    for i := n - 3; i >= 0; i-- {
        if d[i+1] == d[i+2] {
            g[i] = g[i+1] + 1
        }
    }

    ans := 3
    for i := 0; i < n; i++ {
        ans = max(ans, f[i], g[i])

        if i > 0 {
            ans = max(ans, f[i-1]+1)
        }
        if i+1 < n {
            ans = max(ans, g[i+1]+1)
        }

        if i > 0 && i < n-1 {
            diff := nums[i+1] - nums[i-1]
            if diff%2 == 0 {
                diff /= 2
                k := 3
                if i > 1 && diff == d[i-1] {
                    k += f[i-1] - 1
                }
                if i < n-2 && diff == d[i+2] {
                    k += g[i+1] - 1
                }
                ans = max(ans, k)
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function longestArithmetic(nums: number[]): number {
    const n = nums.length;
    const d = new Array(n).fill(0);

    for (let i = 1; i < n; i++) {
        d[i] = nums[i] - nums[i - 1];
    }

    const f = new Array(n).fill(2);
    const g = new Array(n).fill(2);
    f[0] = 1;
    g[n - 1] = 1;

    for (let i = 2; i < n; i++) {
        if (d[i] === d[i - 1]) {
            f[i] = f[i - 1] + 1;
        }
    }

    for (let i = n - 3; i >= 0; i--) {
        if (d[i + 1] === d[i + 2]) {
            g[i] = g[i + 1] + 1;
        }
    }

    let ans = 3;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, f[i], g[i]);
        if (i > 0) {
            ans = Math.max(ans, f[i - 1] + 1);
        }
        if (i + 1 < n) {
            ans = Math.max(ans, g[i + 1] + 1);
        }
        if (i > 0 && i < n - 1) {
            let diff = nums[i + 1] - nums[i - 1];
            if (diff % 2 === 0) {
                diff = Math.floor(diff / 2);
                let k = 3;
                if (i > 1 && diff === d[i - 1]) {
                    k += f[i - 1] - 1;
                }
                if (i < n - 2 && diff === d[i + 2]) {
                    k += g[i + 1] - 1;
                }
                ans = Math.max(ans, k);
            }
        }
    }

    return ans;
}

Comments