Find the Longest Non-Decreasing Subarray After One Replacement
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find the Longest Non-Decreasing Subarray After One Replacement
You are given an integer array `nums`. You may replace at most one element with any integer value of your choice.
Implement:
```text
longestNonDecreasingSubarrayAfterOneReplacement(nums) -> integer
```
Return the maximum length of a contiguous subarray that can be made non-decreasing after at most one replacement. A subarray is non-decreasing when each value is greater than or equal to the value immediately before it. The replacement may be made inside or outside the returned subarray, and using no replacement is allowed.
## Constraints
- `1 <= nums.length <= 100,000`
- `-10^9 <= nums[i] <= 10^9`
## Examples
### Example 1
```text
nums = [1, 2, 3, 1, 2]
output = 4
```
Replace the fourth value with `3`. The prefix `[1, 2, 3, 3]` is then non-decreasing.
### Example 2
```text
nums = [2, 2, 2, 2, 2]
output = 5
```
The complete array is already non-decreasing, so no replacement is needed.
Quick Answer: Find the longest contiguous non-decreasing run obtainable after replacing at most one array element. The prompt permits any integer replacement or no replacement and defines equality, contiguity, and the returned length for a deterministic linear-time target.
Given an integer array nums, you may replace at most one element with any integer value. Return the maximum length of a contiguous subarray that can be made non-decreasing after at most one replacement. Each value in a non-decreasing subarray is greater than or equal to its predecessor. The replacement may be inside or outside the returned subarray, and using no replacement is allowed.
Constraints
- 1 <= nums.length <= 100,000
- -10^9 <= nums[i] <= 10^9
- At most one element may be replaced by any integer.
- The returned subarray must be contiguous and non-decreasing.
Examples
Input: ([1, 2, 3, 1, 2],)
Expected Output: 4
Explanation: The first source example replaces the fourth value and makes a length-four prefix non-decreasing.
Input: ([2, 2, 2, 2, 2],)
Expected Output: 5
Explanation: The second source example needs no replacement.
Hints
- Using no replacement is allowed.
- A replacement at an endpoint only needs to agree with one neighbor.
- To join runs on both sides of a replaced position, consider whether some integer can lie between its two neighbors.