3738. Longest Non-Decreasing Subarray After Replacing at Most One Element

MediumArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

An array is said to be non-decreasing if each element is greater than or equal to its previous one (if it exists).

In other words, you may pick a single position in the array and change its value to anything you want (or leave the array unchanged). After this optional modification, you want to find the longest contiguous segment where every element is greater than or equal to the element before it, and return that segment's length.

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.

Precomputing left and right non-decreasing run lengths then checking each replacement position is a straightforward O(n) scan.

Open in Flowchart

Intuition

The key observation is that since we can replace at most one element, the longest non-decreasing subarray we obtain will fall into one of two situations:

No replacement is needed. The subarray is already non-decreasing, so we just need to find the longest existing non-decreasing run.
Exactly one element is replaced. When we change one element at some position i, the modified subarray is naturally split into a "left part" (ending right before i) and a "right part" (starting right after i), with position i acting as a bridge between them.

This naturally leads us to think about each position i as the candidate for replacement. For any position i, we want to know:

How long is the non-decreasing subarray that ends right before i?
How long is the non-decreasing subarray that starts right after i?

To answer these quickly, we precompute two helper arrays:

left[i]: the length of the longest non-decreasing subarray ending at index i.
right[i]: the length of the longest non-decreasing subarray starting at index i.

Both can be filled in with a single pass each. For left, scanning left to right, if nums[i] >= nums[i - 1] then left[i] = left[i - 1] + 1. For right, scanning right to left, if nums[i] <= nums[i + 1] then right[i] = right[i + 1] + 1.

Now, when we replace position i and try to connect the left run with the right run, there is one crucial condition. The left run ends with the value nums[i - 1], and the right run begins with the value nums[i + 1]. To bridge them with a single replaced value at i, we need some value x such that nums[i - 1] <= x <= nums[i + 1]. Such an x exists only when nums[i - 1] <= nums[i + 1].

If nums[i - 1] <= nums[i + 1], the two sides can be joined, giving a total length of left[i - 1] + right[i + 1] + 1.
If nums[i - 1] > nums[i + 1], the two sides cannot be merged through one value. We can still attach i to only one side, so the best we get is left[i - 1] + 1 (extend the left run by placing a value >= nums[i - 1]) or right[i + 1] + 1 (extend the right run by placing a value <= nums[i + 1]).

By enumerating every position i as the replacement point and combining these results with the unmodified longest run, we capture all possibilities and take the maximum as the final answer.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Prefix and Suffix Decomposition + Enumeration

We use two arrays left and right to record the length of the longest non-decreasing subarray ending and starting at each position, respectively. Initially, left[i] = 1 and right[i] = 1, since a single element by itself is always a non-decreasing subarray of length 1.

Step 1: Build the left array.

We traverse the array in the range [1, n - 1]. If nums[i] >= nums[i - 1], the current element can extend the non-decreasing run ending at i - 1, so we update left[i] to left[i - 1] + 1. Otherwise, left[i] stays at 1.

for i in range(1, n):
    if nums[i] >= nums[i - 1]:
        left[i] = left[i - 1] + 1

Step 2: Build the right array.

Similarly, we traverse the array backwards in the range [n - 2, 0]. If nums[i] <= nums[i + 1], the current element can extend the non-decreasing run starting at i + 1, so we update right[i] to right[i + 1] + 1.

for i in range(n - 2, -1, -1):
    if nums[i] <= nums[i + 1]:
        right[i] = right[i + 1] + 1

Step 3: Enumerate each position as the replacement point.

We first initialize the answer to max(left), which covers the case where no replacement is performed (the longest existing non-decreasing run).

Then we enumerate each position i as the candidate to replace. We define:

a = left[i - 1] if i - 1 >= 0, otherwise a = 0.
b = right[i + 1] if i + 1 < n, otherwise b = 0.

For each position i, there are two cases:

