Longest arithmetic sequence after changing at most one element

Array Enumeration

20.7% acceptance

Mar 31, 2026

102

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_arithmetic(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n <= 2 {
      return n as i32;
    }
    // left[i] = length of longest arithmetic subarray ending at i (no changes)
    let mut left = vec![1i32; n];
    left[1] = 2;
    for i in 2..n {
      if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] {
        left[i] = left[i - 1] + 1;
      } else {
        left[i] = 2;
      }
    }
    // right[i] = length of longest arithmetic subarray starting at i (no changes)
    let mut right = vec![1i32; n];
    right[n - 2] = 2;
    for i in (0..n - 2).rev() {
      if nums[i + 2] - nums[i + 1] == nums[i + 1] - nums[i] {
        right[i] = right[i + 1] + 1;
      } else {
        right[i] = 2;
      }
    }
    let mut ans = *left.iter().max().unwrap();
    // Change nums[0]
    ans = ans.max(right[1] + 1);
    // Change nums[n-1]
    ans = ans.max(left[n - 2] + 1);
    // Change nums[i] for 1 <= i <= n-2
    for i in 1..n - 1 {
      ans = ans.max(left[i - 1] + 1);
      ans = ans.max(right[i + 1] + 1);
      // Bridge: check if we can connect left and right through changed nums[i]
      let diff = nums[i + 1] as i64 - nums[i - 1] as i64;
      if diff % 2 == 0 {
        let d = (diff / 2) as i32;
        let left_len = if i >= 2 && left[i - 1] > 1 && nums[i - 1] - nums[i - 2] == d {
          left[i - 1]
        } else {
          1
        };
        let right_len = if i + 2 < n && right[i + 1] > 1 && nums[i + 2] - nums[i + 1] == d {
          right[i + 1]
        } else {
          1
        };
        ans = ans.max(left_len + 1 + right_len);
      }
    }
    ans.min(n as i32)
  }
}