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).
Example 1:
Input: nums = [1,2,3,1,2]
Output: 4
Explanation:
Replacing nums[3] = 1 with 3 gives the array [1, 2, 3, 3, 2].
The longest non-decreasing subarray is [1, 2, 3, 3], which has a length of 4.
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation:
All elements in nums are equal, so it is already non-decreasing and the entire nums forms a subarray of length 5.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: Given an integer array, you can replace at most one element with any value. The goal is to maximize the length of a contiguous non-decreasing subarray. The challenge is figuring out how a single modification can connect two already valid segments.
Approach 1: Brute Force Replacement + Scan (O(n²) time, O(1) space)
Try replacing each index with a value that could potentially maintain order with its neighbors, then scan the array to compute the longest non-decreasing segment. For every candidate position i, recompute the maximum valid subarray by iterating through the array and checking nums[j] <= nums[j+1]. This approach works because only one element can change, but repeatedly rescanning the array makes it quadratic. It is useful for reasoning about how a replacement affects adjacent elements but does not scale for large inputs.
Approach 2: Dynamic Programming with Left/Right Lengths (O(n) time, O(n) space)
Precompute the length of the longest non-decreasing segment ending at each index using a forward pass. Then compute the longest segment starting at each index using a backward pass. These arrays capture how far a valid sequence extends without modification. When considering a replacement at index i, check whether the left segment ending at i-1 can connect with the right segment starting at i+1. This works because a single replacement can act as a bridge between two valid runs if the boundary condition can be satisfied.
Approach 3: Prefix and Suffix Decomposition + Enumeration (O(n) time, O(n) space)
Compute two arrays: prefix[i] = length of the longest non-decreasing subarray ending at i, and suffix[i] = length starting at i. Iterate over every index as the potential replacement point. If replacing nums[i] allows the left value nums[i-1] to be less than or equal to the right value nums[i+1], the new length becomes prefix[i-1] + 1 + suffix[i+1]. Otherwise, you extend only one side. This decomposition reduces the problem to constant-time checks per index after preprocessing. The technique is a common pattern when working with array continuity problems and is closely related to prefix/suffix ideas used in dynamic programming.
Recommended for interviews: The prefix and suffix decomposition approach is the expected solution. It demonstrates strong reasoning about array boundaries and efficient preprocessing. Starting with the brute force explanation shows understanding of the constraint (only one replacement), while moving to the O(n) solution shows optimization skills typically expected in mid-level interview problems involving arrays and dynamic programming.
We can 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.
Then, we traverse the array in the range [1, n-1]. If nums[i] geq nums[i-1], we update left[i] to left[i-1] + 1. Similarly, we traverse the array backwards in the range [n-2, 0]. If nums[i] leq nums[i+1], we update right[i] to right[i+1] + 1.
Next, we can compute the final answer by enumerating each position. For each position i, we can calculate the length of the longest non-decreasing subarray centered at i in the following way:
i do not satisfy nums[i-1] leq nums[i+1], we can only choose the non-decreasing subarray from either the left or right side, so the answer is max(left[i-1], right[i+1]) + 1.i with an appropriate value so that the non-decreasing subarrays on the left and right can be connected, so the answer is left[i-1] + right[i+1] + 1.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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Replacement + Scan | O(n²) | O(1) | Useful for understanding how a single modification affects neighboring order. |
| Dynamic Programming with Left/Right Arrays | O(n) | O(n) | General optimized solution when you want to track segment lengths from both directions. |
| Prefix and Suffix Decomposition + Enumeration | O(n) | O(n) | Best practical solution; checks each index once after preprocessing. |
Longest Non-Decreasing Subarray After Replacement | LeetCode 3738 | Biweekly Contest 169 • Sanyam IIT Guwahati • 1,755 views views
Watch 3 more video solutions →Practice Longest Non-Decreasing Subarray After Replacing at Most One Element with our built-in code editor and test cases.
Practice on FleetCode