If both neighbors exist and nums[i - 1] > nums[i + 1], the left and right runs cannot be bridged by a single replaced value. We can only attach i to one side, so the answer candidates are a + 1 and b + 1.
Otherwise (either a neighbor is missing or nums[i - 1] <= nums[i + 1]), the two sides can be connected through the replaced value, so the answer candidate is a + b + 1.

ans = max(left)
for i in range(n):
    a = 0 if i - 1 < 0 else left[i - 1]
    b = 0 if i + 1 >= n else right[i + 1]
    if i - 1 >= 0 and i + 1 < n and nums[i - 1] > nums[i + 1]:
        ans = max(ans, a + 1, b + 1)
    else:
        ans = max(ans, a + b + 1)
return ans

Finally, we take the maximum value across all positions as the final answer.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums. We make a constant number of linear passes over the array and use two auxiliary arrays of size n.

Example Walkthrough

Let's walk through the solution with the array nums = [4, 2, 3, 1, 5] (length n = 5).

Step 1: Build the left array.

Recall left[i] is the length of the longest non-decreasing subarray ending at index i. We start with every entry set to 1 and scan left to right, extending whenever nums[i] >= nums[i - 1].

`i`	`nums[i]`	Comparison	`left[i]`
0	4	(base case)	1
1	2	`2 >= 4`? No	1
2	3	`3 >= 2`? Yes → `left[1] + 1`	2
3	1	`1 >= 3`? No	1
4	5	`5 >= 1`? Yes → `left[3] + 1`	2

So left = [1, 1, 2, 1, 2].

Step 2: Build the right array.

Here right[i] is the length of the longest non-decreasing subarray starting at index i. We start with every entry at 1 and scan right to left, extending whenever nums[i] <= nums[i + 1].

`i`	`nums[i]`	Comparison	`right[i]`
4	5	(base case)	1
3	1	`1 <= 5`? Yes → `right[4] + 1`	2
2	3	`3 <= 1`? No	1
1	2	`2 <= 3`? Yes → `right[2] + 1`	2
0	4	`4 <= 2`? No	1

So right = [1, 2, 1, 2, 1].

Step 3: Enumerate each position as the replacement point.

First, the no-replacement baseline is ans = max(left) = 2.

Now we test replacing each index i, using a = left[i - 1] (left run before i) and b = right[i + 1] (right run after i):

`i`	`a`	`b`	Bridge check `nums[i-1] > nums[i+1]`?	Candidate(s)	New `ans`
0	0	`right[1]=2`	left neighbor missing → bridge ok	`a + b + 1 = 0 + 2 + 1 = 3`	3
1	`left[0]=1`	`right[2]=1`	`nums[0]=4 > nums[2]=3`? Yes → no bridge	`a+1=2`, `b+1=2`	3
2	`left[1]=1`	`right[3]=2`	`nums[1]=2 > nums[3]=1`? Yes → no bridge	`a+1=2`, `b+1=3`	3
3	`left[2]=2`	`right[4]=1`	`nums[2]=3 > nums[4]=5`? No → bridge ok	`a + b + 1 = 2 + 1 + 1 = 4`	4
4	`left[3]=1`	0	right neighbor missing → bridge ok	`a + b + 1 = 1 + 0 + 1 = 2`	4

The maximum candidate appears at i = 3. Here the left run is [2, 3] (ending at index 2) and the right run is [5] (starting at index 4). Since nums[2] = 3 <= nums[4] = 5, we can replace nums[3] = 1 with any value x where 3 <= x <= 5 (say 4), turning the array into [4, 2, 3, 4, 5]. The segment [2, 3, 4, 5] is non-decreasing with length 4.

