Watch 4 video solutions for Longest Non-Decreasing Subarray After Replacing at Most One Element, a medium level problem involving Array, Dynamic Programming. This walkthrough by Sanyam IIT Guwahati has 1,755 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |