Longest non decreasing subarray after replacing at most one element

Array Dynamic Programming

21.6% acceptance

Feb 24, 2026

You are given an integer array nums. You are allowed to replace at most one element in the array with any other integer value of your choice. Return the length of the longest non-decreasing subarray that can be obtained after performing at most one replacement.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subarray(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 0 { return 0; }

    // left[i] = length of longest non-decreasing subarray ending at i (no replacement)
    let mut left = vec![1i32; n];
    for i in 1..n {
      if nums[i] >= nums[i - 1] {
        left[i] = left[i - 1] + 1;
      }
    }

    // right[i] = length of longest non-decreasing subarray starting at i (no replacement)
    let mut right = vec![1i32; n];
    for i in (0..n - 1).rev() {
      if nums[i + 1] >= nums[i] {
        right[i] = right[i + 1] + 1;
      }
    }

    // Baseline: no replacement needed
    let mut ans = *left.iter().max().unwrap();

    // Try replacing each position j
    for j in 0..n {
      let left_len = if j > 0 { left[j - 1] } else { 0 };
      let right_len = if j + 1 < n { right[j + 1] } else { 0 };
      let left_val = if j > 0 { nums[j - 1] } else { i32::MIN };
      let right_val = if j + 1 < n { nums[j + 1] } else { i32::MAX };

      let total = if left_val <= right_val {
        // Can pick a replacement that bridges both sides
        left_len + 1 + right_len
      } else {
        // Cannot bridge; extend whichever side is longer
        (left_len + 1).max(1 + right_len)
      };
      ans = ans.max(total);
    }

    ans
  }
}