Result: the function returns 4.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def longestSubarray(self, nums: List[int]) -> int:
6        n = len(nums)
7
8        # left[i]: length of the longest non-decreasing run ending at index i
9        left = [1] * n
10        # right[i]: length of the longest non-decreasing run starting at index i
11        right = [1] * n
12
13        # Build left runs: extend when current element is >= previous element
14        for i in range(1, n):
15            if nums[i] >= nums[i - 1]:
16                left[i] = left[i - 1] + 1
17
18        # Build right runs: extend when current element is <= next element
19        for i in range(n - 2, -1, -1):
20            if nums[i] <= nums[i + 1]:
21                right[i] = right[i + 1] + 1
22
23        # Baseline answer: the longest non-decreasing run without any removal
24        ans = max(left)
25
26        # Try removing each element nums[i] and join the runs on both sides
27        for i in range(n):
28            # Length of the non-decreasing run ending just before i
29            prev_len = 0 if i - 1 < 0 else left[i - 1]
30            # Length of the non-decreasing run starting just after i
31            next_len = 0 if i + 1 >= n else right[i + 1]
32
33            if i - 1 >= 0 and i + 1 < n and nums[i - 1] > nums[i + 1]:
34                # The two neighbors cannot be joined into one run,
35                # so we can only keep one side plus the removed slot
36                ans = max(ans, prev_len + 1, next_len + 1)
37            else:
38                # The two sides can be merged after removing nums[i]
39                ans = max(ans, prev_len + next_len + 1)
40
41        return ans
42

1class Solution {
2    public int longestSubarray(int[] nums) {
3        int n = nums.length;
4
5        // leftLen[i]: length of the longest non-decreasing run ending at index i
6        int[] leftLen = new int[n];
7        // rightLen[i]: length of the longest non-decreasing run starting at index i
8        int[] rightLen = new int[n];
9
10        // Every single element forms a run of length 1 by default
11        Arrays.fill(leftLen, 1);
12        Arrays.fill(rightLen, 1);
13
14        // The answer is at least 1 (a single element)
15        int ans = 1;
16
17        // Build leftLen: extend the run while the array stays non-decreasing
18        for (int i = 1; i < n; i++) {
19            if (nums[i] >= nums[i - 1]) {
20                leftLen[i] = leftLen[i - 1] + 1;
21                ans = Math.max(ans, leftLen[i]);
22            }
23        }
24
25        // Build rightLen: extend the run from right to left while non-decreasing
26        for (int i = n - 2; i >= 0; i--) {
27            if (nums[i] <= nums[i + 1]) {
28                rightLen[i] = rightLen[i + 1] + 1;
29            }
30        }
31
32        // Try deleting each element i and see how long a run we can form
33        for (int i = 0; i < n; i++) {
34            // Length of the run that ends just before i (0 if i is the first element)
35            int prevLen = (i - 1 < 0) ? 0 : leftLen[i - 1];
36            // Length of the run that starts just after i (0 if i is the last element)
37            int nextLen = (i + 1 >= n) ? 0 : rightLen[i + 1];
38
39            if (i - 1 >= 0 && i + 1 < n && nums[i - 1] > nums[i + 1]) {
40                // After deleting i, the left and right runs cannot be joined
41                // because nums[i-1] > nums[i+1] breaks the non-decreasing order.
42                // So we can only keep one side (plus the deleted slot's contribution of 1).
43                ans = Math.max(ans, Math.max(prevLen + 1, nextLen + 1));
44            } else {
45                // The two surrounding runs can be merged after deleting i.
46                ans = Math.max(ans, prevLen + nextLen + 1);
47            }
48        }
49
50        return ans;
51    }
52}
53

