Skip to main content
Talentd

Longest Non-Decreasing Subarray After Replacing at Most One Element - Solution & Explanation

MediumArrayDynamic Programming11 min readAsked at: Google
Practice this problem

Problem Statement

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] <= 109​​​​​​​

Approach Overview

Problem 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.

Solution

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:

  1. If the elements on the left and right sides of 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.
  2. Otherwise, we can replace position 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Replacement + ScanO(n²)O(1)Useful for understanding how a single modification affects neighboring order.
Dynamic Programming with Left/Right ArraysO(n)O(n)General optimized solution when you want to track segment lengths from both directions.
Prefix and Suffix Decomposition + EnumerationO(n)O(n)Best practical solution; checks each index once after preprocessing.

Video Solution

Longest Non-Decreasing Subarray After Replacement | LeetCode 3738 | Biweekly Contest 169 • Sanyam IIT Guwahati • 1,954 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Longest Non-Decreasing Subarray After Replacing at Most One Element easy or hard?
The problem is typically rated Medium difficulty. The main challenge is recognizing that a single replacement can connect two valid segments, which leads to the prefix–suffix preprocessing technique rather than brute-force scanning.
Longest Non-Decreasing Subarray After Replacing at Most One Element Python/Java solution
Implement the prefix and suffix approach by first computing two arrays storing non-decreasing segment lengths. Then iterate through each index to test the effect of replacing that element. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Longest Non-Decreasing Subarray After Replacing at Most One Element in O(n)?
Compute two arrays: prefix[i] for the longest non-decreasing segment ending at i and suffix[i] for the segment starting at i. For each index i, treat it as the replaced element and check whether nums[i-1] can connect with nums[i+1]. If the boundary condition holds, combine prefix[i-1] and suffix[i+1] with the replaced element to form a longer segment.
What is the best approach for Longest Non-Decreasing Subarray After Replacing at Most One Element?
The prefix and suffix decomposition approach is the most efficient. Precompute the longest non-decreasing subarray ending at each index and starting at each index, then evaluate every position as the replacement point. This allows constant-time merging checks and produces an overall O(n) time solution with O(n) space.
Is Longest Non-Decreasing Subarray After Replacing at Most One Element asked at Google/Amazon/Meta?
Problems involving longest non-decreasing segments and single modifications appear frequently in interviews at companies like Google, Amazon, and Meta. They test array traversal, boundary reasoning, and prefix/suffix preprocessing techniques commonly used in dynamic programming patterns.
What data structure is used in Longest Non-Decreasing Subarray After Replacing at Most One Element?
The solution primarily uses arrays to store prefix and suffix lengths. These auxiliary arrays allow constant-time lookup of the longest valid segment on either side of a candidate replacement index.
What is the time complexity of Longest Non-Decreasing Subarray After Replacing at Most One Element?
The optimal solution runs in O(n) time because the array is scanned a constant number of times to build prefix and suffix lengths and then evaluated once more for the replacement position. Space complexity is O(n) for the auxiliary arrays that store segment lengths.

Ready to solve this problem?

Practice Longest Non-Decreasing Subarray After Replacing at Most One Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays