Longest Increasing subarray with one change allowed

Problem

Given an array, find the length of the longest increasing subarray (contiguous elements) such that it is possible to change at most one number (change one number to any integer you want) from the sequence to make the sequence strictly increasing.

Examples

Example 1

Input:
nums = [7, 2, 3, 1, 5, 10]
Output:
5
Explanation:
Here, we can choose subarray [2, 3, 1, 5, 10] and by changing its 3rd element (that is 1) to 4, it will become an increasing sequence.

Example 2

Input:
nums = [10, 10]
Output:
2
Explanation:
Here, we can choose subarray [10, 10] and by changing its 2nd element (that is 10) to 11, it will become an increasing sequence.

Solution

Method 1 – Dynamic Programming with Two Passes

Intuition

We want to find the longest increasing subarray, allowing at most one change. By keeping track of the longest increasing subarrays ending and starting at each index, we can efficiently combine segments by skipping one element.

Approach

1. Create two arrays:
   • l[i]: Length of the longest increasing subarray ending at index i.
   • r[i]: Length of the longest increasing subarray starting at index i.
2. Fill l from left to right and r from right to left.
3. For each index, check if removing it (changing it) can connect the left and right segments into a longer increasing subarray.
4. Track the maximum length found.
5. Handle edge cases where the array is already strictly increasing or has only one element.

Code

C++

class Solution {
public:
    int longestIncreasingSubarray(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<int> l(n, 1), r(n, 1);
        for (int i = 1; i < n; ++i)
            l[i] = (nums[i] > nums[i-1]) ? l[i-1] + 1 : 1;
        for (int i = n-2; i >= 0; --i)
            r[i] = (nums[i] < nums[i+1]) ? r[i+1] + 1 : 1;
        ans = *max_element(l.begin(), l.end());
        for (int i = 1; i < n-1; ++i) {
            if (nums[i-1] < nums[i+1])
                ans = max(ans, l[i-1] + r[i+1]);
        }
        return min(ans+1, n);
    }
};

Go

func longestIncreasingSubarray(nums []int) int {
    n := len(nums)
    l := make([]int, n)
    r := make([]int, n)
    ans := 1
    for i := range l {
        l[i], r[i] = 1, 1
    }
    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            l[i] = l[i-1] + 1
        }
    }
    for i := n-2; i >= 0; i-- {
        if nums[i] < nums[i+1] {
            r[i] = r[i+1] + 1
        }
    }
    for _, v := range l {
        if v > ans {
            ans = v
        }
    }
    for i := 1; i < n-1; i++ {
        if nums[i-1] < nums[i+1] {
            if l[i-1]+r[i+1] > ans {
                ans = l[i-1]+r[i+1]
            }
        }
    }
    if ans+1 > n {
        return n
    }
    return ans+1
}

Java

class Solution {
    public int longestIncreasingSubarray(int[] nums) {
        int n = nums.length, ans = 1;
        int[] l = new int[n], r = new int[n];
        Arrays.fill(l, 1);
        Arrays.fill(r, 1);
        for (int i = 1; i < n; i++)
            l[i] = nums[i] > nums[i-1] ? l[i-1] + 1 : 1;
        for (int i = n-2; i >= 0; i--)
            r[i] = nums[i] < nums[i+1] ? r[i+1] + 1 : 1;
        for (int v : l) ans = Math.max(ans, v);
        for (int i = 1; i < n-1; i++)
            if (nums[i-1] < nums[i+1])
                ans = Math.max(ans, l[i-1] + r[i+1]);
        return Math.min(ans+1, n);
    }
}

Kotlin

class Solution {
    fun longestIncreasingSubarray(nums: IntArray): Int {
        val n = nums.size
        val l = IntArray(n) { 1 }
        val r = IntArray(n) { 1 }
        var ans = 1
        for (i in 1 until n)
            l[i] = if (nums[i] > nums[i-1]) l[i-1] + 1 else 1
        for (i in n-2 downTo 0)
            r[i] = if (nums[i] < nums[i+1]) r[i+1] + 1 else 1
        ans = l.maxOrNull() ?: 1
        for (i in 1 until n-1)
            if (nums[i-1] < nums[i+1])
                ans = maxOf(ans, l[i-1] + r[i+1])
        return minOf(ans+1, n)
    }
}

Python

def longest_increasing_subarray(nums: list[int]) -> int:
    n = len(nums)
    l = [1] * n
    r = [1] * n
    ans = 1
    for i in range(1, n):
        l[i] = l[i-1] + 1 if nums[i] > nums[i-1] else 1
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] + 1 if nums[i] < nums[i+1] else 1
    ans = max(l)
    for i in range(1, n-1):
        if nums[i-1] < nums[i+1]:
            ans = max(ans, l[i-1] + r[i+1])
    return min(ans+1, n)

Rust

impl Solution {
    pub fn longest_increasing_subarray(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut l = vec![1; n];
        let mut r = vec![1; n];
        let mut ans = 1;
        for i in 1..n {
            if nums[i] > nums[i-1] {
                l[i] = l[i-1] + 1;
            }
        }
        for i in (0..n-1).rev() {
            if nums[i] < nums[i+1] {
                r[i] = r[i+1] + 1;
            }
        }
        ans = *l.iter().max().unwrap();
        for i in 1..n-1 {
            if nums[i-1] < nums[i+1] {
                ans = ans.max(l[i-1] + r[i+1]);
            }
        }
        ans = ans + 1;
        if ans > n {
            n as i32
        } else {
            ans as i32
        }
    }
}

TypeScript

class Solution {
    longestIncreasingSubarray(nums: number[]): number {
        const n = nums.length;
        const l = Array(n).fill(1);
        const r = Array(n).fill(1);
        let ans = 1;
        for (let i = 1; i < n; i++)
            l[i] = nums[i] > nums[i-1] ? l[i-1] + 1 : 1;
        for (let i = n-2; i >= 0; i--)
            r[i] = nums[i] < nums[i+1] ? r[i+1] + 1 : 1;
        ans = Math.max(...l);
        for (let i = 1; i < n-1; i++)
            if (nums[i-1] < nums[i+1])
                ans = Math.max(ans, l[i-1] + r[i+1]);
        return Math.min(ans+1, n);
    }
}

Complexity

• ⏰ Time complexity: O(n) — We traverse the array a few times to fill l and r and to find the answer.
• 🧺 Space complexity: O(n) — We use two extra arrays of size n for l and r.