1class Solution {
2public:
3    int longestSubarray(vector<int>& nums) {
4        int n = nums.size();
5
6        // leftRun[i]: length of the non-decreasing run ending at index i
7        // rightRun[i]: length of the non-decreasing run starting at index i
8        vector<int> leftRun(n, 1);
9        vector<int> rightRun(n, 1);
10
11        // Build the non-decreasing run length ending at each index (left to right)
12        for (int i = 1; i < n; ++i) {
13            if (nums[i] >= nums[i - 1]) {
14                leftRun[i] = leftRun[i - 1] + 1;
15            }
16        }
17
18        // Build the non-decreasing run length starting at each index (right to left)
19        for (int i = n - 2; i >= 0; --i) {
20            if (nums[i] <= nums[i + 1]) {
21                rightRun[i] = rightRun[i + 1] + 1;
22            }
23        }
24
25        // Baseline answer: the longest run without removing any element
26        int ans = ranges::max(leftRun);
27
28        // Try removing each index i, then check if the runs on both sides can merge
29        for (int i = 0; i < n; ++i) {
30            // Length of the run just before index i (0 if no left neighbor)
31            int leftLen = (i - 1 < 0) ? 0 : leftRun[i - 1];
32            // Length of the run just after index i (0 if no right neighbor)
33            int rightLen = (i + 1 >= n) ? 0 : rightRun[i + 1];
34
35            if (i - 1 >= 0 && i + 1 < n && nums[i - 1] > nums[i + 1]) {
36                // The neighbors cannot be joined into one increasing run,
37                // so only one side can be extended after removing nums[i]
38                ans = max({ans, leftLen + 1, rightLen + 1});
39            } else {
40                // The two surrounding runs can be merged after removing nums[i]
41                ans = max(ans, leftLen + rightLen + 1);
42            }
43        }
44
45        return ans;
46    }
47};
48

1/**
2 * Finds the length of the longest turbulent subarray.
3 *
4 * A turbulent subarray is one in which the comparison sign between
5 * adjacent elements flips for each pair of consecutive elements.
6 *
7 * Strategy:
8 *  - `ascendingRun[i]`  : length of the longest non-decreasing run ending at i.
9 *  - `descendingRun[i]` : length of the longest non-increasing run starting at i.
10 *  - For each index treated as a "pivot", combine the run on its left and
11 *    the run on its right to evaluate candidate lengths.
12 */
13function longestSubarray(nums: number[]): number {
14    const length: number = nums.length;
15
16    // ascendingRun[i]: length of the longest non-decreasing segment ending at index i.
17    const ascendingRun: number[] = Array(length).fill(1);
18
19    // descendingRun[i]: length of the longest non-increasing segment starting at index i.
20    const descendingRun: number[] = Array(length).fill(1);
21
22    // Build the non-decreasing run lengths from left to right.
23    for (let i = 1; i < length; i++) {
24        if (nums[i] >= nums[i - 1]) {
25            ascendingRun[i] = ascendingRun[i - 1] + 1;
26        }
27    }
28
29    // Build the non-increasing run lengths from right to left.
30    for (let i = length - 2; i >= 0; i--) {
31        if (nums[i] <= nums[i + 1]) {
32            descendingRun[i] = descendingRun[i + 1] + 1;
33        }
34    }
35
36    // Baseline answer: the longest purely non-decreasing run.
37    let answer: number = Math.max(...ascendingRun);
38
39    // Examine each index as a potential pivot point.
40    for (let i = 0; i < length; i++) {
41        // Length of the ascending run that ends just before index i.
42        const leftRun: number = i - 1 < 0 ? 0 : ascendingRun[i - 1];
43
44        // Length of the descending run that starts just after index i.
45        const rightRun: number = i + 1 >= length ? 0 : descendingRun[i + 1];
46
47        if (i - 1 >= 0 && i + 1 < length && nums[i - 1] > nums[i + 1]) {
48            // The left neighbor is strictly greater than the right neighbor,
49            // so the two runs cannot be joined through index i.
50            // Take the better of attaching i to the left run or the right run.
51            answer = Math.max(answer, Math.max(leftRun + 1, rightRun + 1));
52        } else {
53            // The runs can be merged through index i, forming a longer segment.
54            answer = Math.max(answer, leftRun + rightRun + 1);
55        }
56    }
57
58    return answer;
59}
60

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm consists of several sequential loops, each iterating over the array at most once: the first loop computes the left array in O(n), the second loop computes the right array in O(n), the max(left) call takes O(n), and the final loop iterates through all indices in O(n). Since these operations are sequential rather than nested, the total time complexity is O(n).
Space Complexity: O(n), where n is the length of the array nums. Two auxiliary arrays left and right, each of size n, are used to store the lengths of the longest non-decreasing subarrays ending at and starting from each index, respectively. Thus, the additional space required scales linearly with the input size, giving a space complexity of O(n).

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

Common Pitfalls

Pitfall 1: Treating the replacement as a deletion rather than a value change

The most subtle pitfall in this problem is misunderstanding what "replacement" allows. When you replace nums[i], you do not remove it — you keep it as an element and assign it a new value. This means the resulting subarray that passes through position i includes that slot, contributing +1 to the length.

A common mistake is to model the operation as a removal (where the two neighboring runs simply get concatenated, giving prev_len + next_len). That logic would be correct for a "delete one element" variant, but here the replaced slot still occupies a position, so the joined length must be prev_len + next_len + 1.

Why the +1 matters: Consider nums = [1, 5, 3]. Replacing the middle 5 with any value in [1, 3] yields a fully non-decreasing array [1, x, 3] of length 3. If you forgot the +1 and computed prev_len + next_len = 1 + 1 = 2, you'd return the wrong answer.

# WRONG (models deletion):
ans = max(ans, prev_len + next_len)

# CORRECT (models replacement — the slot stays):
ans = max(ans, prev_len + next_len + 1)

Pitfall 2: Incorrectly handling the "cannot bridge" case

When both neighbors exist and nums[i - 1] > nums[i + 1], you cannot pick a single value for nums[i] that satisfies both nums[i-1] <= nums[i] <= nums[i+1] simultaneously. A frequent error is to still compute prev_len + next_len + 1 in this situation, which over-counts.

The correct handling is to attach the replaced slot to only one side:

Extend the left run: prev_len + 1 (set nums[i] >= nums[i-1]).
Extend the right run: next_len + 1 (set nums[i] <= nums[i+1]).

# WRONG — assumes the two runs can always be bridged:
ans = max(ans, prev_len + next_len + 1)

# CORRECT — when nums[i-1] > nums[i+1], keep only one side:
if i - 1 >= 0 and i + 1 < n and nums[i - 1] > nums[i + 1]:
    ans = max(ans, prev_len + 1, next_len + 1)
else:
    ans = max(ans, prev_len + next_len + 1)

Concrete example: For nums = [4, 2, 1] at i = 1, we have nums[0] = 4 > nums[2] = 1. No single replacement value sits in [4, 1]. The best is prev_len + 1 = 2 (e.g., [4, 4, 1]) or next_len + 1 = 2 (e.g., [4, 1, 1]), giving 2 — not the incorrect 3.

Pitfall 3: Forgetting the no-replacement baseline

Since at most one replacement is allowed (zero is valid), the existing longest non-decreasing run must be considered. The line ans = max(left) covers this. Omitting it is usually harmless because the enumeration loop tends to recover the same value, but it is safer and clearer to initialize the baseline explicitly — especially as a guard for edge cases like a single-element array, where the loop's bridging logic might otherwise be reasoned about incorrectly.

Pitfall 4: Off-by-one and boundary indexing

When position i is at either end of the array, one of its neighbors does not exist. Failing to guard i - 1 >= 0 and i + 1 < n leads to index-out-of-range errors or accidental wrap-around (in languages where negative indices are valid, like Python, left[-1] silently reads the last element). Always default the missing side to 0:

prev_len = 0 if i - 1 < 0 else left[i - 1]
next_len = 0 if i + 1 >= n else right[i + 1]

This guarantees the boundary cases reduce cleanly to "one side only," and the bridge condition (i - 1 >= 0 and i + 1 < n) is only evaluated when both neighbors genuinely exist.

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:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering